Traversal

Tree Traversals:

  • preorder (or postorder)
  • inorder (only for binary trees)
  • lever-order

Given two traversal sequence, a unique binary tree can be constructed if and only if one sequence is inorder traversal. However, for binary search tree, arbitrary traversal sequence is sufficient.

Full binary trees: all nodes except leaves have two children.

  • the number of leaves is one more than the number of internal nodes.

Search Trees

Search trees are data structures used to efficiently searche and update on sets of items that satisfy a total order. Possible operations includes:

  • empty, singleton: create an empty tree or a tree with a single item.
  • search, max, min, successor, predecessor
  • order(k): how may elements are less than k.
  • insert, delete
  • split(T, k): split a tree T, return (T1, F, T2) with all keys in T1 less than k, all keys in T2 greater than k, and F be true if and only if k exists.
  • join(T1, T2): join two trees, where all keys in T1 are less than that in T2, takes O(log(|T1| + |T2|))
  • union, intersect, difference

Some details:

  1. The set may be a multiset, i.e. allow the same key appear multiple times.
  2. For some operations, such as successor, the input may be either a key or a node.
  3. Sometimes an operation may ask for only a value, other times it ask for a pointer to the corresponding node.
  4. Updating a node can be implemented by deleting it followed by inserting a node.

Balanced: A tree is blanced if it has Trees - 图1 height.

Binary Search Tree

A list of blanced (binary) search trees:

  • AVL trees
  • Red-black trees
  • Weight balanced (BB[ℵ]) trees
  • Treaps: Combine trees and heaps. Assign randomly a priority to each key and grow the tree by inserting keys one by one in the order of priorities, hence resulting in heap property with respect to those priorities.
  • Splay trees
  • Other binary trees including scapegoat trees, skip lists
  • Non-binary trees, such as 2-3 trees, brother trees, B-trees

For balanced binary search trees, such as red-black trees, operations that follow take Trees - 图2 if not specified. (n = |T|, n = max(|T1|, |T2|), m = min(|T1|, |T2|))

  1. search, min, max, predecessor, successor
  2. insert, delete
  3. union, intersect, diff: all take Trees - 图3
  4. split, join

Red-black trees can be regarded as 2-3-4 trees by contracting red children into corresponding black nodes, and vice versa.

If we maintain for each node the number of nodes in the subtree rooted at it, then we can query the order of an element (i.e. how many elements are less than it) in log time.

B-Trees