SUNY Geneseo Department of Computer Science

Deleting from Ordered Trees

Previous Lecture

Misc

I'm out of town next Thursday and Friday

• Prof. Zollo lectures Friday
• (I run afternoon lab Tuesday)

Questions?

Deletion from Ordered Trees

Section 13.5.1

Problem: can't just replace node with its children because there are too many children

But if only one child, parent can be replaced

Otherwise preserve structure of tree by replacing root with largest node less than one being deleted, which must have only one child, to the left

Example

Examples

Performance of Deletion

Tree of n items, height h

Balanced trees

Consider search plus actual deletion

• Search phase: Θ(log n)
• Physical delete phase (cut-and-raise)
  • Last "else" gets executed in worst case
  • Time in this code depends on how many times "while" repeats
  • Bounded by (remaining) height of tree
  • No more than Θ(log n)

Other cases (best, worst-worst)

• Worst-worst (completely unbalanced)

• Never need to look for rightmost in left subtree
• But worst-case search phase could still take time Θ(h) = Θ(n)

Next

Limits of computing

Look at some very expensive algorithms

Read Section 15.1

Next Lecture