Lecture Notes on Binary Search Trees 15 122 Principles of Imperative Computation Tom Cortina Lecture 15 October 14 2010 1 Introduction In the previous two lectures we have seen how to exploit the structure of binary trees in order to efficiently implement priority queues A priority queue is an abstract type where we can insert an arbitrary element and delete the minimal element The O log n worst case time for insert and delete arose from using a balanced binary tree which has maximal depth log n 1 for storing n elements With binary search trees we try to obtain efficient insert and search times for associative arrays which we have previously implemented as hash tables Even though the operations turn out to be quite different from those on priority queues we will indeed eventually be able to achieve O log n worst case asymptotic complexity for insert and search This also extends to delete although we won t discuss that operation in lecture 2 The Interface We assume that the client defines a type elem of elements and a type key of keys as well as functions to extract keys from elements and to compare keys Then the implementation of binary search trees will provide a type bst and functions to insert an element and to search for an element with a given key bst bst new void bst insert bst B elem x L ECTURE N OTES O CTOBER 14 2010 Binary Search Trees elem bst search bst B key k L15 2 return NULL if not in tree We stipulate that elem is some form of pointer type so we can return null if no element with the given key can be found Generally some more operations may be requested at the interface such as the number of elements in the tree or a function to delete an element with a given key 3 The Ordering Invariant At the core of binary search trees is the ordering invariant Ordering Invariant At any node with key k in a binary search tree all keys of the elements in the left subtree are strictly less than k while all keys of the elements in the right subtree are strictly greater than k We assume here that no key occurs more than once in a tree and we have to make sure our insertion function maintains this invariant If our binary search tree were perfectly balanced that is had the same number of nodes on the left as on the right for every subtree then the ordering invariant would ensure that search for an element with a given key has asymptotic complexity O log n where n is the number of elements in the tree Why When searching for a given key k in the tree we just compare k with the key k 0 of the entry at the root If they are equal we have found the entry If k k 0 we recursively search in the left subtree and if k 0 k we recursively search in the right subtree This is just like binary search except that instead of an array we traverse a tree data structure 4 A Representation with Pointers Unlike heaps we cannot easily represent binary search trees with arrays and keep them balanced in the way we preserved the heap invariant This is because with heaps where was a lot of flexibility where to insert new elements while with binary search trees the position of the new element seems rather rigidly determined1 So we will use a pointer based implementation where every node has two pointers one to its left child and one to its right child A missing child is represented as NULL so a leaf just has two null pointers 1 although we will see next lecture that this is not strictly true L ECTURE N OTES O CTOBER 14 2010 Binary Search Trees L15 3 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 the root of the tree We often keep other information associated with the data structure in these headers such as the size struct bst tree root 5 Searching for a Key In this lecture we will implement insertion and search first before considering 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 significant challenge meanwhile we would like to exercise programming with pointers in a tree a little For now we just assume we have two functions bool is ordtree tree T bool is bst bst B Search is quite straightforward implementing the informal description above Recall that compare k1 k2 returns 1 if k1 k2 0 if k1 k2 and 1 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 key kt elem key T data if compare k kt 0 return T data else if compare k kt 0 return tree search T left k else return tree search T right k L ECTURE N OTES O CTOBER 14 2010 Binary Search Trees L15 4 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 Exercise We can check the invariant if T is ordered when tree search T is called and presumably is bst would guarantee that then both subtrees should be ordered as well and the invariant is preserved 6 Inserting an Element Inserting an element is almost as simple We just proceed as if we are looking for the key of the given element If we find a node with that key we just overwrite its data field If not we insert it in the place where it would have been had it been there in the first place This last clause however creates a small difficulty When we hit a null pointer which indicates the key was not already in the tree we cannot just modify NULL Instead we return the new tree so that the parent can modify itself tree tree insert tree T elem x requires is ordtree T ensures is ordtree T ensures tree search result elem key x NULL if T NULL create new node T alloc struct tree T data x T left NULL T right NULL else key kt elem key T data key k elem key x if compare k kt 0 T data x else if compare k kt 0 L ECTURE N OTES O CTOBER 14 2010 Binary Search Trees L15 5 T left tree insert T left x else assert compare k kt 0 T right tree insert T right x return T For the same reason as in tree search we expect the subtrees to be ordered when we make recursive calls The result should …