Lecture Notes on Binary Search Trees 15 122 Principles of Imperative Computation Frank Pfenning Lecture 17 March 17 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 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 This implies that no key occurs more than once in a tree and we have to make sure our insertion function maintains this invariant L ECTURE N OTES M ARCH 17 2010 Binary Search Trees L17 2 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 3 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 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 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 The compare function provided by the client is different from the equality function we used for hash tables For binary search trees we actually need to compare keys k1 and k2 and determine if k1 k2 k1 k2 or L ECTURE N OTES M ARCH 17 2010 Binary Search Trees L17 3 k1 k2 A standard approach to this in imperative languages is for a comparison function to return an integer r where r 0 means k1 k2 r 0 means k1 k2 and r 0 means k1 k2 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 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 1 although we will see next lecture that this is not strictly true L ECTURE N OTES M ARCH 17 2010 Binary Search Trees L17 4 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 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 Exercise 1 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 L ECTURE N OTES M ARCH 17 2010 Binary Search Trees L17 5 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 …