Textbook Notes (270,000)
CA (160,000)
Carleton (2,000)
COMP (20)
Chapter 9

# COMP 2402 Chapter Notes - Chapter 9: Eaves, Binary Search Tree, Binary Search Algorithm

Department
Computer Science
Course Code
COMP 2402
Professor
Pat Morin
Chapter
9

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