二叉搜索树

二叉搜索树是一种有用的数据结构，它的特征是，把数据组织成一个分叉的树状结构，每个节点最多有两个子节点，对于每个节点，它不小于左边的子节点，不大于右边的子节点
二叉搜索树有很多有用的特性。
我们把数据按照一定的特性组织，可以形成一种叫做二叉搜索树的数据结构——对于一个随便给出的序列
[8, 7, 4, 10, 15, 12, 13, 2, 6, 11]
我们从 8 开始——如果序列已经排好了，选择第一个元素并不会构造一棵太好的二叉树。好坏取决于树的高度，如果二叉树又高又稀疏，通常它不是很好的结构，如果二叉树又矮又满，它是比较好的树，原因在于，一棵二叉树如果缀满了节点，理论上可以表达 个节点，这样的既能充分利用内存资源，又保证了很好的查询插入删除的操作速度。

一般来说，数据结构都涉及到增删改查四大操作。

我们知道线性表的增删改查的基本特性：

• 查找和插入： 线性顺序存储表(C++ 的vector），查找一个元素的方法是从表的 0 下标开始一次遍历，最坏的情况下要查到表尾——如果元素正好在表尾或者不存在，用渐进号表示是 O(n) 时间复杂度；
  线性表索引一个元素可以用语言特性的下标索引方法在常数时间内直接访问到；
  如果是链式的结构，则索引一个元素总是需要从表头开始逐步抵达下一个的方式抵达。
  算法理论中用 O(n) 表示一个算法的复杂度的上界, n表示输入规模。
• 删除： 从一个表中删除元素的方式，一般是先找到它，所以它和查询操作有着类似的时间复杂度,对于线性表，如果某个元素被删除，那么它需要将后面地元素逐个左向移动占上这个被空出的空间
  位置，保证线性表的顺序特征。插入有着和删除类似的特性。

综合线性表的特征，它不适合大规模的数据存储，检索效率不能忍受，除非你不需要进行检索。
人们为了更好地查询数据，发明了很多数据结构。
二叉搜索树，顾名思义，就是为了检索而生的数据结构。
它背后的数学原理是对数函数缓慢增长的特性。二叉树对应的对数函数一个2为底的对数函数 , x = 0 时 y = 0, 当 x = 32 时, y = 5, 当 x 增加一百万倍 , y 的值出人意料地才增长到 19.93 , 略小于 20。 想要 y 增加 100， x 得是个天文数字(

组织好的二叉搜索树无论是查找，插入和删除，操作的时间复杂度就正比于树的高度，由于现实世界的数据量远远小于 ，我们可以认为这是一个常数时间的操作

二叉搜索树的查找
查找的方法很简单，只需要从树根开始查询，如果查到就返回，否则判断关键字是否大于当前的节点值，如果大于，则往右子树查找，否则往左子树上查找。

这种检索的方法可以跳过绝大多数的节点，从而大大节约了时间。

二叉树的中序遍历是个排序

延伸

将二叉树延伸成多叉树。如果树的子节点不确定数量，数据则被组织成一个多叉树，多叉树最典型的应用就是操作系统的文件目录结构。
多叉树的表达和二叉树稍有不同，二叉树有明确的左右节点，一般用左右节点表示；
多叉树则表示成一个子节点列表，它的遍历和二叉树是类似的。

对比二叉树，有前中后三种序的遍历，多叉树理论上有更多的顺序遍历，但是只有前序遍历比较有意义。

C++ 多叉树节点的表达:

struct Node {
    int val;
    vector<Node*> children;

    Node() {}
    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};