This

**preview**shows half of the first page. to view the full**2 pages of the document.**Chapter 9: Red-Black Trees

● Version of binary search trees with logarithmic height

● One of most widely used data structures, often used in library implementations

● stores n values while having a height of at most 2logn

● add(x) and remove(x) run in, at worst case, O(logn) time

● amortized number of rotations performed during an add(x) or remove(x) operation is

constant

9.1 2-4 Trees

● A rooted tree where all leaves have the same depth, and every internal node has 2, 3, or

4 children

● A 2-4 tree with n leaves has height at most logn

● When adding a node u as a child of w, if this causes w to have 5 children, split w into w

and w’ each having 2 and 3 nodes respectively. w’ then becomes a child of w’s parent. If

this causes w’s parent to have too many children, split w’s parent and so on and so forth.

Process continues until a node is reached with less than 4 children or the root is

reached. In this case root r is split into r and r’ and a new root is assigned, increasing the

depth of every leaf by 1.

● remove a leaf u from its parent w. If w now has only 1 child, look at w’s sibling w’. If w’

has 3, 4 children, take a child from w’ and give it to w. If w’ has only 2 children, give both

children to w, and recursively remove w’ from the parent of w’

9.2 RedBlackTree: A simulated 2-4 tree

● A binary search tree where each node u has an assigned colour of red or black, red

represented by 0, black by 1.

● There are the same number of black nodes on every root to leaf path

● No two red nodes are adjacent

● Removing each red node u and connecting u’s 2 children to the black parent of u, turns

the tree into a 2-4 tree

● 1st and last node in root to tree path are black. This path will contain at most log(n + 1)

black nodes and log(n + 1) - 1 red nodes

● The height of a red black tree with n nodes is at most 2logn

● When adding, a node with 5 children in a red-black tree is represented by a black node

with 2 red children, one of which also has a red child. Can “split” this node by colouring it

red and colouring its two children black

● When removing, merging two nodes is the inverse of a split, colouring two black siblings

red and their red parent black. Borrowing from a sibling is the most complicated

procedure and involves both rotations and recolouring nodes

●Left Leaning Red-Black Tree: Maintains the additional property that at any node u, if

u.left is black, then u.right is black

○ reduces number of cases in add(x) and remove(x) operations

●pushBlack(u) takes as input a black node u that has two red children and colours u red

and its children black. pullBlack(u) does the exact opposite

###### You're Reading a Preview

Unlock to view full version