Lecture Notes for 7/19 and 7/20 Michael Brudno More Trees: ---- ------ Definition: A complete binary tree is one which is completely filled, except for possibly the bottom level, which is filled from left to right. Array Representation ----- -------------- In the previous lecture we represented Binary Trees, just like other trees with pointers. There is an alternate way, however, which will work better for "bushy" trees: To store a tree of height H allocate an array with 2^(H+1) elements. Store the root node in a[1]. Then recursively: if a parent node is stored in a[j], its two children should be a[2*j] and a[2*j+1]. This implementation works very well for complete trees because it is possible to get to parents and children without having to store explicit pointers to them. For non-complete trees this method wastes space: if our tree is actually a list, we will use up O(2^H) storage for just H nodes! Heaps ----- A heap is a binary tree where the parent is larger than all of its children (alternatively, the parent could always be smaller than the children). 10 / \ 9 8 / \ / 8.5 5 6 Insertion into a heap takes O(log n) time. Unlike BSTs, we will not always insert at a leaf. To insert 11 we place it in an empty leaf position and compare it with its parent. If it is smaller than it we are done. Otherwise we switch it with the parent and repeat the procedure. This is called percolating the node up the tree, or just percolate up. The result is: 10 10 11 / \ / \ / \ 9 8 --> 9 11 --> 9 10 / \ / \ / \ / \ / \ / \ 8.5 5 6 11 8.5 5 6 8 8.5 5 6 8 Because we start our insertions at the leafs, the tree will always remain complete. Hence insertions will always take log time. Removals also take log time, however we must be careful to maintain the heap property and the "bushiness" of the tree. In order to do this, we replace the element to be removed with its last child: To remove the 11, we replace it with the 8, and then "percolate down", or swap it with the largest of its two children until it is bigger then both: 8 10 / \ / \ 9 10 --> 9 8 / \ / / \ / 8.5 5 6 8.5 5 6 So, the obvious question you may have is how long does it take to create a heap given just an unordered array? The trivial way of doing it, by inserting all of the elements would take O(n log n) time. However we can do better! Instead of inserting, lets toss all of the elements into some arbitrary complete binary tree. Note, now, that the leaf nodes are already treaps. Looking at the nodes above those, we can restore the heap property by percolating the nodes down as necessary, than look at all nodes at level 3, etc. Note that the running time to make a heap of height v is (1) T(v) = 2*T(v-1) + (v-1) first you need to build the 2 children heaps, after which in v-1 steps you can insert the root node. Lets also define the time to make a heap of height 0 as 1: T(0) = 1. Let us show by induction that the running time T to make a heap of height v is (in the worst case) T(v) = 2^(v+1) - (v+1): base case, v = 1: 2^2 -1 = 3, 2*1+1 = 3. Inductive case: Given T(v) = 2^(v+1) - (v+1) --------------------------------- Show T(v+1) = 2^(v+2) - (v+2) From (1) T(v+1) = 2 * T(v) + v = 2 * (2^(v+1) - (v+1)) + v = 2^(v+2) - 2v - 2 + v = 2^(v+2) - (v+2). QED Since a complete tree of height H has Theta(2^H) nodes, our algorithm runs in linear time to the number of nodes in the tree. Let us now implement the algorithm using the array representation of a binary tree and that each element of our heap is an int: class Heap { int[] A; int currentSize; public Heap(int[] elems) { currentSize = elems.length; A = new int[elems.length+1]; for (int i = 0; i < elems.length; i++) A[i+1] = arg[i]; for (int i = currentSize / 2; i > 0; i-- ) percDown( i ); } private void percDown(int root) { int largest = root; int left = 2 * root; int right = 2 * root + 1; if (left <= currentSize && (A[left] > A[largest])) largest = left; if (right <= currentSize && (A[right] > A[largest])) largest = right; if (largest != root) { swap(A, index, largest); percDown(largest); } } } What makes heaps attractive? We can create a heap from n elements in O(n) time. (It would take O(n log n) time to create a BST.) To remove the top element, the time required is O(log n). Using heaps you can implement heapsort. To sort n elements, we create a heap, which takes O(n) time. Then we remove the elements one by one, which takes O(n log n) time. So the total time required for the sort is O(n + n log n) = O(n log n). The reason that heapsort is rarely used in practice is that despite a good algorithmic time it has high overhead. We can also use them to implement efficient Priority Queues: The ones you made in HW had O(n) either insertion or removal time. These are much better. We will also see more uses of heaps when we study graphs. Treaps ------ [Treaps and Tries (the next topic) are covered in Professor Hilfinger's handout "Balanced Searching", which is available from the class website.] The treap data structure will let us bring together all of the ones we have already learned. A tree is a combination of a BST & a heap, with a little bit of hashtables thrown in. Each node of a treap has a label (the element stored in the node) and a priority (gotten by applying a hash function to the label). If you look only at the label, the treap is a BST, while according to its priority it is a heap. This can be done! (L3,P100) / \ (L2, P92) (L7, P50) When inserting we just insert according to the BST property, and when done do whatever rotations are necessary to restore the heap property. To insert (L9, P64): insert first as BST rotate to restore heap property (L3,P100) (L3,P100) / \ rotate / \ (L2,P92) (L7,P50) ---> (L2,P92) (L9,P94) \ / (L9,P94) (L7,P50) Rotation is O(1) time, so insertions are still O(log n). This approach lets us have a probabilistically balanced tree: a tree which is probably going to be pretty close to balanced. Just to demonstrate, we will insert (L6, P200): after initial insert: (L3,P100) (L3,P100) (L6,P200) / \ rotate / \ rotate / \ (L2,P92) (L9,P94) --> (L2,P92) (L9,P94) 2 more (L3,P100) (L9,P94) / / times / / (L7,P50) (L6,P200) ----> (L2,P92) (L7,P50) / \ (L6, P200) (L7, P50) thus the result is more or less balanced, even if in the process we had unbalanced trees. Lets put this into code: class Treap { private int label; protected Treap left,right; protected int priority; public Treap(int label) { this.label = label; priority = someHashFunction(label); } public Treap left() { return left; } public Treap right() { return right; } public int label() { return label; } public Treap find(int l) { /* same as for BST */ } /** Performs a right rotation on this. Assumes left child non-empty. */ protected Treap rotateRight() { Treap result = left; left = left.right; result.right = this; return result; } protected Treap rotateLeft() { /* Symmetric to above */ } public Treap insert(int X) { if (X < label) { left = left.insert(X); if (left.priority > this.priority) return rotateRight(); } else { right = right.insert(X); if (right.priority > this.priority) return rotateLeft(); } return this; } Removal is somewhat trickier. We cannot just remove a node if it has two children, so we must rotate until it becomes a leaf node. Removing 6 from the treap below, we do the following (L6,P200) (L3,P100) (L3,P100) / \ / \ / \ (L3,P100) (L9,P94) --> (L2,P92) (L6,P200) --> (L2,P92) (L9,P94) / \ / / \ / \ (L2,P92) (L5,P85) (L7,P50) (L5,P85) (L9,P94) (L6,P200) (L7,P50) / / (L7,P50) (L5,P85) Once the node to be removed has only one child we can just replace it with the child. Putting this into code (assume that we already found the Treap node we wish to remove): /** Remove this node from the treap, returning the result. */ protected Treap removeMe() { if (left == null) return right; if (right == null) return left; if (left.priority < right.priority) { Treap res = rotateLeft(); // My RC is now root res.left = removeMe(); return res; } else { Treap res = rotateRight(); // My LC is now root res.right = removeMe(); return res; } } } Interestingly, the expected number of rotations per insertions is bounded by a constant: 2. With p=1/2 the node will need no rotations, with p=3/4 one or less, with p=7/8 two or less, etc. This is the geometric progression 1/2^n, the expected value of which is 2. Tries ----- How long does searching [a treap, balanced BST, sorted array] take? The answer which we have come to know is O(log n), where n is the number of elements in the array. This, however, is not strictly true. If the elements we are dealing with are ints, it is close enough, but what is they are Strings? In order to find out whether one string is >, <, or = to some other, we need to go through every character and compare those one by one. So the real answer is that it takes O(L log N), where L is the number of bytes in the longest key. Quite clearly we can't get rid of the L: we have to compare the keys no matter what else we do. What about the log N though? It turns out we can, by using something called a Trie (The name comes from reTRIEval tree, and is usually pronounced "try"). In this tree each internal node corresponds to a letter from our alphabet, and contains two or more children. The children can be either other internal nodes or Strings. Each String must have a special (unprintable) terminator, which indicates that the end of a String has been reached. I will use $$ for it. The attached figure shows a sample trie containing some set of word. To check whether some word is in the trie, we start at the root node and compare the first character to the children of the root. If such a child exists, we repeat the procedure with the 2nd char and the child. If at some point we reach a String node, we check if it matches the remaining part of the String, and if so return true. If we get to the end of our string and we are not at a String node, we need to check if the node we are at has a child corresponding to $$, and if so we will return true. (This is necessary if one String is a substring of another: "a" and "abate"). In order to insert we go through a similar procedure, but as soon as we find a node where the child corresponding to the word to be inserted in null, we insert the remaining part of the word into the cell. If while doing the insertion we find a String node, we find the longest common prefix we have with that String and make nodes for each letter in that prefix, after which we should re-insert both the other String and our original word. This is hard to put in words. Trace through the algorithms in your heada and insert more words into the attached tries in order to make sure you get this! The actual code is in Hilfinger's handout. Trie Implementation ---- -------------- If our alphabet is small (a few letters) we can use the regular representation of the tree, and when doing lookups or insertions check all of the children for equality to the current letter. It should be clear, however, that doing this even with the 128 ASCII chars, at every level, would be time consuming. So instead we will borrow an idea from HW1 and use an array of children so that it is easy to get to any particular one. There will be a memory overhead, but it will be at most a factor of the size of the alphabet. In order to find the child corresponding to the letter 'a' we will just get children['a']: constant time! Consequently our lookups (and insertions will be O(L)). More complicated representations exist which will save you some space by giving up time. Once again, I point you to Prof. Hilfinger's notes for these details.