Held: Wednesday, 23 September 2015

Back to Outline 11 - Binary Search Trees. On to Outline 13 - Red-Black Trees, Continued.

Summary

We start to consider red-black trees, one of the approaches for making balanced trees.

Related Pages

Overview

• Balancing (or at least rearranging) balanced trees.
• Red-black tree basics.
• Red-black tree examples.
• Insertion in red-black trees.

Administrivia

• If things don't show up in the boards, check the .md file and send me an email (and send me another email).

Upcoming Work

• For Friday: Read CLRS on Red-Black Trees
• For Next Wednesday: HW 4
  • What kind of homework do you want? Implementation? Proof? Thought problems? Reading and reflection? Correcting someone else's incorrect work?

Extra Credit

Academic

• Wednesday CS Extra, 4:15 in 3821: Ursula Wolz on Building Coding Communities
• Thursday CS Extra, 4:15 in 3821: SamR on The Architecture of Mediascript
• CS Table Tuesday at noon.

Peer

• Monday 7-10 Sound Art Projects in JRC
• CM Talk

Balancing Binary Search Trees, Continuedj

How do we keep trees balanced? Let's start by thinking about some slightly imbalanced trees. Lowercase letters will represent values, uppercase letters will represent trees. Numbers in parentheses represent the height of a tree

       a(n+3)
        / \
       /   \
    b(n+2) C(n)
     / \
    /   \
 D(n+1) E(n)

How did you balance this?

What are all options you can come up with for adding a leaf that will cause an imbalance?

What whould we do in each case to achieve better balance?

Red-Black Trees

• Binary search trees in which every node is colored red or black. (The color can change.)
• The root is black.
• Leaves are null and are all black.
• Every red node has a black child. (Black nodes can have red or black children.)
• For any node, n, the number of black nodes on the path from n to any of its leaf descendants is the same. (Different nodes will naturally have different path lengths.) We call this the black height of a node.
  • How do you compute the black height of a node?
• Example: CLRS p. 310
  • Is this a red-black tree?
  • What the is black height of each node?
• Why do we care?
  • Intuitively, the longest path from root to leaf cannot be more than two times the length of the shortest path from root to leaf. (They get longer the more reds we insert.) as long

Exercises

These are taken from CLRS.

• Draw the complete binary tree of the integers [1... 15] (so it's perfectly blanced.)
  • 1/3 class; Color the nodes so that it has a black height of 2
  • 1/3 class: Color the nodes so that it has a black height of 3.
  • 1/3 class: Color the nodes so that it has a black height of 4
• What happens if we add node 36 to our sample tree?
  • If it's red?
  • If it's black?

Insertion

• Assumption: We make any node we insert red!
• What could go wrong?
• We'll look at a series of examples based on trees of size 4