Report

Computer Sciences Department 1 Binary Search Trees Chapter 12 Computer Sciences Department 3 Objectives The idea of Binary Search Tree Operations of Binary Search Tree The run time of Binary Search Tree Analysis of Binary Search Tree Computer Sciences Department 4 Search trees -1 Search trees are data structures that support many dynamic-set operations, including SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and DELETE. Computer Sciences Department 5 Search trees - 2 Basic operations on a binary search tree take time proportional to the height of the tree. For a complete binary tree with n nodes, such operations run in” O(lg n) = height” worst-case time. If the tree is a linear chain “ linear time algorithm” of n nodes, however, the same operations take O (n) worstcase time (the process will always cover all the nodes = O (n)). The height of the Binary Search Tree equals the number of links from the root node to the deepest node. Computer Sciences Department 6 What is a binary tree? Property 1: each node can have up to two successor nodes (children) The predecessor node of a node is called its parent The "beginning" node is called the root (no parent) A node without children is called a leaf Property 2: a unique path exists from the root to every other node Computer Sciences Department 7 What is a binary search tree? a tree can be represented by a linked data structure in which each node is an object. Computer Sciences Department 8 key field - 1 In addition to a key field and satellite data, each node contains fields left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate field contains the value NIL. The root node is the only node in the tree whose parent field is NIL. Computer Sciences Department 9 key field -2 The keys in a binary search tree are always stored in such a way as to satisfy the binary-search-tree property: Computer Sciences Department 10 Computer Sciences Department 11 Inorder, preorder, and postorder The binary-search-tree property allows us to print out all the keys in a binary search tree in sorted order by a simple recursive algorithm, called an inorder tree walk. This algorithm is so named because the key of the root of a subtree is printed between the values in its left subtree and those in its right subtree. Similarly, a preorder tree walk prints the root before the values in either subtree, and A postorder tree walk prints the root after the values in its subtrees. It takes O(n) time to walk a tree of n nodes Computer Sciences Department 12 Computer Sciences Department 13 Computer Sciences Department 14 Computer Sciences Department 15 Computer Sciences Department 16 Computer Sciences Department 17 Computer Sciences Department 18 INORDER-TREE-WALK procedure Procedure to print all the elements in a binary search tree T , we call INORDER-TREE-WALK(root[T ]). Computer Sciences Department 19 Computer Sciences Department 20 Querying a binary search tree Computer Sciences Department 21 Search the BST x for a value k To search for the key 13 in the tree, we follow the path 15 → 6 → 7 → 13 from the root. Computer Sciences Department 22 Note: Search operation takes time O(h) “proportional to the height of the tree”, where h is the height of a BST Minimum and maximum Computer Sciences Department Note: max and min operations take time O(h) “proportional to the height of the tree”, 23 where h is the height of a BST Successor and predecessor Given a node in a binary search tree, it is sometimes important to be able to find its successor in the sorted order determined by an in-order tree walk. If all keys are distinct, the successor of a node x is the node with the smallest key greater than key[x]. Computer Sciences Department 24 Computer Sciences Department 25 Computer Sciences Department 26 Computer Sciences Department 27 - If the right subtree of node x is nonempty, then the successor of x is just the leftmost node in the right subtree, - If the right subtree of node x is empty and x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestor of x. - the successor of the node with key 15 in Figure 12.2 is the node with key 17 - the successor of the node with key 13 is the node with key 15. Computer Sciences Department 28 Insertion and deletion Computer Sciences Department 29 Insertion and deletion operations take time proportional to the height of the tree O(h) Deletion (in lab.) Computer Sciences Department 30 Computer Sciences Department 31 Randomly built binary search trees Self study Computer Sciences Department 32 Conclusion -1 Binary search trees come in many shapes. The shape of the tree determines the efficiency of its operations. Logarithmic time is generally much faster than linear time. For example, for n = 1,000,000: log2 n = 20. Using binary search trees to represent sets: insert, search, remove, …………… O(h) = O(log2 n) Using linear data structures to represent sets: insert, search, remove, …………… O(n) Balanced BTS: Easier insertion/deletion Running time = O(log2 n) Computer Sciences Department 33 Conclusion -2 Computer Sciences Department 34