DOC PREVIEW
UMD CMSC 420 - Binary Search Trees

This preview shows page 1-2-3-27-28-29 out of 29 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 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 29 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 29 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 29 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 29 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 29 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Binary Search TreesCMSC 420: Lecture 6Binary Tree TraversalsHI JD E FBGCAinorder:! HDIBEAJFCGpreorder:! ABEHIECFJGpostorder:! HIDEBJFGCAvoid traverse(BinNode *T) { if(T != NULL) { PREORDER(T); traverse(T->left()); INORDER(T); traverse(T->right()); POSTORDER(T); }}How much space is used?Threaded Trees•Traversals:-Require extra memory, and-Must be started from the root•Use NULL pointers to store in-order predecessors and successors.•Extra bit associated with each pointer marks whether it is a thread.EGDEBAHGThreaded TreesEGDEBAHGvoid inorder_succ(BinNode *T) { BinNode * next = T->right(); if(!next) return NULL; if(!is_thread(T->right)) { while(next->left() && is_thread(next->left) ) next = next->left(); } return next;}r1r2rIn general, in order successor = leftmost item in right subtreeUsing Threads for PreorderEGDEBAHGvoid preorder_succ(BinNode *T) { if(T->left() && !is_thread(T->left) return T->left(); for(BinNode* next = T->right(); is_thread(next->right); next = next->right()) {} return RC(P);}preorder_succ(H) = right child of the lowest ancestor of H that both has H in its left subtree and has a right child.Walk up right threadsReturn right childSerializing Trees•Often want to write trees out to disk in a space efficient way.•Preorder traversal will let you store the nodes.-What’s the preorder traversal of this tree?•Need to encode the structure somehow.EHDFBAGCSerializing Trees•In preorder traversal, output a mark when you finish processing a node’s children.•Leaves = empty children lists: ∅•∅ symbols are redundant:-ABE))C)D)F)G)H))•“)” means “go up one level”.EHDFBAG∅ ∅ ∅∅∅A B E ∅ ) ) D F ∅ ) G ∅ ) H ∅ ) ) C ∅ ) )Cb d ae f g h cBinary Search Trees•BST Property: If a node has key k then keys in the left subtree are < k and keys in the right subtree are > k.•We disallow duplicate keys.•Generalization of the binary search process we saw before:-ordering-partitioning-linking•Good for implementing the dictionary ADT we’ve already seen: insert, delete, find.211863594Sorted Set Problem•If keys are totally ordered, dictionary ADT is sometimes extended to a “sorted set ADT.” -Totally ordered means: for every pair (a,b) either a < b or b < a).-Operations:• s = make_sorted_set• find(s, k)• insert(s, k)• delete(s, k)• join(s1, k, s2): make a new sorted set from s1, {k}, s2; destroy s1 and s2. Assumes every item in s1 < k and k < every time in s1.• split(s, k): return 3 new sorted sets: s1 with items < k, {k}, and s2 with items > k.Dictionary operationsBST Find211863594Find k = 6:Is k < 8?Is k < 5? No, go rightYes, go leftBST Find211863594Find k = 9:Is k < 8?Is k < 5? No, go rightYes, go leftNo, go rightIs k < 11?BST Find211863594Find k = 13:Is k < 8?Is k < 5? No, go rightNo, go rightIs k < 11?NULLNo, go rightinsert(T, K): q = NULL p = T while p != NULL and p.key != K: q = p if p.key < K: p = p.left else if p.key > K: p = p.right if p != NULL: error DUPLICATE N = new Node(K) if q.data > K: q.left = N else: q.right = NBST Insert11863594NULL2qpqpqpSame idea as BST Findinsert(T, K): if T == NULL: T = new_node(K) T.left = new_external_node() T.right = new_external_node() else p = T while p.key != K and p.left != NULL: if p.key < K: p = p.left else if p.key > K: p = p.right if p.left != NULL: error DUPLICATE p.key = K p.left = new_external_node() p.right = new_external_node()BST Insert with Extended Binary Trees1186359421BST FindMin21186354Walk left until you can’t go left any moreCan you express inorder_successor using find_min?11186453BST Delete23562354 235Node is leaf: Node has 1 child:23552423564Node has 2 children:Python Implementation of BSTHow would you implement join and split?Split(G)GBACabcDdEeFfghghs1s2Gi=Ffjoin(s2,F,f)Eejoin(s2, E, e)Cjoin(s2, C, c) cAajoin(a, A, s1)Bbjoin(b, B, s1)Ddjoin(d, D, s1)Letters represent labels not keys•What’s the worst possible insertion order?•What’s the best possible insertion order?Expected Path Length of Random BST•Suppose the keys k1, k2, k3, ..., kn are inserted in a random order (every permutation equally likely).•What is the expected path length to a node in the BST built by inserting these keys?•Idea: consider the leftmost path as a representative path.•New key ki added to left-most path when it is the smallest encountered so far (ki < kj for j < i).•In a random permutation, how often does the minimum change? [This is the length of the leftmost path]Expected Path Length of Random BST•What’s the probability that ki is the smallest so far?•Pr[ki is smallest among k1,...ki] = 1/i•Why?•In a random permutation of k1,...ki, the minimum is equally likely to be in any one of the i positions. •Probability it is in the last position = 1/i.k1, k2, k3, k4, k5, k6, k7, k8Expected Path Length of Random BST•sum of xi = length of leftmost path.•Expected length = E[∑xi] = ∑E[xi] ! = ∑[(1/i)1 + 0(1-1/i)]! = ∑(1/i) = Hn = O(log n)k1, k2, k3, k4, k5, k6, k7, k8 x1, x2, x3, x4, x5, x6, x7, x8 xi = 1 if ki is smallest among k1,...,ki! 0 otherwisekeys = random variables =Expected Path Length of Random BST(Dave Mount’s Figure)Optimal Static BSTs –!Cost of trees•Define the cost of a tree built on keys kj,...,km:•T is optimal if C(T) is smallest among any possible T containing the same keys.•C(T) = expected cost of searching for a key in T.C(T) = ∑ pi(Depth(T, ki) + 1)i = jmk1, k2, k3, k4, k5, k6, k7, k8 p1, p2, p3, p4, p5, p6, p7, p8 Why is it Depth + 1?Subtrees of optimal tree are optimal trees•Goal: find tree that minimizes C(T).•Claim: every subtree of optimal tree is optimal.•Proof: Let T be an optimal tree on kj,...,km, with root = kr (j ≤ r ≤ m)C(T) = pr + ∑pi(Depth(T, ki) + 1) + ∑pi(Depth(T, ki) + 1)C(Tleft)C(Tright)i=jr-1i=r+1m∑pi + ∑piDepth(T, ki) i=jr-1i=jr-1∑pi + ∑piDepth(T, ki) i=jr-1i=jr-1C(T) = ∑pi + C(Tleft) + C(Tright)i=jmSo,•If there were a lower cost Tleft or Tright we could reduce the total cost of T, contradicting that T is optimal. •Hence, Tleft and Tright must be optimal.C(T) = ∑pi + C(Tleft) + C(Tright)i=jmDynamic Programming to Find OPT Tree k2, k3, k4, k5, k6, k7, k8 C[j, m] = 0! if m < j (tree is empty)pj! if j = m (tree is single node)∑pi + min { C[j, r-1] + C[r+1, m]}! if j < mri=jmjmrSo: if you


View Full Document

UMD CMSC 420 - Binary Search Trees

Download Binary Search Trees
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 Binary Search Trees 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 Binary Search Trees 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?