Algorithms, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2002–2012·March 4, 2012 1:33:02 PMAlgorithmsFOUR T H EDIT IONR O B E R T S EDG EWICK K EVIN W A Y N E3.3 BALANCED SEARCH TREES‣2-3 search trees‣red-black BSTs‣B-trees2Symbol table reviewChallenge. Guarantee performance.This lecture. 2-3 trees, left-leaning red-black BSTs, B-trees.introduced to the worldin COS 226, Fall 2007implementationworst-case cost(after N inserts) worst-case cost(after N inserts) worst-case cost(after N inserts) average case(after N random inserts)average case(after N random inserts)average case(after N random inserts)orderedkeyimplementationsearchinsertdeletesearch hitinsertdeleteiteration?interfacesequential search(unordered list)NNNN/2NN/2noequals()binary search(ordered array)lg NNNlg NN/2N/2yescompareTo()BSTNNN1.39 lg N1.39 lg N?yescompareTo()goallog Nlog Nlog Nlog Nlog Nlog NyescompareTo()3‣2-3 search trees‣red-black BSTs‣B-treesAllow 1 or 2 keys per node.•2-node: one key, two children.•3-node: two keys, three children.Symmetric order. Inorder traversal yields keys in ascending order.Perfect balance. Every path from root to null link has same length.2-3 tree4between E and Jlarger than Jsmaller than ES XA C PHRML3-nodeEJ2-nodenull link52-3 tree demo6Local transformations in a 2-3 treeSplitting a 4-node is a local transformation: constant number of operations.b c da ebetweena and blessthan abetweenb and cbetweend and egreaterthan ebetweenc and dbetweena and blessthan abetweenb and cbetweend and egreaterthan ebetweenc and db da c eSplitting a 4-node is a local transformation that preserves balance Invariants. Maintains symmetric order and perfect balance.Pf. Each transformation maintains symmetric order and perfect balance.7Global properties in a 2-3 treebrightmiddleleftrightleftbdb c da caa b cdcab da b ccarootparent is a 2-nodeparent is a 3-nodeSplitting a temporary 4-node in a 2-3 tree (summary) cebdc d ea bb c da ea b da c ea b cd ecab d e82-3 tree: performancePerfect balance. Every path from root to null link has same length.Tree height.•Worst case:•Best case:Typical 2-3 tree built from random keys92-3 tree: performancePerfect balance. Every path from root to null link has same length.Tree height.•Worst case: lg N. [all 2-nodes]•Best case: log3 N ≈ .631 lg N. [all 3-nodes]•Between 12 and 20 for a million nodes.•Between 18 and 30 for a billion nodes.Guaranteed logarithmic performance for search and insert.Typical 2-3 tree built from random keysST implementations: summary10constants depend upon implementationimplementationworst-case cost(after N inserts) worst-case cost(after N inserts) worst-case cost(after N inserts) average case(after N random inserts)average case(after N random inserts)average case(after N random inserts)orderedkeyimplementationsearchinsertdeletesearch hitinsertdeleteiteration?interfacesequential search(unordered list)NNNN/2NN/2noequals()binary search(ordered array)lg NNNlg NN/2N/2yescompareTo()BSTNNN1.39 lg N1.39 lg N?yescompareTo()2-3 treec lg Nc lg Nc lg Nc lg Nc lg Nc lg NyescompareTo()112-3 tree: implementation?Direct implementation is complicated, because:•Maintaining multiple node types is cumbersome.•Need multiple compares to move down tree.•Need to move back up the tree to split 4-nodes.•Large number of cases for splitting.Bottom line. Could do it, but there's a better way.12‣2-3 search trees‣red-black BSTs‣B-trees1. Represent 2–3 tree as a BST.2. Use "internal" left-leaning links as "glue" for 3–nodes.13Left-leaning red-black BSTs (Guibas-Sedgewick 1979 and Sedgewick 2007)larger key is rootEncoding a 3-node with two 2-nodes connected by a left-leaning red linka b3-nodebetweena and blessthan agreaterthan babbetweena and blessthan agreaterthan bEncoding a 3-node with two 2-nodes connected by a left-leaning red linka b3-nodebetweena and blessthan agreaterthan babbetweena and blessthan agreaterthan b1−1 correspondence between red-black and 2-3 treesXSHPJREAMCLXSHPJREAMCLred−black treehorizontal red links2-3 treeE JH LMRPS XA C1−1 correspondence between red-black and 2-3 treesXSHPJREAMCLXSHPJREAMCLred−black treehorizontal red links2-3 treeE JH LMRPS XA Cblack links connect2-nodes and 3-nodesred links "glue" nodes within a 3-node2-3 tree corresponding red-black BSTA BST such that:•No node has two red links connected to it.•Every path from root to null link has the same number of black links.•Red links lean left.14An equivalent definition"perfect black balance"1−1 correspondence between red-black and 2-3 treesXSHPJREAMCLXSHPJREAMCLred−black treehorizontal red links2-3 treeE JH LMRPS XA CKey property. 1–1 correspondence between 2–3 and LLRB.15Left-leaning red-black BSTs: 1-1 correspondence with 2-3 trees1−1 correspondence between red-black and 2-3 treesXSHPJREAMCLXSHPJREAMCLred−black treehorizontal red links2-3 treeE JH LMRPS XA CSearch implementation for red-black BSTsObservation. Search is the same as for elementary BST (ignore color).Remark. Most other ops (e.g., ceiling, selection, iteration) are also identical.16public Val get(Key key){ Node x = root; while (x != null) { int cmp = key.compareTo(x.key); if (cmp < 0) x = x.left; else if (cmp > 0) x = x.right; else if (cmp == 0) return x.val; } return null;}but runs faster because of better balance1−1 correspondence between red-black and 2-3 treesXSHPJREAMCLXSHPJREAMCLred−black treehorizontal red links2-3 treeE JH LMRPS XA CRed-black BST representationEach node is pointed to by precisely one link (from its parent) ⇒can encode color of links in nodes.17 private static final boolean RED = true; private static final boolean BLACK = false; private class Node { Key key; Value val; Node left, right; boolean color; // color of parent link } private boolean isRed(Node x) { if (x == null) return false; return x.color == RED; }null links are blackprivate static final boolean RED = true;private static final boolean BLACK = false;private class Node{ Key key; // key Value val; // associated data Node left, right; // subtrees int N; // # nodes in this subtree boolean color; // color of link from // parent to this node Node(Key key, Value val) { this.key = key; this.val = val; this.N = 1; this.color = RED; }}private boolean isRed(Node x){ if (x ==
View Full Document
Unlocking...