TreesCLRS chapter 12.ppt

TreesCLRS: chapter 12 A hierarchical combinatorial structure Terminology ???? ???????? The dictionary problem Maintain (distinct) items with keys from a totally ordered universe subject to the following operations E.g.: 5, 19, 2, 989, 7 ( = order ) The ADT Insert(x,D) Delete(x,D) Find(x,D): Returns a pointer to x if x ? D, and a pointer to the successor or predecessor of x if x is not in D (worth to add an indicator if found or not) The ADT successor(x,D) predecessor(x,D) Min(D) (2) Max(D) (989) The ADT catenate(D1,D2) : Assume all items in D1 are smaller than all items in D2 split(x,D) : Separate to D1, D2. D1 with all items smaller than x and D2 with all items greater than x Reminder from “mavo” We have seen solutions using unordered lists and ordered lists. Worst case running time O(n) We also defined Binary Search Trees (BST) Binary search trees A representation of a set with keys from a totally ordered universe We put each element in a node of a binary tree subject to: BST BST Find(x,T) Find(5,T) Find(5,T) Find(5,T) Find(5,T) Find(5,T) Find(5,T) Find(6,T) Find(6,T) Min(T) Insert(x,T) Insert(6,T) Insert(6,T) Delete(6,T) Delete(6,T) Delete(8,T) Delete(8,T) Delete(2,T) Delete(2,T) delete(x,T) delete(x,T) delete(x,T) delete(x,T) delete(x,T) delete(x,T) delete(x,T) delete(x,T) delete(x,T) delete(x,T) Variation: Items only at the leaves Keep elements only at the leaves Each internal node contains a number to direct the search Analysis Each operation takes O(h) time, where h is the height of the tree In general h may be as large as n Want to keep the tree with small h Balance ?????? ??? ?? ?? ????? ?????? Balance successor(x,T) successor(x,T) successor(6,T) successor(x,T) successor(x,T) successor(x,T) successor(x,T) successor(x,T) 2 8 7 5 10 1 6 Switch 5 and 2 and delete the node containing now 2 If node has 2 children: take father(node) and make point to child(node) 5 8 7 10 1 6 Switch 5 and 2 and delete the node containing 5 q ←