Question? Leave a message!




Red-black trees

Red-black trees
ECE 250 Algorithms and Data Structures Redblack Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo trees Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Redblack trees 2 Outline In this topic, we will cover: – The idea behind a redblack tree – Defining balance – Insertions and deletions – The benefits of redblack trees over AVL treesRedblack trees 3 RedBlack Trees A red black tree ―colours‖ each node within a tree either red or black – This can be represented by a single bit – In AVL trees, balancing restricts the difference in heights to at most one – For redblack trees, we have a different set of rules related to the colours of the nodesRedblack trees 4 RedBlack Trees Define a null path within a binary tree as any path starting from the root where the last node is not a full node – Consider the following binary tree:Redblack trees 5 RedBlack Trees All null paths include: (H, C, B) (H, C, F, D) (H, L, J, I) (H, L, P) (H, C, B, A) (H, C, F, D, E) (H, L, J, K) (H, L, P, N, M) (H, C, F, G) (H, L, P, N, O)Redblack trees 6 RedBlack Trees The three rules which define a redblack tree are 1. The root must be black, 2. If a node is red, its children must be black, and 3. Each null path must have the same number of black nodesRedblack trees 7 RedBlack Trees These are two examples of redblack trees:Redblack trees 8 RedBlack Trees Theorem: Every red node must be either • A full node (with two black children), or • A leaf node Proof: Suppose node S has one child: • The one child L must be black • The null path ending at S has k black nodes • Any null path containing the node L will therefore have at least k + 1 black nodesRedblack trees 9 RedBlack Trees In our two examples, you will note that all red nodes are either full or leaf nodesRedblack trees 10 RedBlack Trees Another consequence is that if a node P has exactly one child: – The one child must be red, – The one child must be a leaf node, and – That node P must be blackRedblack trees 11 RedBlack Trees Suppose that the child is black – then the null path ending in P will have one fewer black nodes than the null path passing through C – this contradicts the requirement that each null path has the same number of black nodes – therefore the one child must be redRedblack trees 12 RedBlack Trees Suppose the child is not a leaf node: – Since it is red, its children: • cannot be red because that would contradict the requirement that all children of a red node are black, and • cannot be black, as that would cause any leaf node under the child to have more black nodes than the null path ending in P – Contradiction, therefore the child must be a leaf nodeRedblack trees 13 RedBlack Trees Since the one child is red and it must be a leaf node, the parent P must be black – otherwise, we would contradict the requirement that the child of a red node must be blackRedblack trees 14 RedBlack Trees Again, in our examples, the only nodes with a single child are black and the corresponding children are redRedblack trees 15 RedBlack Trees All redblack trees with 1, 2, 3, and 4 nodes:Redblack trees 16 RedBlack Trees All redblack trees with 5 and 6 nodes:Redblack trees 17 RedBlack Trees All redblack trees with seven nodes—most are shallow:Redblack trees 18 RedBlack Trees Every perfect tree is a redblack tree if each node is coloured black A complete tree is a redblack tree if: – each node at the lowest depth is coloured red, and – all other nodes are coloured black What is the worst caseRedblack trees 19 RedBlack Trees Any worstcase redblack tree must have an alternating redblack pattern down one side The following are the worstcase redblack trees with 1 and 2 black nodes per null path (i.e., heights 1 and 3)Redblack trees 20 RedBlack Trees To create the worstcase for paths with 3 black nodes per path, start with a black and red node and add the previous worstcase for paths with 2 nodes Redblack trees 21 RedBlack Trees This, however, is not a redblack tree because the two top nodes do not have paths with three black nodes – To solve this, add the optimal redblack trees with two black nodes per pathRedblack trees 22 RedBlack Trees That is, add two perfect trees with height 1 to each of the missing subtreesRedblack trees 23 RedBlack Trees Thus, we have the worstcase for a redblack tree with three black nodes per path (or a redblack tree of height 5)Redblack trees 24 RedBlack Trees Note that the left subtree of the root has height 4 while the right has height 1 – Thus suggests that AVL trees may be better...Redblack trees 25 RedBlack Trees To create the worstcase scenario for redblack trees with 4 black nodes per null path (i.e., height 7), again, start with two nodes and add the previous worstcase tree:Redblack trees 26 RedBlack Trees To satisfy the definition of the redblack tree, add two perfect trees of height 2:Redblack trees 27 RedBlack Trees Thus, with 30 nodes, the worst case redblack tree has height 7 – The worstcase AVL tree with 33 nodes has height 6...Redblack trees 28 RedBlack Trees Let k represent the number of black nodes per null path and h = 2k– 1 represent the height of the worstcase tree To determine F(k), the number of nodes in the worstcase tree, we note that F(1) = 2 and: k– 1 F(k) = F(k– 1) + 2 + 2(2– 1) the number of nodes in the worstcase redblack tree with two perfect trees of height k– 2 k– 1 nodes per null path the two extra nodesRedblack trees 29 RedBlack Trees Use Maple: rsolve( F(1) = 2, F(k) = 2 + F(k1) + 2(2(k–1)–1), F(k) ); k 2 2– 2 solve( h = 2k 1, k ); solve equation for k eval( 22k 2, ); evaluate at k = h/2 – 1/2 solve( n = , h ); solve for hRedblack trees 30 RedBlack Trees A little manipulation shows that the worstcase height simplifies to h = 2 lg(n + 2) – 3 worst This grows quicker than the worstcase height for an AVL tree h = log ( n ) – 1.3277 worstfRedblack trees 31 RedBlack Trees Plotting the growth of the height of the worstcase redblack tree (red) versus the worstcase AVL tree (blue) demonstrates this:Redblack trees 32 RedBlack Trees RedBlack Height AVL Tree Tree 1 2 2 This table shows the number of nodes 3 7 6 in a worstcase trees for the given 5 20 14 heights 7 54 30 9 143 62 11 376 126 Thus, an AVL tree with 131070 nodes has 13 986 254 a height of 23 while a redblack tree could 15 2583 510 have a height as large as 31 17 6764 1022 19 17710 2046 21 46367 4094 23 121492 8190 25 317810 16382 27 832039 32766 29 2178308 65534 31 5702886 131070 33 14930351 262142Redblack trees 33 RedBlack Trees Comparing redblack trees with AVL trees, we note that: – Redblack trees require one extra bit per node – AVL trees require one byte per node (assuming the height will never exceed 255) • aside: we can reduce this to two bits, storing one of –1, 0, or 1 indicating that the node is left heavy, balanced, or right heavy, respectivelyRedblack trees 34 RedBlack Trees AVL trees are not as deep in the worst case as are redblack trees – therefore AVL trees will perform better when numerous searches are being performed, – however, insertions and deletions will require: • more rotations with AVL trees, and • require recursions from and back to the root – thus AVL trees will perform worse in situations where there are numerous insertions and deletionsRedblack trees 35 Insertions We will consider two types of insertions: – bottomup (insertion at the leaves), and – topdown (insertion at the root) The first will be instructional and we will use it to derive the second caseRedblack trees 36 BottomUp Insertions After an insertion is performed, we must satisfy all the rules of a red black tree: 1. The root must be black, 2. If a node is red, its children must be black, and 3. Each path from a node to any of its descendants which are is not a full node (i.e., two children) must have the same number of black nodes The first and second rules are local: they affect a node and its neighbours The third rule is global: adding a new black node anywhere will cause all of its ancestors to become unbalanced Redblack trees 37 BottomUp Insertions Thus, when we add a new node, we will add a node so as to break the global rule: – the new node must be red We will then travel up the tree to the root fixing the requirement that the children of a red node must be blackRedblack trees 38 BottomUp Insertions If the parent of the inserted node is already black, we are done – Otherwise, we must correct the problem We will look at two cases: – the initial insertion, and – the recursive steps back to the rootRedblack trees 39 BottomUp Insertions For the initial insertion, there are two possible cases: – the grandparent has one child (the parent), or – the grandparent has two children (both red) Inserting A, the first case can be fixed with a rotation: Consequently, we are finished...Redblack trees 40 BottomUp Insertions The second case can be fixed more easily, just swap the colours: Unfortunately, we now may cause a problem between the parent and the grandparent....Redblack trees 41 BottomUp Insertions Fortunately, dealing with problems caused within the tree are identical to the problems at the leaf nodes Like before, there are two cases: – the grandparent has one child (the parent), or – the grandparent has two children (both red)Redblack trees 42 BottomUp Insertions Suppose that A and D, respectively were swapped In both these cases, we perform similar rotations as before, and we are finishedRedblack trees 43 BottomUp Insertions In the other case, where both children of the grandparent are red, we simply swap colours, and recurs back to the rootRedblack trees 44 BottomUp Insertions If, at the end, the root is red, it can be coloured blackRedblack trees 45 Examples of Insertions Given the following redblack tree, we will make a number of insertionsRedblack trees 46 Examples of Insertions Adding 46 creates a redred pair which can be corrected with a single rotationRedblack trees 47 Examples of Insertions Because the pivot is still black, we are finishedRedblack trees 48 Examples of Insertions Similarly, adding 5 requires a single rotationRedblack trees 49 Examples of Insertions Which again, does not require any additional workRedblack trees 50 Examples of Insertions Adding 10 allows us to simply swap the colour of the grand parent and the parent and the parent’s siblingRedblack trees 51 Examples of Insertions Because the parent of 5 is black, we are finishedRedblack trees 52 Examples of Insertions Adding 90 again requires us to swap the colours of the grandparent and its two childrenRedblack trees 53 Examples of Insertions This causes a redred parentchild pair, which now requires a rotationRedblack trees 54 Examples of Insertions A rotation does not require any subsequent modifications, so we are finishedRedblack trees 55 Examples of Insertions Inserting 95 requires a single rotationRedblack trees 56 Examples of Insertions And consequently, we are finishedRedblack trees 57 Examples of Insertions Adding 99 requires us to swap the colours of its grandparent and the grandparent’s children Redblack trees 58 Examples of Insertions This causes another redred childparent conflict between 85 and 90 which must be fixed, again by swapping colours Redblack trees 59 Examples of Insertions This results in another redred parentchild conflict, this time, requiring a rotationRedblack trees 60 Examples of Insertions Thus, the rotation solves the problemRedblack trees 61 TopDown Insertions and Deletions With a bottomup insertion, it is first necessary to search the tree for the appropriate location, and only then recurs back to the root correcting any problems – This is similar to AVL trees With redblack trees, it is possible to perform both insertions and deletions strictly by starting at the root, but not requiring the recurs back to the rootRedblack trees 62 TopDown Insertions The important observation is: – swapping may require recursive corrections going back all the way to the root – rotations do not require recursive steps back to the root Therefore, while moving down from the root, automatically swap the colours of any black node with two red children – this may require at most one rotation at the parent of the nowred nodeRedblack trees 63 Examples of TopDown Insertions We will start with the same redblack tree as before, but make top down insertions (no recursion):Redblack trees 64 Examples of TopDown Insertions Adding 46 does not find any (necessarily black) parent with two red childrenRedblack trees 65 Examples of TopDown Insertions However, it does require one rotation at the endRedblack trees 66 Examples of TopDown Insertions Similarly, adding 5 does not meet any parent with two red children:Redblack trees 67 Examples of TopDown Insertions A rotation solves the last problemRedblack trees 68 Examples of TopDown Insertions Adding 10 causes us to search down two edges before we meet node 5 with two red childrenRedblack trees 69 Examples of TopDown Insertions We swap the colours, and this does not cause a problem between 5 and 11Redblack trees 70 Examples of TopDown Insertions We continue and place 10 in the appropriate location – No further rotations are requiredRedblack trees 71 Examples of TopDown Insertions To add the node 90, we traverse down the right tree until we reach 85 which has two red childrenRedblack trees 72 Examples of TopDown Insertions We swap the colours, however this creates a redred pair between 85 and its parentRedblack trees 73 Examples of TopDown Insertions We require only one rotation to solve this problem, and we are guaranteed that this will not cause any problem for its parentsRedblack trees 74 Examples of TopDown Insertions We continue to search down the right path and add 90 in the appropriate location—no further corrections are requiredRedblack trees 75 Examples of TopDown Insertions Next, adding 95, we traverse down the righthand until we reach node 77 which has two red childrenRedblack trees 76 Examples of TopDown Insertions We swap the colours, which causes a redred parentchild combination which must be fixed by a rotationRedblack trees 77 Examples of TopDown Insertions The rotation is around the root – Note this rotation was not necessary with the bottomup insertion of 95Redblack trees 78 Examples of TopDown Insertions We can now proceed to add 95 by following the righthand branch, and the insertion causes a redred parentchild combinationRedblack trees 79 Examples of TopDown Insertions This is fixed with a single rotation – We are guaranteed that this will not cause any further problemsRedblack trees 80 Examples of TopDown Insertions If we compare the result of doing bottomup insertions (left, seen previously) and topdown insertions (right), we note the resulting trees are different, but both are still valid redblack treesRedblack trees 81 Examples of TopDown Insertions If we add 99, the first thing we note is that the root has two red children, and therefore we swap the coloursRedblack trees 82 Examples of TopDown Insertions At this point, each path to a nonfull node still has the same number of black nodes, however, we violate the requirement that the root is blackRedblack trees 83 Examples of TopDown Insertions We change the colour of the root to black – This adds one more black node to each pathRedblack trees 84 Examples of TopDown Insertions Moving to the right, we now reach node 90 which has two red children and therefore we swap the coloursRedblack trees 85 Examples of TopDown Insertions We continue down the right to add 99Redblack trees 86 Examples of TopDown Insertions This does not violate any of the rules of the redblack tree and therefore we are finishedRedblack trees 87 Examples of TopDown Insertions Again, comparing the result of doing bottomup insertions (left) and topdown insertions (right), we note the resulting trees are different, but both are still valid redblack treesRedblack trees 88 TopDown Deletions If we are deleting a red leaf node X, then we are finished If we are deleting a node X with one child, we only need to replace the value of the deleted node with the value of the leaf node Redblack trees 89 TopDown Deletions If we are deleting a full node, we use the same strategy used in standard binary search trees: – replace the node with the minimum element in the right subtree – then delete that element from the right subtreeRedblack trees 90 TopDown Deletions That minimum element must be either: – a red leaf node, – a black node with a single red leaf node, or – a black leaf node The first two cases are solved, consequently, we need only deal with the possibility that the leaf node we are deleting is blackRedblack trees 91 TopDown Deletions Similar to topdown insertions, we will adopt a strategy which ensures that the leaf node being deleted is not black ...to be completed...Redblack trees 92 RedBlack Trees In this topic, we have covered redblack trees – simple rules govern how nodes must be distributed based on giving each node a colour of either red or black – insertions and deletions may be performed without recursing back to the root – only one bit is required for the ―colour‖ – this makes them, under some circumstances, more suited than AVL treesRedblack trees 93 References 1 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990, Ch.14, p.26180. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley, §12.2, p.52534.Redblack trees 94 References Wikipedia, http://en.wikipedia.org/wiki/Hashfunction 1 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W. Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017