【算法打卡60天】Day21二叉树基础（下）：有了如此高效的散列

第21天
学习内容 : 二叉树基础（下）：有了如此高效的散列表，为什么还需要二叉树？（二）

1.支持重复数据的二叉查找树
那如果存储的两个对象键值相同，这种情况该怎么处理呢？
第一种：二叉查找树中每一个节点不仅会存储一个数据，因此我们通过链表和支持动态扩容的数组等数据结构，把值相同的数据都存储在同一个节点上。
第二种：每个节点仍然只存储一个数据。在查找插入位置的过程中，如果碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。

2.二叉查找树的时间复杂度分析
时间复杂度其实都跟树的高度成正比，也就是 O(height)。

平衡二叉查找树的高度接近 logn，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)。

本文参考【极客时间】专栏《数据结构与算法之美》。