{"id":300,"date":"2018-07-19T05:20:06","date_gmt":"2018-07-19T05:20:06","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=300"},"modified":"2018-12-12T10:30:48","modified_gmt":"2018-12-12T10:30:48","slug":"binary-search-trees-ii","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/binary-search-trees-ii\/","title":{"rendered":"Binary Search Trees-II"},"content":{"raw":"
\"epgp<\/a>\r\n<\/span><\/div>\r\n
\r\n\r\n \r\n\r\n \r\n\r\n \r\n

Welcome to the e-PG Pathshala Lecture Series on Data Structures. We have understood the basic concept of an important ADT \u2013 the binary search tree ADT. In this module we will discuss some more operations of binary search tree ADT.<\/p>\r\n \r\n\r\nLearning Objectives<\/strong>\r\n\r\n \r\n\r\nThe learning objectives of the module are as follows:\r\n\r\n \r\n\r\n\u2022 To illustrate the different types of Binary Search Tree Traversals\r\n\r\n\u2022 To discuss the construction of Binary Search Trees\r\n\r\n\u2022 To describe Insertion into Binary Search Trees\r\n\r\n\u2022 To explain Deletion from Binary Search Trees\r\n\r\n \r\n\r\n22.1\u00a0 Introduction<\/strong>\r\n\r\n \r\n

As you may recall from our last module Binary Search Trees (BST) or Lexicographic Trees are a type of Binary Trees with a special organization of data. A binary search tree is a binary tree with a special property called the BST-property. This property states that for a tree or sub-tree rooted at X, all keys to the left of X are lesser than the key at X and all keys to the right of X are greater than the key at X. We also assume that the keys of a BST are pairwise distinct.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n<\/div>\r\n

\r\n\r\n \r\n\r\n22.2\u00a0 Traversals of Binary Search Trees<\/strong>\r\n\r\n \r\n

Now let us consider the example of a binary search tree given in Figure 22.1. Traversals of binary search tree is similar to the traversal of binary trees but here we know that the binary tree is organized is a special way.<\/p>\r\n \r\n\r\n22.2.1<\/strong>\u00a0Preorder Traversal<\/strong>\r\n\r\n \r\n

We will first discuss the preorder traversal of a BST (Figure 22.2). Here we process the root (23<\/strong>) first. The root of the left subtree of 23 that is 14<\/strong> is processed, followed by 7<\/strong> root of left subtree of 14 is processed. Now since 7 has no left child, we process the right subtree of 7 that is 12<\/strong>. Now we have completed processing node 7, that is processing of left subtree of 14. Now we need to process the right subtree of 14 \u2013 which in this example does not exist. Therefore we have completed processing node 14 or in other words the left subtree of the root node 23. Now we need to process the right subtree of the root 23. Now we process the root node 67<\/strong>, then its left subtree 34<\/strong>. Since 34 has no children, we process the right subtree of 67 that is 89<\/strong>. Now 89 has no left child so we process the right child of 89, that is 90<\/strong>. Now we have completed traversing all the nodes. The preorder traversal is given in Figure 22.2.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n 22.2.2 Postorder Traversal<\/strong>\r\n\r\n \r\n

Now let us discuss the postorder traversal of the BST (Figure 22.3). Here we first need to process the left subtree of the root (23). In order to process the root of the left subtree of 23 that is subtree rooted 14 in post order, we need to process its left subtree that is subtree rooted at 7. Here since 7 has no left child, we go on to process it\u2019s right subtree \u2013 here only one child 12<\/strong>. Now we process node 7<\/strong>. We have completed processing left subtree of node 14. Now we need to process the right subtree of 14 \u2013 which in this example does not exist. Therefore we have completed processing left and right subtree of node 14, therefore we need to process node 14<\/strong>. On completion of processing node 14, we have completed processing left subtree of root node 23. Now we need to process the right subtree of the root 23 rooted at 67. Now we need to process the left subtree of 67 that is 34. Since 34 has no children, we process the node 34.<\/strong> Now we need to process the right subtree of 67 rooted at 89. Now 89 has no left child so we process the right child of\u00a089, that is <\/span>90<\/strong>. Now we have completed processing left and right subtree of 89, so we process the root <\/span>89<\/strong>. Now we have completed processing left and right subtree of the root 67, so we process the node <\/span>67<\/strong>. Now we have completed processing left and right subtree of the root 23, so we process the root <\/span>23<\/strong>. Now we have completed processing all the nodes of the tree. The postorder traversal is given in Figure 22.3.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n22.2.3 Inorder Traversal<\/strong>\r\n\r\n \r\n

Now let us discuss the in-order traversal of the BST (Figure 22.4). Here we first need to process the left subtree of the root (23). In order to process the root of the left subtree of 23 that is subtree rooted 14 in in-order, we need to process its left subtree that is subtree rooted at 7. Here since 7 has no left child, we process the node 7<\/strong>. We go on to process it\u2019s right subtree \u2013 here only one child 12<\/strong>. We have completed processing left subtree of node 14. Now we process node 14<\/strong>. Now we need to process the right subtree of 14 \u2013 which in this example does not exist. Therefore we have completed processing left and right subtree of node 14. On completion of processing node 14, we have completed processing left subtree of root node 23. Therefore we process the node 23<\/strong>. Now we need to process the right subtree of the root 23 rooted at 67. Now we need to process the left subtree of 67 that is 34. Since 34 has no left child, we process the node 34.<\/strong> We proceed in the same way by processing the left subtree, then root node and then right subtree until all the nodes are processed. The in-order traversal is given in Figure 22.4. The in-order traversal of a binary search tree produces a sequence of numbers which are in increasing order.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n22.2.4 Right Node Left Traversal<\/strong>\r\n\r\n<\/div>\r\n

\r\n\r\n \r\n

Now for the BST another type of traversal has also been defined called the right node left traversal (Figure 22.5). This traversal is similar to inorder traversal except that instead of left subtree \u2013root- right subtree, the traversal is carried out as right subtree \u2013node-left subtree. This type of traversal is important for a BST because this produces a descending sequence.<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n22.3\u00a0 Construction of a Binary Search Tree<\/strong>\r\n\r\n \r\n

Now let us consider the construction of BSTs. There are two things to remember. First the tree that is constructed must obey the binary search property. Second we need to search the BST to find the correct position in which is insert a node. That is we need to maintain the key property and ensure that the smaller values are in the left sub-tree and the larger values in right sub-tree for every node in the tree. We also need to remember for the same keys, different BSTs will be constructed if the keys are used for construction in a different order.<\/p>\r\n \r\n

Now the base case is when the tree is empty. In this case, we create new node for the item and make it the root of the BST. In the recursive case, if key (node to be added next) < root's value, add to the left subtree, otherwise add to the right subtree. Remember that all BST insertions take place at a leaf or a leaflike node. A leaflike node is a node that has one null subtree.<\/p>\r\n \r\n

In order to insert an element e, we need to find the node n<\/em> that should be e<\/em> 's parent, and set n<\/em> 's child to be a newly created node containing e. Now here we use the search operation in order to find the parent node n<\/em>. If the element or key is smaller than the root we are at, we examine the left subtree and if the elemnt is greater, we examine the right subtree in each case. When we can no longer proceed, we are at a leaf; this is the position at which to add the element e.<\/p>\r\n \r\n\r\n22.3.1<\/strong>\u00a0\u00a0\u00a0 Algorithm<\/strong>\r\n\r\n \r\n\r\nPerform search for value X\r\n\r\nSearch will end at node Y (if X not in tree). If the element to be added is a duplicate which is generally\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 not\u00a0 \u00a0allowed in BST we can indicate that insertion is not possible.<\/span>\r\n