The search tree data structure supports many dynamic-set operations, includingSEARCH,MINIMUM,MAXIMUM,PREDECESSOR,SUCCESSOR,INSERT, andDELETE. Thus, we can use a search tree both as a dictionary and as a priority queue.
1.Definition：
a binary search tree (BST), sometimes also called anordered or sorted binary tree, is a node-based binary tree
data structure which has the following properties:
- The left subtree of a node contains only nodes with keys less than the node‘s key.
- The right subtree of a node contains only nodes with keys greater than the node‘s key.
- The left and right subtree each must also be a binary search tree.
- There must be no duplicate nodes.
Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.
The major advantage of binary search trees over other data structures is that the related sorting algorithms and search algorithms such as in-order traversal can be very efficient.
Binary search trees are a fundamental data structure used to construct more abstract data structures such as sets, multisets, and associative arrays.
Binary-search-tree property：
Let x be a node in a binary search tree. If y is a node in the left subtree of x, then y.key < x.key. If y is a node in the right subtree of x, then y.key > x.key.
2. operations
2.1 Traversal（遍历）
遍历分为三种，分别是
- inorder tree walk,print out all the keys in a binary search tree in sorted order by a simple recursive algorithm.
- preorder tree walk ,prints the root before the values in either subtree.
- postorder tree walk ,print the root after the values in its subtrees.
inorder tree walk的伪代码：
定理：
2.2 Querying a binary search tree
We often need to search for a key stored in a binary search tree. Besides theSEARCHoperation, binary search trees can support such queries asMINIMUM,MAXIMUM,SUCCESSOR, andPREDECESSOR.
In this section, we shall examine these operations and show how to support each one in time O(h) on any binary search tree of height h.
2.2.1 Search
We use the following procedure to search for a node with a given key in a binary search tree. Given a pointer to the root of the tree and a key k, TREE-SEARCH returns a pointer to a node with key k if one exists; otherwise,
it returns NIL.
在以x为根节点的树中搜索k的伪代码：
上面的代码是以递归法写的，我们也可以利用一个while语句以迭代的方式实现，而且在大多数计算机中迭代的形式要比递归效率更高。
迭代伪代码：
2.2.2 Minimum and Maximum
寻找最小数x伪代码：
找最大数x伪代码：
2.2.3 Successor and predecessor
寻找x元素后继的伪代码：
伪代码中可以分为两个部分，1-2和3-7两部分。
第一部分表示：如果x存在右孩子，那么右边最小的那个肯定是x的后继（如下图中15的后继是17）
第二部分表示：如果x不存在右孩子，那么寻找他的后继就必须从父辈中找，此时又分为两情况。
1.当x为其parent的左孩子时，则后继即为x.p. while条件(x==y.right)就是判断这个，此时不进入循环，此时的情况如2的后继是3. 2.当x为其parent的右孩子时，则进入循环，多次循环找到后继，此时的情况如13的后继是15.
（注意while判断里面的y不等NIL是防止x为根，假如x为树根且不存在右孩子的话得出的结果是y==NIL）
最后得出的定理是：
We can implement the dynamic-set operations SEARCH, MINIMUM, MAXIMUM,SUCCESSOR, and PREDECESSOR so that each one runs in O(h) time on a binary search tree of height h.
2.3 Insertion
Like the other primitive operations on search trees, the procedure TREE-INSERT runs in O(h)time on a tree of height h.
插入操作比较简单就直接上伪代码了：
往树T中插入z
2.4 Deletion
Like the other primitive operations on search trees, the procedure Deletion runs in
O(h)time on a tree of height h.
删除操作实现比较复杂，我们可以把它分为四种情况：
1.如果z没有左孩子，这样我们就用z的右孩子取代z的位置。如果z也没有右孩子的话，那么z就没有孩子可以直接删除。
2.如果z仅有一个孩子，排除上面的情况，那么z只有左孩子，我们可以用他的左孩子取代它的位置
3.如果z有两个孩子，则此时又要分两种情况。首先我们找到z的后继y
a.如果y是z的右孩子，那么我们就用y取代z
b.如果y是z的右子树中的一个而不是z的右孩子，那么我们首先将z的右孩子和y交换位置，然后再用y取代z
下面这张图及为四种情况。
伪代码实现：
首先我们实现一个 TRANSPLANT(T,u,v) 即用v取代u
接下来实现整体的删除伪代码：
References：