二叉查找树（Binary Search Tree，BST）
二叉查找树（Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者一颗二叉树的任何节点均满足：
- 若节点的左子树不空，则左子树上所有节点的值均小于这个节点的值；
- 若节点的右子树不空，则右子树上所有节点的值均大于这个节点的值；
- 节点的左、右子树也分别为二叉查找树；
- 没有值相等的节点
如果对一棵二叉查找树进行中序遍历，会得到一个已经将各结点的值按从小到大的顺序排列好的序列，所以也称二叉查找树为二叉排序树。
比如，对上面的二叉查找树进行中序遍历，结果为：10 15 20 25 30 35 40 45 50。
二叉查找树的意义
二分查找很好的解决了查找问题，将时间复杂度从 $O(n)$降到了$O(log_2n)$。 但是二分查找的前提条件是数据必须是有序的，并且具有线性的下标。 对于线性表，可以很好的应用二分查找，但是在插入和删除操作时则可能会造成整个线性表的动荡，时间复杂度达到了$O(n)$。
链表更是没法应用二分查找。
于是我们引入二叉查找树，在理想情况下，其在查找、插入、删除都能够达到$O(log_2n)$的时间复杂度。
性能分析
在二叉查找树中查找节点，理想情况下，每次检查后，待检查的节点数都会减半。
如下图中的二叉查找树，包含了 15 个节点。从根节点开始执行查找算法，第一次比较决定我们是移向左子树还是右子树。对于任意一种情况，一旦执行这一步，我们需要访问的节点数就减少了一半，从 15 降到了 7。同样，下一步访问的节点也减少了一半，从 7 降到了 3，以此类推。
根据这一特点，查找算法的时间复杂度应该是 $O(log_2n)$，简写为 $O(lg n)$。$log_2n = y$，相当于 2y = n。即，如果节点数量增加 n，查找时间只缓慢地增加到 $log_2n$。
下图中显示了 $O(log_2n)$ 和线性增长 $O(n)$ 的增长率之间的区别。时间复杂度为 $O(log_2n)$ 的算法运行时间为下面那条线。
从上图可以看出，$O(log_2n)$ 曲线几乎是水平的，随着 n 值的增加，曲线增长十分缓慢。举例来说，查找一个具有 1000 个元素的数组，需要查询 1000 个元素，而查找一个具有 1000 个元素的二叉查找树，仅需查询不到10 个节点（$log_21024$ = 10）。
而实际上，对于二叉查找树查找算法来说，其十分依赖于树中节点的拓扑结构，也就是节点间的布局关系。下图描绘了一个节点插入顺序为 20, 50, 90, 150, 175, 200 的二叉查找树。这些节点是按照递升顺序被插入的，结果就是这棵树没有广度（Breadth）可言。也就是说，它的拓扑结构其实就是将节点排布在一条线上，而不是以扇形结构散开，所以查找时间也为 O(n)。
当二叉查找树中的节点以扇形结构散开时，对它的插入、删除和查找操作最优的情况下可以达到亚线性的运行时间 $O(log_2n)$。因为当在 BST 中查找一个节点时，每一步比较操作后都会将节点的数量减少一半。尽管如此，如果拓扑结构像上图中的样子时，运行时间就会退减到线性时间 O(n)。因为每一步比较操作后还是需要逐个比较其余的节点。也就是说，在这种情况下，在二叉查找树中查找节点与在数组（Array）中查找就基本类似了。
因此，二叉查找树查找时间依赖于树的拓扑结构。最佳情况是 $O(log_2n)$，而最坏情况是 O(n)。
总结
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，在理想情况下，均为$O(log_2n)$。
- 查找：理想情况/平均情况$O(log_2(n))$，最坏情况$O(n)$。
- 插入：理想情况/平均情况$O(log_2(n))$，最坏情况$O(n)$。
- 删除：理想情况/平均情况$O(log_2(n))$，最坏情况$O(n)$。
二叉查找树的常用操作
查找节点
查找指定值的元素
在二叉查找树bb中查找xx的过程为：
- 若b是空树，则搜索失败，否则：
- 若x等于b的根节点的数据域之值，则查找成功；否则：
- 若x小于b的根节点的数据域之值，则递归搜索左子树；否则:
- 递归查找右子树
使用python实现如下：
def search(root, val):
if root == None:
return False, None
elif val > root.val:
return search(root.right, val)
elif val < root.val:
return search(root.left, val)
else:
return True, root
查找二叉查找树中最小值对应节点
def smallest(self, root: Optional[TreeNode]) -> int:
if not root:
return -1
def dfs(root):
if not root.left:
return root.val
return dfs(root.left)
return dfs(root)
查找二叉查找树中最大值对应节点
def biggest(self, root: Optional[TreeNode]) -> int:
if not root:
return -1
def dfs(root):
if not root.right:
return root.val
return dfs(root.right)
return dfs(root)
插入节点
向一个二叉查找树b中插入一个节点s，过程为：
- 若b是空树，则将s所指结点作为根节点插入，否则：
- 若s.val等于b的根节点的数据域之值，则返回，否则：
- 若s.val小于b的根节点的数据域之值，则把s所指节点插入到左子树中，否则：
- 把s所指节点插入到右子树中（新插入节点总是叶子节点）
def insert(self, root, node):
"""insert inplace"""
if root == None:
root = node
return
if node.val == root.val:
return
elif node.val > root.val:
self.insert(root.right, node)
else:
self.insert(root.left, node)
删除节点
二叉查找树的节点删除操作分以下三种情况：
1 如果待删除的节点是一个叶子节点，那么可以立即删除这个节点
例：删除值为16的节点，因为该节点是叶子节点，因此可以直接删除。
2 如果待删除节点有一个子节点，则要先将当前子节点对应的树上移到待删除节点的父节点下，再删除待删除节点
例：删除值为25的节点，而它下面有且只有一个子节点（这个子节点的值为35）。则在删除前，需要先将该子节点上移到待删除节点的父节点下（该父节点的值为17）。
3 如果待删除节点有两个子节点，则将其右子树的最小值代替此节点的数据，并将其右子树的具有最小值的节点删除
例：删除值为5的节点，要先找到待删除节点的右子树中的最小节点（在这个过程中，用一个临时变量successor，以存储在值为5的节点的右子树中搜索到的最小节点），我们发现，待删除节点的右子树中的最小节点为7，因此用最小节点7替换被删除节点，再删除之前的最小节点7，以维持二叉树结构。
二叉查找树的存储结构实现
对于二叉树，我们还是习惯的选择采用链式存储结构实现。
二叉查找树结点定义
二叉查找树最大的特点，就是他的元素是可以比较大小的。这一点是需要注意的地方。
public class TreeNode<T extends Comparable<T>> {
// 数据域
private T data;
// 左子树
public TreeNode<T> leftChild;
// 右子树
public TreeNode<T> rightChild;
public TreeNode(T data) {
this(null, data, null);
}
public TreeNode(TreeNode leftChild, T data, TreeNode rightChild) {
this.leftChild = leftChild;
this.data = data;
this.rightChild = rightChild;
}
public T getData() {
return data;
}
public TreeNode<T> getLeftChild() {
return leftChild;
}
public TreeNode<T> getRightChild() {
return rightChild;
}
public void setData(T data) {
this.data = data;
}
}
二叉查找树插入实现
有了根节点，我们就可以根据二叉树的性质，从根节点出发，构建出一颗二叉树。
/**
* 树中插入元素
*/
void insert(T value) {
if (value == null) {
return;
}
root = insert(root, value);
}
private TreeNode<T> insert(TreeNode<T> node, T value) {
if (node == null) {
// 树为空,则创建根节点
return new TreeNode<>(value);
} else {
if (compare(node, value) < 0) { // 插入值比根节点小，在左子树继续创建二叉查找树
node.leftChild = insert(node.getLeftChild(), value);
} else if (compare(node, value) > 0) { // 插入值比根节点大，在右子树继续创建二叉查找树
node.rightChild = insert(node.getRightChild(), value);
}
}
return node;
}
private int compare(TreeNode<T> node, T value) {
return value.compareTo(node.getData());
}
根据二叉查找树的特性，我们很容易使用递归实现二叉树的插入操作；总的来说，就是每次插入一个结点，从根节点出发作比较，小的就往左子树插，大的就往右子树插。这和二叉查找树的定义时完全一致的。
二叉查找树查找实现
通过插入操作，我们已经实现了一颗二叉查找树，下面就来看看如何从树中查找元素。
查找最大值与最小值
根据二叉查找树的特点，我们知道在一颗二叉查找树上，最小的值一定在最最左边的结点上，而最大值一定在最最右边的结点上。因此，查找二叉树最值就变得非常容易了。
/**
* 查找最大值
*/
public T findMax() {
if (isEmpty()) return null;
return findMax(root);
}
/**
* 从特定结点开始寻找最大值
*/
private T findMax(TreeNode<T> node) {
TreeNode<T> temp = node;
while (temp.getRightChild() != null) {
temp = temp.getRightChild();
}
return temp.getData();
}
/**
* 查找最小值
*/
public T findMin() {
if (isEmpty()) return null;
return findMin(root);
}
/**
* 从特定结点开始寻找最小值
*/
private T findMin(TreeNode<T> node) {
TreeNode<T> temp = node;
while (temp.getLeftChild() != null) {
temp = temp.getLeftChild();
}
return temp.getData();
}
可以看到，算法实现非常简单，就是不断后移结点找到没有子树的结点，就是最边界位置的结点了。
查找特定值
在二叉查找树中，怎样快速找到一个值为特定元素的结点呢？想想我们是怎样实现结点插入的？这个问题就很简单了。
递归实现，查找特定结点
/**
* find 特定值 递归实现
*/
public TreeNode<T> find(T value) {
if (isEmpty()) {
return null;
} else {
return find(root, value);
}
}
private TreeNode<T> find(TreeNode<T> node, T value) {
if (node == null) {
// 当查找一个不在树中元素时，抛出异常
throw new RuntimeException("the value must not in the tree");
}
if (compare(node, value) < 0) {
// 小于根节点时，从去左子树找
return find(node.getLeftChild(), value);
} else if (compare(node, value) > 0) {
// 大于根节点时，从右子树找
return find(node.getRightChild(), value);
} else {
// 刚好等于，找到了
return node;
// 剩下还有一种情况，就是不等于，也就是所查找的元素不在树中
}
}
查找的实现思路，总体上和插入是一致的；无非就是做不同的操作；这里需要注意的是，为了程序的健壮性，我们还得考虑如果查找的元素不在树中这种情况。
迭代实现，查找特定值
有了前面查找最大值、最小值的经验，我们也可以考虑使用迭代算法实现查找指定元素的算法。
/**
* 查找特定值-非递归实现
*/
public TreeNode<T> findIter(T value) {
TreeNode<T> current = root;
while (current != null) {
if (compare(current, value) < 0) {
current = current.getLeftChild();
} else if (compare(current, value) > 0) {
current = current.getRightChild();
} else {
return current;
}
}
// current为null,说明所查找的元素不在tree里
return null;
}
这里同样测试一下，查找方法的正确性：
System.out.printf("\nfind value %d in mSearchTree \n", 12);
TreeNode mTreeNode = mSearchTree.find(12);
TreeNode mTreeNode_1 = mSearchTree.findIter(12);
System.out.println("递归实现结点 = :" + mTreeNode + ", value=" + mTreeNode.getData());
System.out.println("非递归实现结点= :" + mTreeNode_1 + ", value=" + mTreeNode_1.getData());
System.out.println("\nfind the max value in mSearchTree = " + mSearchTree.findMax());
System.out.println("find the min value in mSearchTree = " + mSearchTree.findMin());
输出：
find value 12 in mSearchTree
递归实现结点 = :com.avaj.datastruct.tree.bst.TreeNode@4b67cf4d, value=12
非递归实现结点= :com.avaj.datastruct.tree.bst.TreeNode@4b67cf4d, value=12
find the max value in mSearchTree = 17
find the min value in mSearchTree = 1
我们分别用递归和迭代两种方式去查找 12，可以看到两次找到是同一个对象，这个对象的值为12；找到的最大值和最小值也是正确的；因此查找功能的实现是正确的。
二叉查找树删除节点实现
从二叉查找树中，删除一个结点可以算是最复杂的操作了，主要是因为所要删除的结点，所处的位置被删除后，依然需要保持整棵树依然为二叉树，因此需要就不同的情况就像分析。
就拿我们上面创建的这颗二叉树来说，如果要删除的结点是1,7,11,17 这样的叶子结点，就很容易了；让其父结点指向为null即可；而如果是4,5 这样包含一颗子树的结点，换个角度来说，这其实就是单向链表，从单向链表中间位置删除一个结点也比较容易；最麻烦的就是如果要删除的结点是10,8,3,12 这类结点包含左右子树，我们就需要从左子树中找一个最大值，或者是右子树中的最小值来替代这个值。总结一下删除结点的操作：
- 叶子结点：直接删除，其父结点指向null
- 包含一个孩子的结点 ：父结点指向要删除结点的自结点（相当于链表中间删除一个元素）；
- 包含左右子树的结点：右子树最小值或左子树最大值替换此结点
结合以上分析，得出从二叉查找树中删除结点的实现。
/**
* 从树中删除值为value 的特定结点
*/
public void delete(T value) {
if (value == null || isEmpty()) {
return;
}
root = delete(root, value);
}
private TreeNode<T> delete(TreeNode<T> node, T value) {
// 结点为空，要出删除的元素不在树中
if (node == null) {
return node;
}
if (compare(node, value) < 0) { // 去左子树删除
node.leftChild = delete(node.getLeftChild(), value);
} else if (compare(node, value) > 0) { // 去右子树删除
node.rightChild = delete(node.getRightChild(), value);
} else { // 要删除的就是当前结点
if (node.getLeftChild() != null && node.getRightChild() != null) {// 被删除的结点，包含左右子树
T temp = findMin(node.getRightChild()); // 得到右子树的最小值
node.setData(temp); //右子树最小值替换当前结点
node.rightChild = delete(node.getRightChild(), temp); // 从右子树删除这个最小值的结点
} else {// 被删除的结点，包含一个子树或没有子树
if (node.getLeftChild() != null) {
node = node.getLeftChild();
} else {
node = node.getRightChild();
}
}
}
return node;
}
这里选择使用右子树的最小值替换，是因为删除这个最小值的结点会比较容易，因为他一定是不会是一个包含左右子树的结点。
计算二叉查找树的高度
最后，再来看看如何计算一颗二叉搜素树的度。
# RECURSIVE DFS
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root:
return 0
return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))
Reference
- https://en.wikipedia.org/wiki/Binary_search_tree
- 二叉查找树(BST)的基本概念及常用操作 - https://blog.csdn.net/John_xyz/article/details/79622219
- 数据结构-二叉查找树的实现 - https://www.jianshu.com/p/8baf54e53c26
- 二叉查找树 - https://www.cnblogs.com/gaochundong/p/binary_search_tree.html