CSE310 Lecture 16 Red Black Trees Guoliang Larry Xue Department of CSE Arizona State University http optimization asu edu xue Guoliang Xue asu edu Topics of this lecture Problems with binary search trees Properties of Red Black Trees Tree Height Running time of RB Insertion Running time of RB deletion Demo of RB trees 2 Guoliang Xue asu edu Problems with Binary Search Trees O h operations h could be as high as n Can we make h as low as O log n 3 Guoliang Xue asu edu Red Black Tree A balanced binary tree also called AVL tree is a tree in which the heights depths of the two subtrees of every node never differ by more than 1 A red black tree is binary search tree with some extra properties that make it approximately balanced one extra bit to store color red or black A red node must have two black nodes as children Pointers to nil are considered as external nodes and are black data carrying nodes are all internal nodes All internal notes have two children 4 Guoliang Xue asu edu Red Black Tree Example root left nil data right color x parent left data right color nil parent left data right color nil nil 5 y parent left data right color nil nil Guoliang Xue asu edu Red Black Tree Definition 1 2 3 4 5 A binary search tree is a red black tree if it satisfies the following properties Every node is either red or black The root is black Every leaf nil is black If a node is red then both its children are black Every simple path from a node to a descendant leaf contains the same number of black nodes The number of black nodes on any path from a node x but not including x to a leaf is the black height of node x The black height of the root of a red black tree is the black height of the tree 6 Guoliang Xue asu edu Red Black Tree Example 26 17 41 14 21 10 7 16 12 15 3 nil nil nil nil nil 30 19 nil nil 20 23 28 nil nil nil nil nil nil 47 38 nil nil 35 39 nil nil nil nil nil nil Node 26 there are 3 black nodes to any leaf bh 3 Node 17 there are 3 black nodes to any leaf bh 3 Node 14 there is 2 black nodes to any leaf bh 2 Node 41 there is 2 black nodes to any leaf bh 2 7 Guoliang Xue asu edu Internal nodes and leaf nodes We will call the non leaf nodes in a red black tree internal nodes or data bearing nodes The internal nodes in a red black tree form a binary search tree The nil leaf nodes are all black We call the number of black nodes on any path from but not including a node x down to a leaf the black height of the node denoted by bh x The black height of the root is the black hight of the red black tree 8 Guoliang Xue asu edu Height of Red Black Tree Theorem A red black tree with n internal nodes has height h of at most 2 lg n 1 The idea of the proof is to show 1 The number of black nodes n 2 2 The black height bh h 2 3 n 2bh 1 This is the difficult step 4 n 2bh 1 2h 2 1 or 5 lg n 1 h 2 or h 2 lg n 1 9 Guoliang Xue asu edu Height of Red Black Tree contd 1 We first prove that a subtree rooted at any node x has 2bh x 1 internal nodes by induction on height h of x i If h x 0 then x is a leaf bh x 0 20 1 0 internal nodes The claim have 0 nodes holds ii Hypothesis The claim holds for k h iii Consider internal node x with two children y and z The child will have either the same bh or bh 1 worse case If y and z are red then bh x bh y bh z If y or z is black then bh x bh y 1 or bh z 1 Since the height h of children is one less than x we can apply the hypothesis on y and z Each child has at most 2bh x 1 1 nodes 10 Guoliang Xue asu edu Height of Red Black Tree contd Proof contd Therefore the number of nodes in the subtree rooted at x is 1 2bh x 1 1 2bh x 1 1 2bh x 1 x y z We therefore proved that subtree rooted at any node x has at least 2bh x 1 nodes 2 Now let s prove the claim in the theorem According to the definition of red black trees at least half of nodes on any path from root to leaf are black not including the root but including the leaf thus the black height must be at least h 2 and we have n 2bh r 1 2h 2 1 or lg n 1 h 2 or h 2 lg n 1 11 Guoliang Xue asu edu Running Time of Red Black Tree Operations Dynamic set operations Search Maximum Minimum Successor Predecessor can be done in O h O lgn time For operations Insertion Deletion A single operation can be done in O lgn time but it can not guarantee that the modified tree is still a red black tree Can insertion and deletion be supported in O lgn time 12 Guoliang Xue asu edu Red Black Tree Insertion Demo There are many demos of red black trees on the internet Here is a good one UC Demo 13 Guoliang Xue asu edu Summary Properties of Red Black Trees Height Complexities of operations Materials in Sections 13 1 13 3 14 Guoliang Xue asu edu
View Full Document
Unlocking...