Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• 2-3 Trees.
• Insertion in 2-3 Trees.
• Deletion in 2-3 Trees.
• B-Trees.

Preliminaries

Admin

• Homework due!

Upcoming Work

• For Friday the 2nd: Skim Knuth Handout
• For Friday the 9th: Exam 1 (distributed tonight)

Extra Credit

• Don't forget that you can send these to me in advance!

Academic

• Convocation Thursday at 11 am
• CS Extra Thursday at 4:15 p.m.: PMO and CC on Grad School.
• Peter Coyote Thursday at 7pm
• CS Table Tuesday at noon: NSA Barbie

Peer

• EE Closing 8pm tonight
• Women's Soccer, Saturday or Sunday at 11 am
• Men's Soccer, Saturday or Sunday at 1:30 pm

Questions

2-3 Trees

• Yet another attempt to make balanced search trees.
• Nodes can have 1 or 2 values ; and 2 or 3 subtrees
  • 1 value -> 2 subtrees
  • 2 values -> 3 subtrees
• "Obvious" organization (see whiteboard)
• All subtrees are the same height

Insertion in 2-3 Trees

• We insert at leaves
• Think about cases
• Hint: Think about temporarily expanding to 3 values in a node
• Hint: Think about "propagate up" as an option

Idea 1: If we insert in the two-element left subtree of a singleton node, move the largest value in the left subtree up, and move the value in the right subtree down

Idea 2: Move the center value value up, split the node, and cross your fingers.

We will pursue idea 2

Example

          (8)
         /   \
      (2 5)  (17)

Insert 7

          (5 8)
         /  |  \
      (2)  (7)  (17)

Task

                (8   12)
              /    |    \
          (2 5)   (10)  (17)


Assume we insert 4

              (4  8   12)
              /    |    \
          (2) (5)   (10)  (17)


Pop the middle one up and split it

                (8)
              /    \
           (4)      (12)
          /   \     /   \
        (2)  (5)  (10)  (17)


Deletion in 2-3 Trees


Hint: Assume we only delete at leaves
Think about cases
Hint: Think about when you'll need to "propagate up"
Hint: Think about sibling nodes


                (8)
              /    \
           (4)      (12)
          /   \     /   \
        (2)  (5)  (10)  (17 21)


B-Trees

Generalized 2-3 trees   min # values in a node and a maximum number
(m-n)

Idea: The nodes in the tree are stored on disk, so we have 1K or more per
node.  We might as well make use of it.  So ... array of values and links
to other disk blocks