二叉查找树（二叉搜索树或二叉排序树）是一种数据结构。采用了图的树形结构。数据存储于二叉查找树的各个结点中。
二叉查找树的示例如下图：结点中的数字就是存的数据。（这里以不存在相同的数字为例）
二叉查找树性质：
1.每个结点的值大于其左树上任意结点的值
2.每个结点的值小于其右树上任意结点的值
比如9大于其左树上的3和8。
根据这两个性质可以得出结论：
二叉查找树的最小结点从顶端开始，往其左树的末端寻找。此处最小值是3。
二叉查找树的最大结点从顶端开始，网右树的末端寻找。此处的最大值是28。
二叉树添加数据：
假设往当前二叉树里面添加一个数据，比如添加数字1。
先从顶端开始比较：
因为 1 < 15 ,所以往左下位置继续寻找
接下来和9比较，因为1 < 9 ，所以继续往左下位置寻找
接下来和和3比较，因为1 < 3 ,所以继续向左下位置寻找
最终左下没有值了，得到的结果是
接下来操作再添加一位数字4
先将4和15比较4 < 15 ,往左树寻找
4 < 9 ,再往左树寻找，
4 > 3 ,往右树寻找，
4 < 8 ,将4添加到8的左树位置，添加完成。
二叉树删除数据
尝试性删除结点28，
删除结果如下图
下面尝试删除带子节点的结点8
删除之后效果
下面删除带子树的节点9
删除之后，先将左树上最大结点4放在被删除的结点位置（这里树的结构没有达到最优解，那么还需要继续递归调整结点的操作）
（备注说明：将左树中的最大结点和右树中的最小结点放在9的原有置都可以）
当前情况下将4放在该位置已经是最优解，因此不用再做调整。
数据查找：
查找数据也是从顶端开始和被查找值的大小进行对比，12 < 15 ,所以需要查找左树。
12 > 4 ,查找右树
到此查到结束。
时间计算
因为二叉查找树有前面两个性质，所以在查找数据或者寻找合适添加数据位置时候，只要将其和现有数据比较大小，就可以根据比较结果得知该往那边移动了。
比较的次数取决于树的高度。所以如果结点数目为n,而且树比较均衡，比较大小和移动的次数最多就是log2n
因此时间复杂度为O（logn）。但是，如果树的形状朝单侧纵向延伸，树就变得很高，此时的时间复杂度就变成了O（n）。
应用
有很多以二叉查找树为基础的扩展数据结构。比如“平衡二叉查找树”。这种结构可以修正形状不均衡的树，让其始终保持均衡的形态，以提高查找效率。
虽然二叉查找树中的一个结点最多有两个子结点，但我们可以把子结点数扩展为m.
像这种结点数可以自由设定，并且形状均衡的树叫做B树。
