Binary Search Tree

• 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
• 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
• 任意節點的左、右子樹也分別為二元搜尋樹；
• 沒有鍵值相等的節點。

Traversing a BST

In-order

left -> parent -> right

INORDER-TREE-WALK (x)
    if x!= NIL
        INORDER-TREE-WALK (x, left)
        print x.key
        INORDER-TREE-WALK (x, right)

In-order with stack

void inOrder(struct Node *root) 
{ 
    stack<Node *> s; 
    Node *curr = root; 
  
    while (curr != NULL || s.empty() == false) 
    { 
        /* Reach the left most Node of the 
           curr Node */
        while (curr !=  NULL) 
        { 
            /* place pointer to a tree node on 
               the stack before traversing 
              the node's left subtree */
            s.push(curr); 
            curr = curr->left; 
        } 
  
        /* Current must be NULL at this point */
        curr = s.top(); 
        s.pop(); 
  
        cout << curr->data << " "; 
  
        /* we have visited the node and its 
           left subtree.  Now, it's right 
           subtree's turn */
        curr = curr->right; 
  
    } /* end of while */
} 

In-order with two pointers

t = tree.Root;
while (true) {
  while (t.Left != t.Right) {
    while (t.Left != null) {   // Block one.
      t = t.Left;
      Visit(t);
    }
    if (t.Right != null) {     // Block two.
      t = t.Right;
      Visit(t);
    }
  }

  while (t != tree.Root && (t.Parent.Right == t || t.Parent.Right == null)) {
    t = t.Parent;
  }
  if (t != tree.Root) {        // Block three.
    t = t.Parent.Right;
    Visit(t);
  } else {
    break;
  }
}

pre-order

parent -> left -> right

PREORDER-TREE-WALK (x)
    if x!= NIL
        print x.key
        PREORDER-TREE-WALK (x, left)
        PREORDER-TREE-WALK (x, right)

post-order

left -> right -> parent

POSTORDER-TREE-WALK (x)
    if x!= NIL
        POSTORDER-TREE-WALK (x, left)
        POSTORDER-TREE-WALK (x, right)
        print x.key

Operations

• search(Node x, key k)
• treeMinimum(Node x) and
• treeMaximum(Node x)
• treeSuccessor(Node x) and
• treePredecessor(Nodex)
• insert(BST T, Node z) and
• delete(BST T, Node z)