Question? Leave a message!

Red-black trees

Red-black trees
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
ECE 250 Algorithms and Data Structures Red-black Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo trees Waterloo, Ontario, Canada © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Red-black trees 2 Outline In this topic, we will cover: – The idea behind a red-black tree – Defining balance – Insertions and deletions – The benefits of red-black trees over AVL treesRed-black trees 3 Red-Black 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 red-black trees, we have a different set of rules related to the colours of the nodesRed-black trees 4 Red-Black 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:Red-black trees 5 Red-Black 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)Red-black trees 6 Red-Black Trees The three rules which define a red-black 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 nodesRed-black trees 7 Red-Black Trees These are two examples of red-black trees:Red-black trees 8 Red-Black 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 nodesRed-black trees 9 Red-Black Trees In our two examples, you will note that all red nodes are either full or leaf nodesRed-black trees 10 Red-Black 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 blackRed-black trees 11 Red-Black 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 redRed-black trees 12 Red-Black 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 nodeRed-black trees 13 Red-Black 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 blackRed-black trees 14 Red-Black Trees Again, in our examples, the only nodes with a single child are black and the corresponding children are redRed-black trees 15 Red-Black Trees All red-black trees with 1, 2, 3, and 4 nodes:Red-black trees 16 Red-Black Trees All red-black trees with 5 and 6 nodes:Red-black trees 17 Red-Black Trees All red-black trees with seven nodes—most are shallow:Red-black trees 18 Red-Black Trees Every perfect tree is a red-black tree if each node is coloured black A complete tree is a red-black tree if: – each node at the lowest depth is coloured red, and – all other nodes are coloured black What is the worst case?Red-black trees 19 Red-Black Trees Any worst-case red-black tree must have an alternating red-black pattern down one side The following are the worst-case red-black trees with 1 and 2 black nodes per null path (i.e., heights 1 and 3)Red-black trees 20 Red-Black Trees To create the worst-case for paths with 3 black nodes per path, start with a black and red node and add the previous worst-case for paths with 2 nodes