1、Trees, Binary Trees, and Binary Search Trees,COMP171,Trees,Linear access time of linked lists is prohibitive Does there exist any simple data structure for which the running time of most operations (search, insert, delete) is O(log N)? Trees Basic concepts Tree traversal Binary tree Binary search tr
2、ee and its operations,Trees,A tree T is a collection of nodes T can be empty (recursive definition) If not empty, a tree T consists of a (distinguished) node r (the root), and zero or more nonempty subtrees T1, T2, , Tk,Tree can be viewed as a nested listsTree is also a graph ,Some Terminologies,Chi
3、ld and Parent Every node except the root has one parent A node can have an zero or more children Leaves Leaves are nodes with no children Sibling nodes with same parent,More Terminologies,Path A sequence of edges Length of a path number of edges on the path Depth of a node length of the unique path
4、from the root to that node Height of a node length of the longest path from that node to a leaf all leaves are at height 0 The height of a tree = the height of the root = the depth of the deepest leaf Ancestor and descendant If there is a path from n1 to n2 n1 is an ancestor of n2, n2 is a descendan
5、t of n1 Proper ancestor and proper descendant,Example: UNIX Directory,Example: Expression Trees,Leaves are operands (constants or variables) The internal nodes contain operators Will not be a binary tree if some operators are not binary,Tree Traversal,Used to print out the data in a tree in a certai
6、n order Pre-order traversal Print the data at the root Recursively print out all data in the leftmost subtree Recursively print out all data in the rightmost subtree,Preorder, Postorder and Inorder,Preorder traversal node, left, right prefix expression+a*bc*+*defg,Preorder, Postorder and Inorder,Pos
7、torder traversal left, right, node postfix expression abc*+de*f+g*+,Inorder traversal left, node, right infix expression a+b*c+d*e+f*g,Example: Unix Directory Traversal,PreOrder,PostOrder,Preorder, Postorder and Inorder Pseudo Code,Binary Trees,A tree in which no node can have more than two children
8、The depth of an “average” binary tree is considerably smaller than N, even though in the worst case, the depth can be as large as N 1.,Generic binary tree,Worst-case binary tree,Convert a Generic Tree to a Binary Tree,Binary Tree ADT,Possible operations on the Binary Tree ADT Parent, left_child, rig
9、ht_child, sibling, root, etc Implementation Because a binary tree has at most two children, we can keep direct pointers to them a linked list is physically a pointer, so is a tree. Define a Binary Tree ADT later ,A drawing of linked list with one pointer ,A drawing of binary tree with two pointers ,
10、Struct BinaryNode double element; / the data BinaryNode* left; / left childBinaryNode* right; / right child ,Binary Search Trees (BST),A data structure for efficient searching, inser-tion and deletion Binary search tree property For every node X All the keys in its left subtree are smaller than the
11、key value in X All the keys in its right subtree are larger than the key value in X,Binary Search Trees,A binary search tree,Not a binary search tree,Binary Search Trees,Average depth of a node is O(log N) Maximum depth of a node is O(N),The same set of keys may have different BSTs,Searching BST,If
12、we are searching for 15, then we are done. If we are searching for a key 15, then we should search in the right subtree.,Searching (Find),Find X: return a pointer to the node that has key X, or NULL if there is no such nodeTime complexity: O(height of the tree),find(const double x, BinaryNode* t) co
13、nst,Inorder Traversal of BST,Inorder traversal of BST prints out all the keys in sorted order,Inorder: 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20,findMin/ findMax,Goal: return the node containing the smallest (largest) key in the tree Algorithm: Start at the root and go left (right) as long as there is a
14、left (right) child. The stopping point is the smallest (largest) elementTime complexity = O(height of the tree),BinaryNode* findMin(BinaryNode* t) const,Insertion,Proceed down the tree as you would with a find If X is found, do nothing (or update something) Otherwise, insert X at the last spot on th
15、e path traversedTime complexity = O(height of the tree),void insert(double x, BinaryNode* / do nothing ,Deletion,When we delete a node, we need to consider how we take care of the children of the deleted node. This has to be done such that the property of the search tree is maintained.,Deletion unde
16、r Different Cases,Case 1: the node is a leaf Delete it immediately Case 2: the node has one child Adjust a pointer from the parent to bypass that node,Deletion Case 3,Case 3: the node has 2 children Replace the key of that node with the minimum element at the right subtree Delete that minimum elemen
17、t Has either no child or only right child because if it has a left child, that left child would be smaller and would have been chosen. So invoke case 1 or 2.Time complexity = O(height of the tree),void remove(double x, BinaryNode* ,Make a binary or BST ADT ,Struct Node double element; / the data Nod
18、e* left; / left childNode* right; / right child class Tree public:Tree(); / constructorTree(const Tree ,update,access, selection,For a generic (binary) tree:,(insert and remove are different from those of BST),Struct Node double element; / the data Node* left; / left childNode* right; / right child
19、class BST public:BST(); / constructorBST(const Tree ,update,access, selection,For BST tree:,BST is for efficient search, insertion and removal, so restricting these functions.,class BST public:BST();BST(const Tree,Weiss textbook:,root, left subtree, right subtree are missing:1. we cant write other t
20、ree algorithms, is implementation dependent, BUT,2. this is only for BST (we only need search, insert and remove, may not need other tree algorithms)so its two layers, the public for BST, and the private for Binary Tree.3. it might be defined internally in private part (actually its implicitly done).,Comments:,void insert(double x, BinaryNode* / do nothing ,void insert(double x) insert(x,root); ,A public non-recursive member function:,A private recursive member function:,
