CSE310 Lecture 16: Red-Black TreesTopics of this lectureProblems with Binary Search TreesPowerPoint PresentationSlide 5Slide 6Slide 7Internal nodes and leaf nodesSlide 9Height of Red-Black Tree (contd.)Slide 11Slide 12Red-Black Tree Insertion [email protected] Lecture 16: Red-Black TreesCSE310 Lecture 16: Red-Black TreesGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://optimization.asu.edu/[email protected] of this lectureTopics of this lectureProblems with binary search treesProperties of Red-Black TreesTree HeightRunning time of RB-InsertionRunning time of RB-deletionDemo of RB [email protected] with Binary Search TreesProblems with Binary Search TreesO(h) operationsh could be as high as nCan we make h as low as O(log n)[email protected] TreeA 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 [email protected] Tree: Exampleleftnilrightrootdataparentrightdataleftparentrightdataxycolorcolorcolorleftparentrightdatacolornil nil nilnil [email protected] Tree: DefinitionA binary search tree is a red-black tree if it satisfies the following properties1. Every node is either red or black;2. The root is black;3. Every leaf (nil) is black;4. If a node is red, then both its children are black;5. 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 [email protected] Tree: Example141921 30387nil nil nilnil3nil1210 16nil nil15nil nilnil nil20nil nil23nil nil28nil nil35nil nil39nil nil4717 4126Node 26: there are 3 black nodes to any leaf, bh = 3Node 17: there are 3 black nodes to any leaf , bh = 3Node 14: there is 2 black nodes to any leaf , bh = 2Node 41: there is 2 black nodes to any leaf , bh = [email protected] nodes and leaf nodesInternal nodes and leaf nodesWe 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 [email protected] of Red-Black TreeTheorem: A red-black tree with n internal nodes has height h of at most 2lg(n+1)The idea of the proof is to show1. The number of black nodes n/22. The black height bh h/23. 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)[email protected] ofHeight of Red Red--BlackBlack Tree (contd.) 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 most2bh(x)-1 - 1 nodes,[email protected] 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 haven 2bh(r) - 1 2h/2 - 1, or lg(n+1) h/2, or h 2 lg(n+1)[email protected] Time of Red-Black Tree OperationsDynamic-set operations:SearchMaximumMinimumSuccessorPredecessorcan be done in O(h) = O(lgn) time. For operationsInsertionDeletionA 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) [email protected] Tree Insertion DemoRed-Black Tree Insertion DemoThere are many demos of red-black trees on the internet.Here is a good one: [email protected]Properties of Red-Black TreesHeightComplexities of operationsMaterials in Sections
View Full Document
Unlocking...