4.4 Balanced Trees 2-3-4 Trees
Symbol Table Review4.4 Balanced TreesSymbol table: key-value pair abstraction.Insert a value with specified key.Search for value given key.Delete value with given key.!!!Randomized BST.O(log N) time per op. [unless you get ridiculously unlucky]Store subtree count in each node.Generate random numbers for each insert/delete op.!!!This lecture. 2-3-4 trees, red-black trees, B-trees.Reference: Chapter 13, Algorithms in Java, 3rd Edition, Robert Sedgewick.Robert Sedgewick and Kevin Wayne Copyright 2006 http://www.Princeton.EDU/ cos22622-3-4 Tree2-3-4 Trees2-3-4 tree. Generalize node to allow multiple keys; keep tree balanced.Perfect balance. Every path from root to leaf has same length.Allow 1, 2, or 3 keys per node.2-node: one key, two children.3-node: two keys, three children.4-node: three keys, four children.!!!K R KK—RC EARobert Sedgewick and Kevin Wayne Copyright 2006 http://www.Princeton.EDU/ cos226D RM OF G JLNWQS VY Z4
2-3-4 Tree: Search2-3-4 Tree: InsertSearch.Compare search key against keys in node.Find interval containing search key.Follow associated link (recursively).Insert.Search to bottom for key.2-node at bottom: convert to 3-node.3-node at bottom: convert to 4-node.4-node at bottom: ?!!!!!!!K R KK —RC EADK R RM OF G JLN KWQS VK—RC EY ZAD RM OF G JLNWQS VY Z562-3-4 Tree: Splitting Four Nodes2-3-4 Tree: Splitting a Four NodeTransform tree on the way down.Ensures last node is not a 4-node.Local transformation to split 4-nodes:Ex. To split a four node, move middle key up.!!DD QK Q WKInvariant. Current node is not a 4-node.Consequence. Insertion at bottom is easy since it's not a 4-node.E-J7WA-CA-CL-PR-VX-ZE-JL-PR-VX-Z8
2-3-4 Tree2-3-4 Tree: BalanceTree grows up from the bottom.Property. All paths from root to leaf have same length.EXATree height.Worst case: lg N[all 2-nodes]Best case:log4 N 1/2 lg N [all 4-nodes]Between 10 and 20 for a million nodes.Between 15 and 30 for a billion nodes.!M!P!!LE92-3-4 Tree: Implementation?10Symbol Table: Implementations Cost SummaryDirect implementation. Complicated because of:Maintaining multiple node types.Implementation of getChild().Large number of cases for split().Worst Case!!!private void insert(Key key, Val val) {Node x root;while (x.getChild(key) ! null) {x x.getChild(key);if (x.is4Node()) x.split();}if(x.is2Node()) x.make3Node(key, val);else if (x.is3Node()) x.make4Node(key, val);}Average leteSorted arraylog NNNlog NNNUnsorted listN11N11HashingN1NBSTNNN1*log NRandomized BSTlog N‡log N‡log N‡Splaylog N§log N§log N§2-3-4log Nlog Nlog N1*†log Nlog N§log N*†‡§fantasy codelog N1*†log Nlog N§log Nlog N†log Nlog N§log Nassumes hash map is random for all keysN is the number of nodes ever insertedprobabilistic guaranteeamortized guaranteeNote. Comparison within nodes not accounted for.1112
Red-Black TreeRed-Black TreesRepresent 2-3-4 tree as a BST.Use "internal" edges for 3- and 4- nodes.!red gluenot 1-1 because 3-nodes swing either way.!Correspondence between 2-3-4 trees and red-black trees.Robert Sedgewick and Kevin Wayne Copyright 2006 http://www.Princeton.EDU/ cos22614Red-Black Tree: Splitting NodesRed-Black Tree: Splitting NodesTwo easy cases. Switch colors.Two easy cases. Switch colors.Two hard cases. Use rotations.do single rotationdo double rotation1516
Red-Black Tree: Splitting NodesRed-Black Tree: Insertioninserting GEchange colorsXAMPLEright rotate R !left rotate E !17Red-Black Tree: Balance18Symbol Table: Implementations Cost SummaryProperty A. Every path from root to leaf has same number of black links.Worst CaseProperty B. At most one red link in-a-row.Property C. Height of tree is less than 2 lg N 2.Average leteSorted arraylog NNNlog NNNUnsorted listN11N11HashingN1NBSTNNN1*log NRandomized BSTlog N‡log N‡log N‡Splaylog N§log N§log N§Red-Blacklog Nlog Nlog N1*†log Nlog N§log N*†‡§log N1*†log Nlog N§log Nlog N†log Nlog N§log Nassumes hash map is random for all keysN is the number of nodes ever insertedprobabilistic guaranteeamortized guaranteeNote. Comparison within nodes are accounted for.1920
Red-Black Trees: PracticeRed-black trees vs. splay trees.Fewer rotations than splay trees.One extra bit per node for color.!B-Treesat most 2 per insertionpossible to eliminate!Red-black trees vs. hashing.Hashing code is simpler and usually faster:arithmetic to compute hash vs. comparison.Hashing performance guarantee is weaker.BSTs have more flexibility and can support wider range of ops.!!!In the wild. Red-black trees are widely used as system symbol tables.Java: java.util.TreeMap, java.util.TreeSet.C STL: map, multimap, multiset.Linux kernel: linux/rbtree.h.!!!Robert Sedgewick and Kevin Wayne Copyright 2006 http://www.Princeton.EDU/ cos22621B-TreeB-Tree ExampleB-Tree. Generalizes 2-3-4 trees by allowing up to M links per node.Main application: file systems.Reading a page into memory from disk is expensive.Accessing info on a page in memory is free.Goal: minimize # page accesses.Node size M page size.!!!!PageSpace-time tradeoff.M large " only a few levels in tree.M small " less wasted space.Typical M 1000, N 1 trillion.insert 275!!!Bottom line. Number of page accesses is logMN per op.M 53 or 4 in practice!2324
B-Tree Example (cont)Symbol Table: Implementations Cost SummaryWorst CaseAverage leteSorted arraylog NNNlog NN/2N/2Unsorted listNNNNNNHashingN1NBSTNNN1*log N1*†log N1*†log N†Randomized BSTlog N‡log N‡log N‡log N§log N§log N§Splaylog N§log N§log N§log N§log N§log N§Red-Blacklog N§log N§log N§log N§log N§log N§B-Tree111111page accessesB-Tree. Number of page accesses is logMN per op.effectively a constant2526B-Trees in the WildSummaryVariants.B trees: Bayer-McCreight. [1972, Boeing]B trees: all data in external nodes.B* trees: keeps pages at least 2/3 full.R-trees for spatial searching: GIS, VLSI.Goal. ST implementation with log N guarantee for all ops.Probabilistic: randomized BST.Amortized: splay tree.Worst-case: red-black tree.Algorithms are variations on a theme: rotations when inserting.File systems.Windows: HPFS.Mac: HFS, HFS .Linux: ReiserFS, XFS, Ext3FS, JFS.Abstraction extends to give search algorithms for huge files.B-tree.!!!!!!!!!!!!Databases.Most common index type in modern databases.ORACLE, DB2, INGRES, SQL, PostgreSQL, !!2728
Splay TreesSplay TreesSplay trees self-adjusting BST.Tree automatically reorganizes itself after each op.After inserting x or searching for x, rotate x up to root usingdouble rotations.Tree remains "balanced" without explicitly storing any balanceinformation.!!!Amortized guarantee: any sequence of N ops, starting from emptysplay tree, takes O(N log N) time.Height of tree can be N.Individual op can take linear time.!!Robert Sedgewick and Kevin Wayne Copyright 2006 http://www.Princeton.EDU/ cos22630A Self-Adjusting TreeSplay TreesSplay.Check two links above current node.ZIG-ZAG: if orientations differ, same as root insertion.ZIG-ZIG: if orientations match, do top rotation first.!!!xyzAyB31ZIG-ZAGDxAzBCDC32
Splay TreesSplay TreesSplay.Check two links above current node.ZIG-ZAG: if orientations differ, same as root insertion.ZIG-ZIG: if orientations match, do top rotation first.Splay.Check two links above current node.ZIG-ZAG: if orientations differ, same as root insertion.ZIG-ZIG: if orientations match, do top rotation first.!!!!!zxyDxA!yAZIG-ZIGCZAG-ZAGBzBCDRoot SplayRoot Insertion33Splay ExampleSearch for 1.34Splay ExampleSearch for 1.1010998876Splay Insertion76ZIG-ZIG5ZIG-ZIG5443122133536
Splay ExampleSearch for 1.Splay ExampleSearch for 1.101099887166ZIG-ZIG1744252ZIG-ZIG5333738Splay ExampleSearch for 1.Splay ExampleSearch for 1.10111086297486ZIG745239533940
Splay ExampleSplay TreesSearch for 2.Intuition.Splay rotations halve search path.Reduces length of path for many other nodes in tree.!2110162848insert 1, 2, , 40insert 1, 2, , 40search 1search forrandom key103969Splay(2)74!575search 23search 3search 441Symbol Table: Implementations Cost SummaryWorst CaseAverage leteSorted arraylog NNNlog NNNUnsorted listN11N11HashingN1N1*1*1*log Nlog Nsqrt(N)log Nlog Nlog NBSTNNNRandomized BSTlog N‡log N‡log N‡Splaylog N§log N§log N§*†‡§log N§log N§log N†§assumes we know location of node to be deletedif delete allowed, insert/search become sqrt(N)probabilistic guaranteeamortized guaranteeSplay: Sequence of N ops takes linearithmic time.Ahead: Can we do all ops in log N time guaranteed?4342
2-3-4 Trees 4 2-3-4 Tree 2-3-4 tree. Generalize node to allow multiple keys; keep tree balanced. Perfect balance. Every path from root to leaf has same length. Allow 1, 2, or 3 keys per node.! 2-node: one key, two children.! 3-node: two keys, three children.! 4-node: three keys, four children. M O K R
Balanced search tree: A search-tree data structure for which a height of O(lg n) is guaranteed when implementing a dynamic set of n items. Examples: AVL trees 2-3 trees B-trees Red-black trees Treaps and Randomized Binary Search Trees
Compare and contrast the Net and Applet Java packages 4. To develop Java application using Servlet . Trees - Binary trees - Binary tree representation and traversals - Threaded binary trees - Expression Trees -Binary Search Tree - Applications of trees. Balanced trees: AVL trees. Priority queue - Binary heap - Heap operations - Applications .
The Man Who Planted Trees Curriculum Guide ABOUT TREES, pg. 1 ABOUT TREES, cont. pg. 12 Author Jean Giono once said that he wrote The Man Who Planted Trees because he wanted to “to make people love trees, or more precisely to make people love planting trees.” Read on to learn more about trees and the many
deletion operations, importance of balancing, AVL trees, searching insertion and deletions in AVL trees, redblack trees, comparison - with AVL trees, search insert and delete operations. 4 7. Multiway Trees: Issues in large dictionaries, m-way search trees, B-trees, search insert and delete operations, height of B-tree
Trees Removed - Rural 60 50 70 50 75 125 100* Trees Planted 323 242 375** 245 162 80 200* *Forecast ** The 2019 "Trees Planted" amount reflects 225 City trees, plus 150 Ballpark Commons trees *** With more developments, we will need to plant more development trees and replacement trees
How to Create a Successful Balanced Scorecard What is a Balanced Scorecard The balanced scorecard is a concept and tool first conceived by by Robert Kaplan and David Norton. The balanced scorecard idea debuted in the Harvard Business Review in 1992. "The balanced scorecard retains traditional financial measures. But financial measures tell the .
the preparation of a blueprint for Balanced Scorecard development and implementation. BALANCED SCORECARD BASICS PROGRAM OUTLINE I. Module I: Understanding the Balanced Scorecard A. What is the balanced scorecard? . programs, such as, Certificate in Strategic Human Resource Transformation and Organization Development from the Penn State .
Balanced Scorecard Step By Step guides readers through the processes required for a successful Balanced Scorecard project. In addition, he shows how to become a strategy-focused organiza-tion by imbedding the Balanced Scorecard into critical organizational pro-cesses. The book provides an
