**Search TreesRed-Black and Other Dynamically BalancedTrees**ECE573: Data Structures and Algorithms Electrical and Computer Engineering Dept. Rutgers University http://www.cs.rutgers.edu/~vchinni/dsa/**Searching - Re-visited**• Binary tree O(log n)if it stays balanced • Simple binary tree good for static collections • Low (preferably zero) frequency of insertions/deletions but my collection keeps changing! • It’s dynamic • Need to keep the tree balanced • First, examine some basic tree operations • Useful in several ways! ECE 573: Data Structures & Algorithms**Tree Traversal**• Traversal = visiting every node of a tree • Three basic alternatives • Pre-order • Root • Left sub-tree • Right sub-tree ¬ ® ¯ ° x A + x + B C x D E F L R L L R ECE 573: Data Structures & Algorithms**11**Tree Traversal • Traversal = visiting every node of a tree • Three basic alternatives • In-order • Left sub-tree • Root • Right sub-tree µ ¬ ± ³ ¯ ® ² ´ A x B + C x D x E + F ° L L R ECE 573: Data Structures & Algorithms**11**Tree Traversal • Traversal = visiting every node of a tree • Three basic alternatives • Post-order • Left sub-tree • Right sub-tree • Root µ ¬ ³ ´ ¯ ² A B C + D E x x F + x ± ° ® L L R ECE 573: Data Structures & Algorithms**11**Tree Traversal • Post-order • Left sub-tree • Right sub-tree • Root • Reverse-Polish Normal algebraic form which traversal? µ ¬ ³ ´ ¯ ² ± ° (A (((BC+)(DEx) x) F +)x ) ® (A x(((B+C)(DxE))+F)) ECE 573: Data Structures & Algorithms**Trees - Searching**• Binary search tree • Produces a sorted list by in-order traversal • In order: A D E G H K L M N O P T V ECE 573: Data Structures & Algorithms**Trees - Searching**• Binary search tree • Preserving the order • Observe that this transformation preserves thesearch tree ECE 573: Data Structures & Algorithms**Trees - Searching**• Binary search tree • Preserving the order • Observe that this transformation preserves thesearch tree • We’ve performed a rotation of the sub-tree about the T and O nodes ECE 573: Data Structures & Algorithms**Trees - Rotations**• Binary search tree • Rotations can be either left- or right-rotations • For both trees: the inorder traversal is • A x B y C ECE 573: Data Structures & Algorithms**Trees - Rotations**• Binary search tree • Rotations can be either left- or right-rotations • Note that in this rotation, it was necessary to moveB from the right child of x to the left child of y ECE 573: Data Structures & Algorithms**Trees - Red-Black Trees**• A Red-Black Tree • Binary search tree • Each node is “coloured” red or black • An ordinary binary search tree with node colouringsto make a red-black tree ECE 573: Data Structures & Algorithms**Trees - Red-Black Trees**• A Red-Black Tree • Every node is RED or BLACK • Every leaf is BLACK When you examinerb-tree code, you will see sentinel nodes (black) added as the leaves. They contain no data. Sentinel nodes (black) ECE 573: Data Structures & Algorithms**Trees - Red-Black Trees**• A Red-Black Tree • Every node is RED or BLACK • Every leaf is BLACK • If a node is RED, then both children are BLACK This implies that no path may have two adjacent RED nodes. (But any number of BLACK nodes may be adjacent.) ECE 573: Data Structures & Algorithms**Trees - Red-Black Trees**• A Red-Black Tree • Every node is RED or BLACK • Every leaf is BLACK • If a node is RED, then both children are BLACK • Every path from a node to a leaf contains the same number of BLACK nodes From the root, there are 3 BLACK nodes on every path ECE 573: Data Structures & Algorithms**Trees - Red-Black Trees**• A Red-Black Tree • Every node is RED or BLACK • Every leaf is BLACK • If a node is RED, then both children are BLACK • Every path from a node to a leaf contains the same number of BLACK nodes The length of this path is the black height of the tree ECE 573: Data Structures & Algorithms**Trees - Red-Black Trees**• Lemma A RB-Tree with n nodes has height £2 log(n+1) • Proof .. See Cormen • Essentially,height £2 black height • Search time O( log n ) ECE 573: Data Structures & Algorithms**Trees - Red-Black Trees**• Data structure • As we’ll see, nodes in red-black trees need to know their parents, • so we need this data structure struct t_red_black_node { enum { red, black } colour; void *item; struct t_red_black_node *left, *right, *parent; } Same as a binary tree with these two attributes added ECE 573: Data Structures & Algorithms**Trees - Insertion**• Insertion of a new node • Requires a re-balance of the tree rb_insert( Tree T, node x ) { /* Insert in the tree in the usual way */ tree_insert( T, x ); /* Now restore the red-black property */ x->colour = red; while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; Insert node 4 Mark itred Label the current node x ECE 573: Data Structures & Algorithms**Trees - Insertion**rb_insert( Tree T, node x ) { /* Insert in the tree in the usual way */ tree_insert( T, x ); /* Now restore the red-black property */ x->colour = red; while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; While we haven’t reached the root and x’s parent is red x->parent ECE 573: Data Structures & Algorithms**Trees - Insertion**rb_insert( Tree T, node x ) { /* Insert in the tree in the usual way */ tree_insert( T, x ); /* Now restore the red-black property */ x->colour = red; while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; If x is to the left of it’s granparent x->parent->parent x->parent ECE 573: Data Structures & Algorithms**Trees - Insertion**/* Now restore the red-black property */ x->colour = red; while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; y is x’s right uncle x->parent->parent x->parent right “uncle” ECE 573: Data Structures & Algorithms**Trees - Insertion**while ((x != T->root)&& (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /*If x's parent is a left, y is x's right'uncle’*/ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; If the uncle is red, change the colours of y, the grand-parent and the parent x->parent->parent x->parent right “uncle” ECE 573: Data Structures & Algorithms**Trees - Insertion**while ((x != T->root)&& (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; ECE 573: Data Structures & Algorithms**Trees - Insertion**while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; x’s parent is a left again, mark x’s uncle but the uncle is black this time New x ECE 573: Data Structures & Algorithms**Trees - Insertion**while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); .. but the uncle is black this time and x is to the right of it’s parent ECE 573: Data Structures & Algorithms**Trees - Insertion**while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); .. So move x up and rotate about x as root ... ECE 573: Data Structures & Algorithms**Trees - Insertion**while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); ECE 573: Data Structures & Algorithms**Trees - Insertion**while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); .. but x’s parent is still red ... ECE 573: Data Structures & Algorithms**Trees - Insertion**while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); .. The uncle is black .. uncle .. and x is to the left of its parent ECE 573: Data Structures & Algorithms**Trees - Insertion**while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); else { /* case 3 */ x->parent->colour = black; x->parent->parent->colour = red; right_rotate( T, x->parent->parent ); } .. So we have the final case .. ECE 573: Data Structures & Algorithms**Trees - Insertion**while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); else { /* case 3 */ x->parent->colour = black; x->parent->parent->colour = red; right_rotate( T, x->parent->parent ); } .. Change colours and rotate .. ECE 573: Data Structures & Algorithms**Trees - Insertion**while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); else { /* case 3 */ x->parent->colour = black; x->parent->parent->colour = red; right_rotate( T, x->parent->parent ); } ECE 573: Data Structures & Algorithms**Trees - Insertion**while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); else { /* case 3 */ x->parent->colour = black; x->parent->parent->colour = red; right_rotate( T, x->parent->parent ); } This is now a red-black tree .. So we’re finished! ECE 573: Data Structures & Algorithms**Trees - Insertion**while ( (x != T->root) && (x->parent->colour == red) ) { if ( x->parent == x->parent->parent->left ) { /* If x's parent is a left, y is x's right 'uncle' */ y = x->parent->parent->right; if ( y->colour == red ) { /* case 1 - change the colours */ x->parent->colour = black; y->colour = black; x->parent->parent->colour = red; /* Move x up the tree */ x = x->parent->parent; else { /* y is a black node */ if ( x == x->parent->right ) { /* and x is to the right */ /* case 2 - move x up and rotate */ x = x->parent; left_rotate( T, x ); else { /* case 3 */ x->parent->colour = black; x->parent->parent->colour = red; right_rotate( T, x->parent->parent ); } } else .... There’s an equivalent set of cases when the parent is to the right of the grandparent! ECE 573: Data Structures & Algorithms**Red-black trees - Analysis**• Addition • Insertion Comparisons O(log n) • Fix-up • At every stage,x moves up the tree at least one level O(log n) • Overall O(log n) • Deletion • Also O(log n) • More complex • ... but gives O(log n) behaviour in dynamic cases ECE 573: Data Structures & Algorithms**Red Black Trees - What you need to know?**• Code? • This is not a course for masochists! • You can find it in a text-book • You need to know • The algorithm exists • What it’s called • When to use it • ie what problem does it solve? • Its complexity • Basically how it works • Where to find an implementation • How to transform it to your application ECE 573: Data Structures & Algorithms**Key Points**• Red-Black Trees • A complex algorithm • Gives O(log n) addition, deletion and search • Software engineers • Know about algorithms • Know when to use them • Know performance • Know where to find an implementation • Are too clever to re-invent wheels ... • They re-use code • So they have more time for • Sailing, eating, drinking, ... Anything else I should put here ECE 573: Data Structures & Algorithms**AVL and other balanced trees**• AVL Trees • First balanced tree algorithm • Discoverers: Adelson-Velskii and Landis • Properties • Binary tree • Height of left and right-subtrees differ by at most 1 • Subtrees are AVL trees AVL Tree AVL Tree ECE 573: Data Structures & Algorithms**AVL trees - Height**• Theorem • An AVL tree of height h has at leastFh+3+1 nodes • Proof • Let Sh be the size of the smallest AVL tree of height h • Clearly, S0= 1 and S1= 2 • Also,Sh = Sh-1+ Sh-2 + 1 • A minimum height tree must be composed of min height trees differing in height by at most 1 • By induction .. • Sh =Fh+3+1 ECE 573: Data Structures & Algorithms**AVL trees - Height**• Now, for large i, Fi+1 / Fi = f, where f = ½(1 + Ö5) orFi» c (½(1 + Ö5))i • Sh =Fh+3 + 1 = O( bh ) • n³Sh,so n is W( bh ) andh £logb n or h is O(log n) ECE 573: Data Structures & Algorithms**AVL trees - Height**• Now, for large i, Fi+1 / Fi = f, where f = ½(1 + Ö5) orFi» c (½(1 + Ö5))i • Sh =Fh+3 + 1 = O( bh ) • n³Sh,so n is W( bh ) andh £logb n or h is O(log n) • In this case, we can show • h £1.44logb (n+2) - 1.328 his no worse than 44% higher than the optimum ECE 573: Data Structures & Algorithms**AVL Trees - Rebalancing**• Insertion leads to non-AVL tree • 4 cases • 1 and 4 are mirror images • 2 and 3 are mirror images 1 2 3 4 ECE 573: Data Structures & Algorithms**AVL Trees - Rebalancing**• Case 1 solved by rotation • Case 4 is the mirror image rotation ECE 573: Data Structures & Algorithms**AVL Trees - Rebalancing**• Case 2 needs a double rotation • Case 3 is the mirror image rotation ECE 573: Data Structures & Algorithms**AVL Trees - Data Structures**• AVL trees can be implemented with a flag to indicate the balance state • Insertion • Insert a new node (as any binary tree) • Work up the tree re-balancing as necessary to restorethe AVL property typedef enum { LeftHeavy, Balanced, RightHeavy } BalanceFactor; struct AVL_node { BalanceFactor bf; void *item; struct AVL_node *left, *right; } ECE 573: Data Structures & Algorithms**Dynamic Trees - Red-Black or AVL**• Insertion • AVL : two passes through the tree • Down to insert the node • Up to re-balance • Red-Black : two passes through the tree • Down to insert the node • Up to re-balance but Red-Black is more popular?? ECE 573: Data Structures & Algorithms**Dynamic Trees - A cautionary tale**• Insertion • If you read Cormen et al, • There’s no reason to prefer a red-black tree • However, in Weiss’ text M A Weiss, Algorithms, Data Structures and Problem Solving with C++, Addison-Wesley, 1996 • you find that you can balance a red-black tree in one pass! • Making red-black more efficient than AVLif coded properly!!! ECE 573: Data Structures & Algorithms**Dynamic Trees - A cautionary tale**• Insertion • If you read Cormen et al, • There’s no reason to prefer a red-black tree • However, in Weiss’ text M A Weiss, Algorithms, Data Structures and Problem Solving with C++, Addison-Wesley, 1996 • you find that you can balance a red-black tree in one pass! • Making red-black more efficient than AVLif coded properly!!! Moral: You need to read the literature! ECE 573: Data Structures & Algorithms**Dynamic Trees - A cautionary tale**• Insertion in one pass • As you proceed down the tree,if you find a node with two red children,make it red and the children black • This doesn’t alter the number of black nodes in any path • If the parent of this node was red,a rotation is needed ... • May need to be a single or a double rotation ECE 573: Data Structures & Algorithms