Binary Search Tree PDF

Binary Search Tree Introduction Binary search trees (BST), sometimes called ordered or sorted binary trees. Properties: – The left subtree of a node contains only nodes with keys less than the node’s key. – The right subtree of a node contains only nodes with keys greater tha...

Binary Search Tree Introduction Binary search trees (BST), sometimes called ordered or sorted binary trees. Properties: – The left subtree of a node contains only nodes with keys less than the node’s key. – The right subtree of a node contains only nodes with keys greater than the node’s key. – The left and right subtree each must also be a binary search tree. There must be no duplicate nodes. BSTs keep keys in sorted order, so that lookup, addition, and deletion operations can be executed efficiently. Contd… All the operations traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree. On average, BST with n nodes has O(log2n) height. In the worst case, BST can have O(n) height. Example Structure code of a tree node struct node { int data; //Data element struct node * left; //Pointer to left node struct node * right; //Pointer to right node }; struct node * root = NULL; Contd… struct node * newnode(int element) { struct node * temp = (node * )malloc(sizeof(node)); temp->data=element; temp->left = temp->right = NULL; return temp; }  Traversals Preorder traversal: (parent, left, right) Inorder traversal: (left, parent, right) Postorder traversal: (left, right, parent) Preorder traversal 60, 41, 16, 25, 53, 46, 42, 55, 74, 65, 63, 62, 64, 70 Inorder traversal 16, 25, 41, 42, 46, 53, 55, 60, 62, 63, 64, 65, 70, 74 Postorder traversal 25, 16, 42, 46, 55, 53, 41, 62, 64, 63, 70, 65, 74, 60 Traversals Preorder traversal 16, 8, 25, 42, 62, 49, 58 Inorder traversal 8, 16, 25, 42, 49, 58, 62 Postorder traversal 8, 58, 49, 62, 42, 25, 16 void preorder(node *temp) { if (temp != NULL) { printf("%d", temp->data); preorder(temp->lchild); preorder(temp->rchild); }} preorder(41) → 41 preorder(16) → 16 41, 16, 25, 53, 46, 42, 55 preorder(NULL) → × preorder(25) → 25 preorder(NULL) → × preorder(NULL) → × preorder(53) → 53 preorder(46) → 46 preorder(42) → 42 preorder(NULL) → × preorder(NULL) → × preorder(NULL) → × preorder(55) → 55 preorder(NULL) → × preorder(NULL) → ×  16, 25, 41, 42, 46, 53, 55 void inorder(node *temp) { if (temp != NULL) { inorder(temp->lchild); printf("%d", temp->data); inorder(temp->rchild); }}  25, 16, 42, 46, 55, 53, 41 void postorder(node *temp) { if (temp != NULL) { postorder(temp->lchild); postorder(temp->rchild); printf("%d", temp->data); }} Searching  Contd… Running time is O(h), where h is the height of the tree.  Minimum and Maximum Maximum (rightmost) Minimum (leftmost)  Successor and Predecessor Successor is next node in inorder traversal. Predecessor is previous node in inorder traversal. 16, 25, 41, 42, 46, 53, 55, 60, 62, 63, 64, 65, 70, 74 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 TREE-SUCCESSOR-WITHOUT-PARENT(y,x) 1. if x.right ≠ NIL 2. return TREE-MINIMUM(x.right) 3. succ = NIL 4. while TRUE 5. if x.key < y.key 6. succ = y 7. y = y.left 8. else if x.key > y.key 9. y = y.right 10. else break 11. return succ TREE-SUCCESSOR-WITHOUT-PARENT(y,x) 1. if x.right ≠ NIL 2. return TREE-MINIMUM(x.right) 3. succ = NIL 4. while TRUE 5. if x.key < y.key 6. succ = y 7. y = y.left 8. else if x.key > y.key 9. y = y.right 10. else break 11. return succ Insertion A new key is always inserted at leaf. Start searching a key from root till a leaf node is found. – Add the new node as a child of the leaf node. Duplicate key values are not allowed. If key to be inserted is already present, then return that node. Create BST using 8, 3, 1, 10, 6, 14, 4, 7, 13 TREE-INSERT-WITHOUT-PARENT(T.root,z) 1. x = T.root 2. 3. if x == NIL return z Contd… 4. if z.key < x.key 5. x.left = TREE-INSERT-WITHOUT-PARENT(x.left,z) 6. else if z.key > x.key 7. x.right = TREE-INSERT-WITHOUT-PARENT(x.right,z) 8. return x Deletion 1. Search for a node to remove; 2. If the node is found, execute the remove algorithm. Three cases, i. Node to be removed has no children. ii. Node to be removed has one child. iii. Node to be removed has two children. Node to be removed has no children Set corresponding link of the parent to NULL and disposes the node. Example. Remove -4 from a BST. Node to be removed has one child Link single child (with it's subtree) directly to the parent of the removed node. Example. Remove 18 from a BST. Node to be removed has two children Find inorder successor, i.e. find the minimum value in right child of the node. Copy contents of the inorder successor (or found minimum) to the node being removed with. Delete the inorder successor (or found minimum) from the right subtree. Note: – The node with minimum value has no left child and, therefore, it's removal may result in first or second cases only. – Inorder predecessor can also be used. Contd… Remove 12 from a BST. 1 2 3 Delete 17 19 TREE-DELETE-WITHOUT-PARENT(T.root,k) 1. x = T.root 2. if x == NIL 3. return x 4. if k < x.key 5. x.left = TREE-DELETE-WITHOUT-PARENT(x.left,k) 6. else if k > x.key 7. x.right = TREE-DELETE-WITHOUT-PARENT(x.right,k) 8. else 9. if x.left == NIL 10. temp = x.right 11. delete x 12. return temp 13. else if x.right == NIL 14. temp = x.left 15. delete x 16. return temp 17. temp = TREE-MINIMUM(x.right) 18. x.key = temp.key 19. x.right = TREE-DELETE-WITHOUT-PARENT(x.right,temp.key) 20. return x Question… 15, 18, 6, 7, 17, 3, 4, 13, 9, 20, 2 Generate BST for the given sequence. Visit the generated BST using inorder, preorder, and postorder traversals. Delete 4, 7, and 15 in sequence showing BST after every deletion.  Inorder and Preorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT]  Inorder and Preorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] F A, B, C, D, E G, H, I  Inorder and Preorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] F B G, H, I A C, D, E  Inorder and Preorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] F B G, H, I A C, D, E  Inorder and Preorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] F B G, H, I A D C E  Inorder and Preorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] F B G A D C E H, I  Inorder and Preorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] F B G A D I C E H  Inorder and Postorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT]  Inorder and Postorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F A, B, C, D, E G, H, I  Inorder and Postorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F G A, B, C, D, E H, I  Inorder and Postorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F G A, B, C, D, E I H  Inorder and Postorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F B G I A C, D, E H  Inorder and Postorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F B G D I A C E H  Inorder and Postorder Inorder: A, B, C, D, E, F, G, H, I [LEFT PARENT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F B G A D I C E H  Preorder and Postorder Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT]  Preorder and Postorder Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F A, B, C, D, E, G, H, I  Preorder and Postorder Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F B G, H, I A, C, D, E  Preorder and Postorder Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F B G, H, I A C, D, E  Preorder and Postorder Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F B G, H, I A D C, E  Preorder and Postorder Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F B G, H, I A D C E  Preorder and Postorder Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT] F B G A D H, I C E  Preorder and Postorder Preorder: F, B, A, D, C, E, G, I, H [PARENT LEFT RIGHT] Postorder: A, C, E, D, B, H, I, G, F [LEFT RIGHT PARENT]  Preorder and Postorder (Full Tree) Preorder: F, B, A, D, C, E, H, G, I [LEFT PARENT RIGHT] Postorder: A, C, E, D, B, G, I, H, F [LEFT RIGHT PARENT] F B G, H, I A D C E  Preorder and Postorder (Full Tree) Preorder: F, B, A, D, C, E, H, G, I [LEFT PARENT RIGHT] Postorder: A, C, E, D, B, G, I, H, F [LEFT RIGHT PARENT] F B H A D G, I C E  Preorder and Postorder (Full Tree) Preorder: F, B, A, D, C, E, H, G, I [LEFT PARENT RIGHT] Postorder: A, C, E, D, B, G, I, H, F [LEFT RIGHT PARENT] F B H A D G I C E