Princeton University • COS 226 • Algorithms and Data Structures • Spring 2004 • Kevin Wayne • http://www.Princeton.EDU/~cos226Balanced TreesReference: Chapter 13, Algorithms in Java, 3rdEdition, Robert Sedgewick.Splay trees2-3-4 treesRed-black treesB-trees2Symbol Table ReviewSymbol table: key-value pair abstraction.n Insert a value with specified key.n Search for value given key.n Delete value with given key.Randomized BST.n log N time per op (unless you get ridiculously unlucky).n Store subtree count in each node.n Generate random numbers for each insert/delete op.This lecture.n Splay trees.n 2-3-4 trees.n Red-black trees.n B-trees.3Splay TreesSplay trees = self-adjusting BST.n Tree automatically reorganizes itself after each op.n After inserting x or searching for x, rotate x up to root using double rotations.n Tree remains "balanced" without explicitly storing any balance information.Amortized guarantee: any sequence of N ops takes O(N log N) time.n Height of tree can be N.n Individual op can take linear time.4Splay TreesSplay.n Check two links above current node.n ZIG-ZAG: if orientations differ, same as root insertion.n ZIG-ZIG: if orientations match, do top rotation first.ZIG-ZAGB CyDzxDCzyABAx5Splay TreesSplay.n Check two links above current node.n ZIG-ZAG: if orientations differ, same as root insertion.n ZIG-ZIG: if orientations match, do top rotation first.ZIG-ZIGA BxCyDzDCzByAxZAG-ZAG6Splay TreesSplay.n Check two links above current node.n ZIG-ZAG: if orientations differ, same as root insertion.n ZIG-ZIG: if orientations match, do top rotation first.Root = Splay Root InsertionSplay Insertion7Splay ExampleSearch for 1.10987654321ZIG-ZIG8Splay ExampleSearch for 1.10987654123ZIG-ZIG9Splay ExampleSearch for 1.10987612345ZIG-ZIG10Splay ExampleSearch for 1.10981672345ZIG-ZIG11Splay ExampleSearch for 1.ZIG1018967234512Splay ExampleSearch for 1.1108967234513Splay ExampleSearch for 2.110896723452846310195 7Splay(2)14Splay TreesIntuition.n Splay rotations halve search path.n Reduces length of path for many other nodes in tree.insert 1, 2, …, 40search 1search 2search 3search 4insert 1, 2, …, 40search for random key15Symbol Table: Implementations Cost SummarySplay: sequence of any N ops in O(N log N) time. Ahead: Can we do all ops in log N time guaranteed?* assumes we know location of node to be deleted† if delete allowed, insert/search become sqrt(N)‡ probabilistic guarantee§ amortized guaranteeSorted arrayImplementationUnsorted listBSTRandomized BSTSplaylog NSearchNNlog N ‡log N §NInsert1Nlog N ‡log N §log NSearchNlog Nlog Nlog N §NInsert1log Nlog Nlog N §NDelete1sqrt(N) †log Nlog N §Worst Case Average CaseNDelete1Nlog N ‡log N §Hashing N 1 1* 1* 1*N162-3-4 Trees2-3-4 tree.n Scheme to keep tree balanced.n Generalize node to allow multiple keys.Allow 1, 2, or 3 keys per node.n 2-node: one key, two children.n 3-node: two keys, three children.n 4-node: three keys, four children.H I NF RUA C Ek £ FF £ k £ R R £ k172-3-4 Trees: Search and InsertSEARCH.n Compare search key against keys in node.n Find interval containing search key.n Follow associated link (recursively).INSERT.n Search to bottom for key.n 2-node at bottom: convert to 3-node.n 3-node at bottom: convert to 4-node.n 4-node at bottom: ??H I NF RUA C Ek £ FF £ k £ R R £ k182-3-4 Trees: Splitting Four NodesTransform tree on the way DOWN.n Ensure that last node is not a 4-node.Local transformation to split 4-nodes:Invariant: current node is not a 4-node.n One of two above transformations must apply at next node.n Insertion at bottom is easy since it's not a 4-node.192-3-4 Trees: Splitting a Four NodeSplitting a four node: move middle key up.A-CK Q WDE-J L-P R-V X-ZA-CKD QE-J L-P R-V X-ZW202-3-4 TreesTree grows up from the bottom.EAPEXML21Balance in 2-3-4 TreesAll paths from top to bottom have exactly the same length.Tree height.n Worst case: lg N all 2-nodesn Best case: log4 N = 1/2 lg N all 4-nodesn Between 10 and 20 for a million nodes.n Between 15 and 30 for a billion nodes.Comparison within nodes not accounted for.222-3-4 Trees: Implementation?Direct implementation complicated because of:n Maintaining multiple node types.n Implementation of getChild.n Large number of cases for split.private Node insert(Node h, String key, Object value) {Node x = h;while (x != null) {x = x.getChild(key);if (x.is4Node()) x.split();}if (x.is2Node()) x.make3Node(key, value);else if (x.is3Node()) x.make4Node(key, value);}Fantasy Code23Red-Black TreesRepresent 2-3-4 trees as binary trees.n Use "internal" edges for 3- and 4- nodes.n Correspondence between 2-3-4 trees and red-black trees.n Not 1-1 because 3-nodes swing either way.red24Splitting Nodes in Red-Black TreesTwo cases are easy: switch colors.Two cases require rotations.do single rotationdo double rotation25Red-Black Tree Node Split Exampleright rotate R ®left rotate E ®change colorsinserting G26Red-Black Tree ConstructionEAPEXML27Balance in Red-Black TreesLength of longest path is at most twice the length of shortest path.Tree height.n Worst case: 2 lg N.Comparison within nodes ARE counted.28Symbol Table: Implementations Cost Summary* assumes hash map is random for all keys† if delete allowed, insert/search become sqrt(N)‡ probabilistic guarantee§ amortized guaranteeSorted arrayImplementationUnsorted listBSTRandomized BSTSplaylog NSearchNNlog N ‡log N §NInsert1Nlog N ‡log N §log NSearchNlog Nlog Nlog N §NInsert1log Nlog Nlog N §NDelete1sqrt(N) †log Nlog N §Worst Case Average CaseRed-Black log N log N log N log N log NNDelete1Nlog N ‡log N §log NHashing N 1 1* 1* 1*N29Red-Black Trees in PracticeRed-black trees vs. splay trees.n Fewer rotations than splay trees.n One extra bit per node for color.Red-black trees vs. hashing.n Hashing code is simpler and usually faster.n Arithmetic to compute hash vs. comparison.n Hashing performance guarantee is weaker.n BSTs have more flexibility and can support wider range of ops.Red-black trees are widely used as system symbol tables.n Java: TreeMap, TreeSet.n C++ STL: map, multimap, multiset.possible to eliminate30Symbol Table: Java LibrariesJava has built-in library for red-black tree symbol table.n TreeMap = red-black tree implementation.Duplicate policy.n Java TreeMap forbids two elements with the same key.n Sedgewick implementations allows duplicate keys.import java.util.TreeMap;public class TreeMapDemo {public static
View Full Document
Unlocking...