binary search tree

constituents

Assume keys are distinct.

  • node: elements in the tree
  • key: each node has a key, which tags the node and is the key being sorted on
  • root: the node with no parents
  • leaves: the nodes with two nil children
  • height: number of edges root to leaf (i.e. if there is a tree root-leaf directly, then the height is 1)

Every node has 2, possibly-null, children. Every node has a parent except for the root.

requirements

A binary search tree is a binary tree such that ever left descendant of a node has a key less than that node; every right descendant of a node has a key larger than that node.

additional information

building a binary tree

  • pick a random node
  • partition list to the left and right
  • and then pick random parts in the left and right

You will note this is quicksort. which is true!

extract ordered list via binary search tree

def traverse(x):
    if x is not None:
        traverse(x.left)
        print(x.key)
        traverse(x.right)

searching for elements

  1. start at the root
  2. if your key is less than current node, go left…
  3. otherwise, go right

Terminate at NIL/conventionally return the last element you found. This takes O(height), and if balanced is log(n). This is better. We ideally want of a self-balancing search tree, namely a red-black tree.

inserting new elements

search (you won’t find it), and then insert following the rules at the desired node.

deleting things

there are three cases, handle all three, but generally takes a few steps once you find the node

motivation

Suppose we have nodes with keys (algorithms). How can we store them?

  1. array / sorted array
  2. linked list (i.e. not necessary sorted)

What are some basic operations?

  • INSERT
  • SEARCH
  • DELETE

How long would they typically take? For arrays:

  • INSERT: \(O\qty(n)\)
  • DELETE: \(O\qty(n)\)
  • SEARCH: \(O\qty(\log n)\)

Unsorted linked lists:

  • INSERT: \(O\qty(1)\)
  • SEARCH/DELETE: \(O\qty(n)\)

Notice how existing structures have all some \(O\qty(n)\) operations, which is bad. Turns out, binary search trees have the property that all operations (INSERT, SEARCH, DELETE) are all \(O\qty(\log n)\).