Lecture Notes for CS 512, Algorithm Design

Binary Search Trees - 2 February 2000

1. collections of entity-value pairs

   1. priority queues, dictionaries

   2. operations: search, min, max, predecessor, successor, insert, and delete

2. trees - nodes with left and right children, value, and parent

3. bst property: n.left.value <= n.value <= n.right.value

4. tree walks - preorder, inorder, postorder

5. bst-search()

6. bst-minimum()

7. bst-maximum()

8. bst-successor()

9. bst-predecessor()

10. bst-insert()

11. bst-delete()

This page last modified on 2 February 2000.