3.4-binary_search_trees.md

Binary search trees

• doubly-linked lists supported insertion and deletion in O(1) but linear query time
• sorted lists support logarithmic query time but linear time update
• binary search tree: fast search and flexible update
• two pointer for each element: the median elements above and below the given node
• a rooted binary tree is recursively defined as either
  • (1) being empty, or
  • (2) consisting of a node called the root, together with two rooted binary trees called the left and right subtrees
• a binary search tree labels each node in a binary tree such that for any node labeled x:
  • all nodes in the left subtree of x have keys < x
  • all nodes in the right subtree of x have keys > x
• nodes have a left and right pointer field (optional parent pointer) and a data field

searching

• start at the root
• unless root is what we're looking for proceed either left or right depending upon whether x occurs before or after the root key
• runs in O(h) time where h is the height of the tree

minimum and maximum

• the minimum element must be the leftmost descendent of the root
• the maximum element must be the rightmost descendent of the root
• runs in O(h) time where h is the height of the tree

tree traversal

• listing the labels of the tree nodes
• in-order: recursively
  • process left subtree first
  • then process actual item
  • process right subtree last
• pre/post order by moving actual item before/after processing subtrees

insertion

• there is only one place to insert an item x into a binary search tree T where we know we can find it again
• we must replace the NULL pointer found in T after an unsuccessful query for the key k
• take care to assign the correct left/right pointer
• runs in O(h) time where h is the height of the tree

deletion

• three cases
• leaf node: zero children, simply remove it
• node with one child: replace node with child
• node with two children: relabel this node with the key of its immediate successor (leftmost descendant in the right subtree)
• TODO: add actual delete algorithm
• takes at most two searches and some contant time: O(h)

performance

• best case if the tree is perfectly balanced: h = log(n)
• worst case: inserting elements in sorted order: h = n
• based on all n! orderings there's a high probablity to get a log(n) tree
• randomization can be helpful

balanced search trees

• worst case out of our hands as it depends on user input
• insert/delete can be implemented in a way that adjusts after each operation
• keeps the tree close enough to be balanced so the max height is logarithmic
• all dictionary operations (search, insert, delete) take O(log n) time
• concrete implementations: red-black trees, avl trees, splay trees