二叉搜索树

中序遍历就是从小到大遍历值。

# 二叉搜索树 (BST) 的性质

二叉搜索树，也叫二叉排序树，它首先是棵二叉树，但多了几条规则，让查找数据变得很快。

1.  首先，它是一棵二叉树，每个节点最多有两个子节点（左子节点和右子节点）。

2.  核心的排序规则是：对于树里的任意一个节点：
    *   它左子树里所有节点的值，都比这个节点的值小。
    *   它右子树里所有节点的值，都比这个节点的值大。

3.  它的左右子树，也必须分别是二叉搜索树。这条规则保证了整棵树从上到下都是有序的。

4.  在经典的定义里，二叉搜索树不包含重复的值。

5.  对二叉搜索树进行中序遍历（左 -> 根 -> 右），你会得到一个升序排列的节点值序列。这个特性非常重要，经常被用来检查一棵树是不是二叉搜索树。

### 操作效率

-   平均情况：如果树长得比较匀称（平衡），查找、插入和删除操作的时间复杂度都是 O(log n)。
-   最坏情况：如果树长歪了，退化成一条链表（比如你按 1、2、3、4 的顺序依次插入），那这些操作的时间复杂度就会变成 O(n)。