Key Points

• We can use rotations to change the structure of a BST without changing the values that it holds.
  • A left rotation moves the root's right child up to be the new root.
  • A right rotation moves the root's left child up to be the new root.
  • Since rotations all involve a fixed number of pointer operations, they can be done in constant time.
  • This diagram shows how the nodes and subtrees get rearranged in a left and right rotation:

• Insert and move to root

  • We can use rotations to provide a way to insert new values at the root of a tree.
  • Insert at root actually puts the new value at a leaf, then “bubbles” it up to the root of the tree through a series of rotations.
  • Through the magic of recursion, we only have to keep track of one rotation at a time instead of remembering the long sequence of rotations needed to move a value from an arbitrary leaf up to the root of the tree.

• A randomized tree uses a random-number generator to decide whether to insert at the root of a subtree or to recurse further down into the left or right branch of the tree.

  • Randomized insertion might insert a new node at any layer of the tree.
  • For each subtree on the way from the root to a leaf, if \( N \) is the size of the subtree, then the node is inserted at the subtree root with probability \( \frac{1}{ N + 1 } \).
  • Randomized trees have expected height \( \Theta(\log n) \), no matter the order of key insertions!

• Random-number generation is a pain in C++.

  • Use the CS 70–provided library (RandUInt32) to make random-number generation easier!
  • In some circumstances (e.g., debugging, testing), being able to seed a random number generator can be a nice way to get predictable output from a random number generator. The RandUInt32 class in the CS 70–provided library can be seeded with an integer.

(When logged in, completion status appears here.)

Previous Page Next Page