1、查找&新增 2、删除 3、数据重复 4、复杂度 5、vs散列表优点
二叉查找树(Binary Search Tree)
支持动态数据集合快速插入、删除、查找：左子树中每个节点值<这个节点<右子树
散列表比二叉查找树更高效，O(1)。哪些地方是散列表做不了，必须要用二叉树来做的呢?
一、查找&新增
查
insert
二、删除
情况1：没有子节点，直接将父节点指向删除节点指针置为null，55
情况2：一个子节点，同上，13
情况3：两个子节点，将节点右子树最小节点，替到删除节点。再删除 18
还可快速查找最大、最小、前驱、后继节点。
重要特性：中序遍历二叉查找树，输出有序数据，时间复杂度O(n)
三、支持重复数据的二叉查找树
对象字段键值(key)构建二叉查找树。对象中其他字段叫作卫星数据。两种办法：
1、链表和动态扩容数组等数据结构，相同数据都存同一节点
2、节点只存一数据。插入数据值相同，放右子树，当作大于。
查时，遇到相同节点不停止，继续在右子树查，遇到叶子节点，才停止。把所有节点都找出来。（删除同理）
四、二叉查找树的时间复杂度分析
(1)退化成链表O(n)。
(2)最理想完全二叉树O(height)。第一层包含1个节点，第二层包含2个节点，第三层包含4个节点，依次类推，节点的个数是n >= 1+2+4+8+...+2^(L-2)+1 n <= 1+2+4+8+...+2^(L-2)+2^(L-1) 范围是[log2(n+1), log2n +1]。O(logn)
五、相比散列表O(logn)优点
1、散列表：无序存储的，二叉查找树：中序遍历O(n)输出有序
2、散列表：扩容耗时，遇到散列冲突，性能不稳定，平衡二叉查找树：性能稳O(logn)
3、散列表：查找因哈希冲突，实际速度不一定比O(logn)快
4、散列表：构造复杂，需考虑散列函数的设计、扩容、缩容、冲突解决（散列表装载因子不能太大，特别是开放寻址法，不浪费空间）
