IntroductionThe Ordering InvariantThe InterfaceA Representation with PointersSearching for a KeyInserting an ElementChecking the Ordering InvariantThe Shape of Binary Search TreesLecture Notes onBinary Search Trees15-122: Principles of Imperative ComputationFrank PfenningLecture 17March 17, 20101 IntroductionIn the previous two lectures we have seen how to exploit the structure ofbinary trees in order to efficiently implement priority queues. A priorityqueue is an abstract type where we can insert an arbitrary element anddelete the minimal element. The O(log(n)) worst-case time for insert anddelete arose from using a balanced binary tree, which has maximal depthlog(n) + 1 for storing n elements.With binary search trees we try to obtain efficient insert and search timesfor associative arrays, which we have previously implemented as hash ta-bles. Even though the operations turn out to be quite different from thoseon priority queues, we will indeed eventually be able to achieve O(log(n))worst-case asymptotic complexity for insert and search. This also extendsto delete, although we won’t discuss that operation in lecture.2 The Ordering InvariantAt the core of binary search trees is the ordering invariant.Ordering Invariant. At any node with key k in a binary searchtree, all keys of the elements in the left subtree are strictly lessthan k, while all keys of the elements in the right subtree arestrictly greater than k.This implies that no key occurs more than once in a tree, and we have tomake sure our insertion function maintains this invariant.LECTURE NOTES MARCH 17, 2010Binary Search Trees L17.2If our binary search tree were perfectly balanced, that is, had the samenumber of nodes on the left as on the right for every subtree, then the or-dering invariant would ensure that search for an element with a given keyhas asymptotic complexity O(log(n)), where n is the number of elementsin the tree. Why? When searching for a given key k in the tree, we justcompare k with the key k0of the entry at the root. If they are equal, wehave found the entry. If k < k0we recursively search in the left subtree, andif k0< k we recursively search in the right subtree. This is just like binarysearch, except that instead of an array we traverse a tree data structure.3 The InterfaceWe assume that the client defines a type elem of elements and a type keyof keys, as well as functions to extract keys from elements and to comparekeys. Then the implementation of binary search trees will provide a typebst and functions to insert an element and to search for an element with agiven key./* Client-side interface declarations */typedef ___ key;typedef ___* elem; /* NULL must be an elem */key elem_key(elem e);int compare(key k1, key k2);/* Library-side interface declarations */typedef struct bst* bst;bst bst_new();void bst_insert(bst B, elem e) /* replace if elem with same key as x in B *///@requires e != NULL;;elem bst_search(bst B, key k); /* return NULL if not in tree */We stipulate that elem is some form of pointer type so we can return null ifno element with the given key can be found. Generally, some more opera-tions may be requested at the interface, such as the number of elements inthe tree or a function to delete an element with a given key.The compare function provided by the client is different from the equal-ity function we used for hash tables. For binary search trees, we actuallyneed to compare keys k1and k2and determine if k1< k2, k1= k2, orLECTURE NOTES MARCH 17, 2010Binary Search Trees L17.3k1> k2. A standard approach to this in imperative languages is for a com-parison function to return an integer r, where r < 0 means k1< k2, r = 0means k1= k2, and r > 0 means k1> k2.4 A Representation with PointersUnlike heaps, we cannot easily represent binary search trees with arraysand keep them balanced in the way we preserved the heap invariant. Thisis because with heaps where was a lot of flexibility where to insert newelements, while with binary search trees the position of the new elementseems rather rigidly determined1. So we will use a pointer-based imple-mentation where every node has two pointers: one to its left child and oneto its right child. A missing child is represented as NULL, so a leaf just hastwo null pointers.typedef struct tree* tree;struct tree {elem data;tree left;tree right;};As usual, we have a header which in this case just consists of a pointer to theroot of the tree. We often keep other information associated with the datastructure in these headers, such as the size.struct bst {tree root;};5 Searching for a KeyIn this lecture, we will implement insertion and search first before consid-ering the data structure invariant. This is not the usual way we proceed,but it turns out finding a good function to test the invariant is a signifi-cant challenge—meanwhile we would like to exercise programming withpointers in a tree a little. For now, we just assume we have two functions1although we will see next lecture that this is not strictly trueLECTURE NOTES MARCH 17, 2010Binary Search Trees L17.4bool is_ordtree(tree T);bool is_bst(bst B);Search is quite straightforward, implementing the informal descriptionabove. Recall that compare(k1,k2) returns −1 if k1< k2, 0 if k1= k2, and1 if k1> k2.elem tree_search(tree T, key k)//@requires is_ordtree(T);//@ensures \result == NULL || compare(elem_key(\result), k) == 0;{if (T == NULL) return NULL;int r = compare(k, elem_key(T->data));if (r == 0)return T->data;else if (r < 0)return tree_search(T->left, k);else //@assert r > 0;return tree_search(T->right, k);}elem bst_search(bst B, key k)//@requires is_bst(B);//@ensures \result == NULL || compare(elem_key(\result), k) == 0;{return tree_search(B->root, k);}We chose here a recursive implementation, following the structure of a tree,but in practice an iterative version may be preferable (see Exercise1).We can check the invariant: if T is ordered when tree_search(T) iscalled (and presumably is_bst would guarantee that), then both subtreesshould be ordered as well and the invariant is preserved.6 Inserting an ElementInserting an element is almost as simple. We just proceed as if we are look-ing for the key of the given element. If we find a node with that key, we justoverwrite its data field. If not, we insert it in the place where it would havebeen, had it been there in the first place. This last clause, however, createsLECTURE NOTES MARCH 17, 2010Binary Search Trees L17.5a small difficulty. When we hit a