1、Ch. 13: Balanced Search Trees,Symbol table: insert, delete, find, pred, succ, sort, Binary Search Tree review: What is a BST? binary tree with a key at each node for any node, the keys in the left subtree are less than the key of the current node, and those in the right subtree greater How do you im
2、plement these operations in a BST? find insert delete pred What is the average runtime of each operation? What is the worst case?,Balanced Search Trees (Ch. 13),To implement a symbol table, Binary Search Trees work pretty well, exceptthe worst case is O(n) and it is embarassingly likely to happen in
3、 practice if the keys are sorted, or there are lots of duplicates, or various kinds of structure Ideally we would want to keep a search tree perfectly balanced, like a heap How can we insert or delete in O(log n) time and re-balance the whole tree?,234 Intro,234 Trees are are worst-case optimal: Q(l
4、og n) per operation Idea: nodes have 1, 2, or 3 keys and 2, 3, or 4 links. Subtrees have keys ordered analogously to a binary search tree. A balanced 234 search tree has all leaves at the same level. How would search work? How would insertion work? split nodes on the way back up? or split 4-nodes on
5、 the way down?,Top-down vs. Bottom-up,Top-down 2-3-4 trees split nodes on the way down. But splitting a node means pushing a key back up, and it may have to be pushed all the way back up to the root. Its easier to split any 4-node on the way down.,2-node with 4-node child: split into 3-node with two
6、 2-node children3-node with 4-node child: split into 4-node with two 2-node childrenThus, all searches end up at a node with space for insertion,Construction Example,234 Balance,All paths from the top to the bottom are the same heightWhat is that height?worst case: lgN (all 2-nodes)best case: lgN/2
7、(all 4-nodes) height 10-20 for a million nodes; 15-30 for a billionOptimal! (But is it fast?),Implementation Details,Actually, there are many 234-tree variants: splitting on the way up vs. down 2-3 vs. 2-3-4 trees Implementation is complicated because of the large number of cases that have to be con
8、sidered. What would happen if we used even more children of each node? (B-Trees) Can we improve the optimal balanced-tree approach, for fewer cases and strictly binary nodes? (Red-black Trees),B-Trees,What about using even more keys? B-trees Like a 234 tree, but with many keys, say b=100 or 500 Usua
9、lly enough keys to fill a 4k or 16k disk block Time to find an item: O(logbn) E.g. b=500: can locate an item in 500 with one disk access, 250,000 with 2, 125,000,000 with 3Used for database indexes, disk directory structures, etc., where the tree is too large for memory and each step is a disk acces
10、s. Drawback: wasted space,Red-Black Trees,Idea: Do something like a 2-3-4 Tree, but using binary nodes only,The correspondence it not 1-1 because 3-nodes can swing either way Add a bit per node to mark as Red or Black Black links bind together the 2-3-4 tree; red links bind the small binary trees ho
11、lding 2, 3, or 4 nodes. (Red nodes are drawn with thick links to them.) Two red nodes in a row are not needed (or allowed),Red-Black Tree Example,This tree is the same as the 2-3-4 tree built a few slides back, with the letters “ASEARCHINGEXAMPLE” Notice that it is quite well balanced.(How well?)(We
12、ll see in a moment.),RB-Tree Insertion,How do we search in a RB-tree? How do we insert into a RB-tree? normal BST insert; new node is red How do we perform splits? Two cases are easy: just change colors!,RB-Tree Insertion 2,Two cases require rotations:,Two adjacent red nodes not allowed! If the 4-no
13、de is on an outside link, a single rotation is needed If the 4-node is on the center link, double rotation If the root becomes red, make it black. (Tree grows!),RB-Tree Split,We can use the red-black abstraction directly No two red nodes should be adjacent If they become adjacent, rotate a red node
14、up the tree (In this case, a double rotation makes I the root) Repeat at the parent node There are 4 cases Details a bit messy: leave to STL!,Red-Black Tree Insertion,link RBinsert(link h, Item item, int sw) Key v = key(item);if (h = z) return NEW(item, z, z, 1, 1);if (hl-red) ,RB Tree Construction,
15、Red-Black Tree Summary,RB-Trees are BSTs with addl properties: Each node (or link to it) is marked either red or black Two red nodes are never connected as parent and child All paths from the root to a leaf have the same black-length How close to being balanced are these trees? According to black no
16、des: perfectly balanced Red nodes add at most one extra link between black nodes Height is therefore at most 2 log n.,Comparisons,There are several other balanced-tree schemes, e.g. AVL trees Generally, these are BSTs, with some rotations thrown in to maintain balance Let STL handle implementation d
17、etails for youBuild Tree Search MissesN BST RBST Splay RB Tree BST RBST Splay RB5000 4 14 8 5 3 3 3 250000 63 220 117 74 48 60 46 36 200000 347 996 636 411 235 294 247 193,Summary,Goal: Symbol table implementation O(log n) per operationRB-Tree: O(log n) worst-caseBalanced-tree algorithms are variati
18、ons on a theme: rotate during insertion or search to improve balanceThink balanced tree when you have a set of objects and you need order operations,STL Containers using RB trees,set: container for unique items Member functions: insert() erase() find() count() lower_bound() upper_bound() iterators to move through the set in ordermultiset: like set, but items can be repeated,
