二叉搜索树

定义：二叉搜索树（英语：Binary Search Tree），也称为二叉查找树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不空，则左子树上所有节点的值均小于等于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树

二叉搜索树平均情况下插入、查找、删除都是 $O(logN)$ 的复杂度，有点像二分搜索的感觉

当一个二叉搜索树是平衡的时候，其实际运行速度是最快的。这里的平衡指的是左右子树高度不超过 1。

下面是两个不平衡的二叉搜索树