Tree

General Definition of Trees

A tree consists of a set of nodes and a set of edges that connect pairs of nodes. A tree is either empty or consists of a root and zero or more subtrees, each of which is also a tree.

# Binary Tree Illustration
class Tree:
    def __init__(self, value):
        self.key = value
        self.left = None
        self.right = None

Tree Traversals

• Preorder
  Visit the root node first, then recursively do a preorder traversal of the left subtree, followed by a recursive preorder traversal of the right subtree.

• Inorder
  Recursively do an inorder traversal on the left subtree, visit the root node, and finally do a recursive inorder traversal of the right subtree.

• Postorder
  Recursively do a postorder traversal of the left subtree and the right subtree followed by a visit to the root node.

Binary Search Tree

A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left subtree and smaller than the keys in all nodes in that node’s right subtree.

AVL Tree

A balanced binary search tree, keeping track of a balance factor for each node in the tree to maintain the balance of left child and right child.

2-3 Search Tree

A 2-3 search tree is a tree that is either empty or

• A 2-node, with one key (and associated value) and two links, a left link to a 2-3 search tree with smaller keys, and a right link to a 2-3 search tree with larger keys
  
• A 3-node, with two keys (and associated values) and three links, a left link to a 2-3 search tree with smaller keys, a mid- dle link to a 2-3 search tree with keys between the node’s keys, and a right link to a 2-3 search tree with larger keys
  

As usual, we refer to a link to an empty tree as a null link.

Red-black BSTs

Define red-black BSTs as BSTs having red and black links and satisfying the following three restrictions:

• Red links lean left.
  
• No node has two red links connected to it.
  
• The tree has perfect black balance : every path from the root to a null link has the same number of black links.
  

There is a 1-1 correspondence between red-black BSTs defined in this way and 2-3 trees.