DOC PREVIEW
CMU CS 15122 - Lecture

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Lecture Notes onBinary Search Trees15-122: Principles of Imperative ComputationTom CortinaLecture 15October 14, 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 obtainefficient insert and search times for associative arrays, which we have pre-viously implemented as hash tables. Even though the operations turn outto be quite different from those on priority queues, we will indeed even-tually be able to achieve O(log(n)) worst-case asymptotic complexity forinsert and search. This also extends to delete, although we won’t discussthat operation in lecture.2 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.bst bst_new();void bst_insert(bst B, elem x);LECTURE NOTES OCTOBER 14, 2010Binary Search Trees L15.2elem 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.3 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.We assume here that no key occurs more than once in a tree, and we haveto make sure our insertion function maintains this invariant.If 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.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.1although we will see next lecture that this is not strictly trueLECTURE NOTES OCTOBER 14, 2010Binary Search Trees L15.3typedef 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 functionsbool 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;{ 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);elsereturn tree_search(T->right, k);LECTURE NOTES OCTOBER 14, 2010Binary 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) 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, createsa small difficulty. When we hit a null pointer (which indicates the key wasnot already in the tree), we cannot just modify NULL. Instead, we return thenew 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) {LECTURE NOTES OCTOBER 14, 2010Binary Search Trees L15.5T->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 or-dered when we make recursive calls. The result should be ordered becausefor analogous reasons. The return subtree


View Full Document

CMU CS 15122 - Lecture

Download Lecture
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?