******************
Binary search tree
******************

Motivation
==========
The motivation behind using a Binary Search Tree (BST) as a data structure lies
in its ability to efficiently support key-based operations, such as searching,
insertion, and deletion, while maintaining a sorted order of elements.

Definition
==========
A binary search tree (BST) is a binary tree, in which for every node, its left
subtree has values less than the node's value, and every node's right subtree
has values greater than the node's value.

Applications
============
+ Map ADT

  * Stores key-value pairs

+ Set ADT

  * Stores a set of elements (keys)

Behaviors
=========
+ Search
+ Insert
+ Remove
+ Traversal: Visit all nodes in a tree in a certain order

  * in-order: for each node: left-subtree, self, right-subtree

    - provides an ascending-ordered sequence of values

  * pre-order: for each node: self, left-subtree, right-subtree
  * post-order: for each node: left-subtree, right-subtree, self

Implementation Details
======================
+ Algorithms that happens from top to bottom

  Easy to implement either iteratively or recursively

  * search
  * insert

+ Algorithms that happens from bottom to top

  Easy to implement recursively; Hard to implement iteratively (must use stack)

  * subtree removal (may be used in the destruction of a tree)
  * find min node or find max node (part of remove)
  * in-order traversal
  * pre-order traversal

Drawbacks and Solutions
=======================
+ Algorithm efficiency depends on the average height of the BST
+ BST may degrade a very unbalanced form or even to a linked list
+ Solutions

  * Randomize the order of insertion
  * Add a balancing mechanism

    - self-balancing tree
    - external balancing (FYI)

  * Move the most recently accessed node toward the root

    * Only optimize the search performance for a specific access pattern
    * No guarantee for the worst case
    * Splay tree

Applications of BST
===================
+ Indexing: store a set of references in a BST and use the key as the search
  key
+ Tree Sort: sort a sequence of numbers by building a BST and then traversing
  it in-order
+ Tree Map: store a set of (key, value) pairs in a BST and use the key as the
  search key
+ Tree Set: store a set of elements in a BST and use the element as the search
  key

Important Binary Search Tree Variations
---------------------------------------
+ Self-balancing BSTs

  * AVL tree
  * Red-black tree

+ Self-adjusting BSTs (other than self-balancing)

  * Splay tree
  * Treap