CS210 · Trees · Annotated SlidesBinary Search Trees
Original
Overview

Binary Search Trees

BST definition, search and insert (Java), tree shape and its effect on cost, lazy deletion, deleting the minimum, and Hibbard deletion.

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 31 slides
  1. 1 A l g o r i t h m s
  2. 2 Slide 2
  3. 3 must
  4. 4 Binary search tree demo
  5. 5 Binary search tree demo
  6. 6 BST representation in Java
  7. 7 BST implementation (skeleton)
  8. 8 BST search: Java implementation
  9. 9 iii
  10. 10 BST insert
  11. 11 Slide 11
  12. 12 BST insert: Java implementation
  13. 13 Tree shape
  14. 14 BST insertion: random order visualization
  15. 15 BSTs: mathematical analysis
  16. 16 ST implementations: summary
  17. 17 Slide 17
  18. 18 ST implementations: summary
  19. 19 BST deletion: lazy approach
  20. 20 hasnochild
  21. 21 Deleting the minimum
  22. 22 Hibbard deletion
  23. 23 iw.a
  24. 24 soswei.es
  25. 25 Simlevernoses
  26. 26 Hibbard deletion
  27. 27 Hibbard deletion
  28. 28 Hibbard deletion: Java implementation
  29. 29 Hibbard deletion: analysis
  30. 30 commissiics
  31. 31 Slide 31
Slide 1 / 31

A l g o r i t h m s

Slide 1: A l g o r i t h m s
Slide 2 / 31

Slide 2

Slide 2: Slide 2
Slide 3 / 31

must

Slide 3: must
Slide 4 / 31

Binary search tree demo

Slide 4: Binary search tree demo
Slide 5 / 31

Binary search tree demo

Slide 5: Binary search tree demo
Slide 6 / 31

BST representation in Java

Slide 6: BST representation in Java
Slide 7 / 31

BST implementation (skeleton)

Slide 7: BST implementation (skeleton)
Slide 8 / 31

BST search: Java implementation

Slide 8: BST search: Java implementation
Slide 9 / 31

iii

Slide 9: iii
Slide 10 / 31

BST insert

Slide 10: BST insert
Slide 11 / 31

Slide 11

Slide 11: Slide 11
Slide 12 / 31

BST insert: Java implementation

Slide 12: BST insert: Java implementation
Slide 13 / 31

Tree shape

Slide 13: Tree shape

Notes

  1. Shape depends on insertion order: random → ~1.39 lg N; sorted order → a path (N).

Exam angle

PredictionQ1

Inserting 1, 2, 3, 4, 5 in order into an empty BST gives height:

Slide 14 / 31

BST insertion: random order visualization

Slide 14: BST insertion: random order visualization
Slide 15 / 31

BSTs: mathematical analysis

Slide 15: BSTs: mathematical analysis
Slide 16 / 31

ST implementations: summary

Slide 16: ST implementations: summary
Slide 17 / 31

Slide 17

Slide 17: Slide 17
Slide 18 / 31

ST implementations: summary

Slide 18: ST implementations: summary
Slide 19 / 31

BST deletion: lazy approach

Slide 19: BST deletion: lazy approach
Slide 20 / 31

hasnochild

Slide 20: hasnochild
Slide 21 / 31

Deleting the minimum

Slide 21: Deleting the minimum
Slide 22 / 31

Hibbard deletion

Slide 22: Hibbard deletion

Notes

  1. Hibbard deletion: 0 children → remove; 1 child → replace with child; 2 children → replace with successor (min of right subtree).

Exam angle

PredictionQ1

How do you delete a node with two children from a BST?

Compare with the model answer

Find its successor (the minimum of its right subtree), copy the successor’s key into the node, then delete the successor (which has at most one child).

Slide 23 / 31

iw.a

Slide 23: iw.a
Slide 24 / 31

soswei.es

Slide 24: soswei.es
Slide 25 / 31

Simlevernoses

Slide 25: Simlevernoses
Slide 26 / 31

Hibbard deletion

Slide 26: Hibbard deletion
Slide 27 / 31

Hibbard deletion

Slide 27: Hibbard deletion
Slide 28 / 31

Hibbard deletion: Java implementation

Slide 28: Hibbard deletion: Java implementation
Slide 29 / 31

Hibbard deletion: analysis

Slide 29: Hibbard deletion: analysis

Notes

  1. Hibbard deletion makes trees unbalanced over time (√N height).

Slide 30 / 31

commissiics

Slide 30: commissiics
Slide 31 / 31

Slide 31

Slide 31: Slide 31