Understanding Red-Black Trees: Properties, Implications, and Methods

Red-Black Trees are binary search trees with specific properties and color coding that facilitate efficient lookup, insert, and delete operations due to their balanced nature. The properties, implications, and essential methods like rotation and insertion-fixup make them a crucial data structure in computer science.

• Red-Black Trees
• Binary Search Trees
• Data Structures
• Balanced Trees
• Insertion

dott137 Follow

Uploaded on Sep 17, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Red Black Tree Essentials Notes from Introduction to Algorithms , Cormen et al.

2. Definition Red Black Trees A red-black tree is a binary search tree with an extra bit of storage per node. The extra bit represents the color of the node. It's either red or black. Each node contains the fields: color, key, left, right, and p. Any nil pointers are regarded as pointers to external nodes (leaves) and key bearing nodes are considered as internal nodes of the tree. See the video at: http://www.youtube.com/watch?v=vDHFF4wjWYU

3. Properties Red-black tree properties: 1. 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 of its children are black. 5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.

4. Implications From these properties, it can be shown (with a proof by induction) that the tree has a height no more than 2 * Lg(n + 1). Thus, worst case lookUp, insert, delete are all (Log n).

5. Three essential methods Rotation Insertion Insert-fixUp

6. LeftRotate(T,x) pre: right[x] != nil[T] pre: root's parent is nill[T] Left-Rotate(T,x) y = right[x] right[x] = left[y] p[left[y]] = x p[y] = p[x] if p[x] == nil[T] then root[T] = y else if x == left[p[x]] then left[p[x]] = y else right[p[x]] = y left[y] = x p[x] = y

7. Red Black Insert RB-Insert(T,z) y = nil[T] x = root[T] while x != nil[T] y = x if key[z] < key[x] then x = left[x] else x = right[x] p[z] = y if y = nil[T] root[T] = z else if key[z] < key[y] then left[y] = z else right[y] = z left[z] = nil[T] right[z] = nil[T] color[z] = RED RB-Insert-fixup(T,z)

8. RB-Insert-fixup(T,z) RB-Insert-fixup(T,z) { while(z's parent is Red) { set y to be z's uncle if uncle y is Red { color parent and uncle black color grandparent red set z to grandparent } else { // the uncle is black if (zig zag) { // make it a zig zig set z to parent rotate to zig zig } // rotate the zig zig and finish color parent of z black color grandparent of z red rotate grand parent of z } } // end while color root black }

9. Problem Insert the following numbers (one by one) into a Red Black Tree. Draw the tree after each insertion. Place an R or circle red nodes. 1,2,3,4,10,14,7,6,12

10. Answer Here is the final tree. 4 / \ 2R 10R / \ / \ 1 3 7 14 / / 6R 12R