{"id":278,"date":"2018-07-19T05:04:27","date_gmt":"2018-07-19T05:04:27","guid":{"rendered":"http:\/\/csp01.epgpbooks.inflibnet.ac.in\/?post_type=chapter&p=278"},"modified":"2018-12-12T10:13:04","modified_gmt":"2018-12-12T10:13:04","slug":"binary-search-trees-i","status":"publish","type":"chapter","link":"https:\/\/ebooks.inflibnet.ac.in\/csp01\/chapter\/binary-search-trees-i\/","title":{"rendered":"Binary Search Trees-I"},"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 Tree ADT. In this module we will discuss one very important type of binary tree that is 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 understand the concept of Binary Search Trees\r\n\r\n\u2022 To discuss the Binary Search Tree Search\r\n\r\n\u2022 To describe Traversal of Binary Search Trees \u2013 the In-order traversal\r\n\r\n\u2022 To explain the operations of finding the Successor and Predecessor of a node in a Binary Search Tree\r\n\r\n \r\n\r\n21.1\u00a0 Introduction<\/strong>\r\n\r\n \r\n

Binary Search Trees (BST) or Lexicographic Trees are a type of Binary Trees with a special organization of data. This organization of the nodes of the binary tree makes searching for an element faster of the O(log n) and for some types of balanced binary search trees (we will discuss this in later modules) insertions and deletions also has a time complexity of the O(log n). However in general insertions and deletions in BST have a complexity of the O(h) where h is the height of the tree. The properties of BST are defined in terms of the maximum number of leaves, maximum number of nodes N and the average depth for the N nodes.<\/p>\r\n \r\n

A binary search tree is a binary tree with a special property called the BST-property, which is defined as follows:<\/p>\r\n \r\n\r\n\u2022\u00a0 For a tree or sub-tree rooted at X,\r\n\r\n\u2013\u00a0 All keys to the left of X are lesser than the key at X\r\n\r\n\u2013\u00a0 All keys to the right of X are greater than the key at X\r\n\r\n\u2022\u00a0 This property is true for every sub-tree of the BST\r\n\r\n\u2022\u00a0 We can assume that the keys of a BST are pairwise distinct\r\n\r\n \r\n

In other words all items in the left subtree are less than the root K, and all items in the right subtree are greater than the root K (Figure 21.1).<\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n21.2 Binary Search Tree Property<\/strong>\r\n\r\n \r\n\r\nAll the stored keys in a binary search tree must satisfy the binary search tree<\/em> property.\r\n\r\nAll nodes K in left sub-tree of R<\/em>, will be such that key<\/em>[K<\/em>] \u00a3 key<\/em>[R<\/em>].\r\n\r\nSimilarly all nodes in right sub-tree of R<\/em>, will be such that key<\/em>[K<\/em>] \u00b3 key<\/em>[R<\/em>].\r\n\r\n \r\n

In other words in a BST, the value stored at the root of a sub-tree is greater<\/em> than any value in its left subtree and less<\/em> than any value in its right subtree (Figure 21.2).<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n\r\n21.3 Other properties of Binary Search Trees<\/strong>\r\n\r\n \r\n

The minimum node is identified as the leftmost node, i.e. the farthest node you can reach by following only left branches. Similarly the maximum node is identified as the rightmost node, i.e. the farthest node you can reach by following only right branches.\u00a0Hence the smallest element in a binary search tree is the <\/span>leftmost element<\/strong> and the\u00a0<\/span>.largest element is the <\/span>rightmost element<\/strong> (Figure 21.3). The same set of keys can result in different BSTs depending on the order in which the keys are inserted into the BST (Figure 21.4). The search time of a node in a tree depends on its depth. In the case of a binary search tree, the maximum depth in the skewed case with the least or the largest key at the root is N where N is the number of nodes. However the minimum depth is logN.<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n\r\n\"\"\r\n\r\n \r\n

Let us now see BST examples and examples that are not BSTs (Figure 21.5). The first example shows a BST with keys being names so here the lexicographic order is relevant while the next example shows a BST with keys being numbers and hence numeric order is followed. The third example shows a tree that is not a BST since the left sub-tree is not binary and the right sub-tree does not satisfy the binary search property.<\/p>\r\n\r\n<\/div>\r\n\"\"\r\n

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

Sometimes duplicate entries are allowed in binary search trees in which case they are always placed in the right subtree (Figure 21.6).<\/p>\r\n \r\n\r\n\"\"\r\n\r\n \r\n

Binary Search Trees data structures that can support dynamic set operations like search, minimum, maximum, predecessor, successor, insert, and delete and hence are appropriate for building dictionaries and priority queues. All the basic operations associated with binary search trees have maximum complexity of the O<\/em>(h<\/em>) where h is the height h of the tree.<\/p>\r\n \r\n\r\n21.4 Ordered Dictionaries<\/strong>\r\n\r\n \r\n

When binary search trees are used to represent dictionaries the keys are assumed to come from a total order. Remember that a total order relation satisfies the reflexive, anti-symmetric and transitive properties. Examples of total order relations include \u2264 and \u2265 for numerical order and we can define a < b if a comes before b in the lexicographic order. Some of the operations associated with the dictionary are:<\/p>\r\n \r\n\r\n\u2022\u00a0 first(): the first entry in the ordering of the dictionary\r\n\r\n\u2022\u00a0 last(): last entry in the ordering of the dictionary\r\n\r\n\u2022\u00a0 successors(k): iterator of entries with keys greater than or equal to k; where the order is increasing\r\n\r\n\u2022\u00a0 predecessors(k): iterator of entries with keys less than or equal to k where the order is decreasing\r\n\r\n \r\n\r\n21.5\u00a0 Binary Search Tree (BST) ADTs<\/strong>\r\n\r\n \r\n

The ADT for a binary search tree is similar to the ADT for a general linear list with the same operations. However searching a BST is more efficient than searching a linear list. While a general linear list uses sequential searching, BSTs use a version of binary search.<\/span><\/p>\r\n

BSTs can be implemented using either arrays or linked lists. However, linked list structures are more common and more efficient. The implementation uses nodes with two pointers, left and right with the node containing the data element (Figure 21.7)<\/span><\/p>\r\n\r\n<\/div>\r\n

\r\n\r\n\"\"\r\n\r\n \r\n

The Binary search tree is represented by a linked data structure of nodes. Here root<\/em>(T<\/em>) points to the root of tree T<\/em>. In one implementation each node contains the fields \u2013key, left<\/em> - pointer to left child, right<\/em> \u2013<\/em> pointer to right child and p<\/em> \u2013<\/em> pointer to parent. p<\/em>[root<\/em>[T]] = NIL (optional).<\/p>\r\n \r\n\r\nSome of the typical operations of the ADT binary search tree are\r\n