绑定完请刷新页面
取消
刷新

分享好友

×
取消 复制
Java集合源码分析之基础(四):二叉排序树
2020-04-29 09:30:03

解决查询速度慢的方案除了哈希表外,还可以使用二叉排序树。我们知道,查询慢主要是因为不知道元素的位置,使用hash函数映射虽然解决了问题,但其并不稳定,当出现大量的哈希碰撞后其表现更像一个链表,查询速度大大降低。

二叉排序树的方案则是使元素有序,这样便可以使用二分法进行查找了,虽然效率相比hash函数低一些,但可以通过AVL树红黑树等增加稳定性。

HashMapJDK1.8的实现中,就结合了哈希表的高效和红黑树的稳定,我们之后会详细分析其实现。

定义

二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一棵空树,或者是具有下列性质的二叉树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值

  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值

  • 它的左、右子树也分别为二叉排序树

如下就是一棵简单的二叉排序树:


 二叉排序树示意图


当对这棵树进行中序遍历时,其结果将按照从小到大排序。

查询操作

二叉排序树的查找时间复杂度为O(lg n),查找使用二分法。要在上图中找到元素37,只需要四次操作即可。

首先,找到根元素22,37比22大,所以淘汰左子树,再找到35,淘汰左子树,再找到41,进入左子树,得到37。可以看到其速度比挨个对比高了很多。

插入操作

二叉排序树的插入操作和查询类似,也需要通过二分法进行查找,找到合适的位置再插入元素,所以其插入速度相比链表较慢。

删除操作

从二叉排序树中删除一个元素主要分为三种情况。

例如要从下面这个二叉排序树中删除一个元素:

二叉排序树


  1. 删除的元素是叶结点,这时可以直接删除它。比如要删除值为1的元素,删除它对树没有任何影响。

  2. 删除的元素仅有左孩子或者仅有右孩子时,直接让其孩子顶替它即可。比如要删除元素35,只需要用41顶替它即可。

  3. 删除的元素既有左孩子又有右孩子,这时删除它相对复杂。一种好的方式是找到它的前驱或者后继来代替它。比如要删除元素9,就用6或者13代替它即可。

问题

一棵普通的二叉排序树也会出现不平衡问题,如果插入的数据都在树的一侧,就会使得树的深度迅速增大,每次二分查找可以排除的数据很少,从而查询速度严重下降,比如下方这棵树:

不平衡的排序树


要查找值为2的元素,使用二分法和使用链表速度差不多。

为了解决这种问题,就需要在元素插入时即进行修正,后续介绍的AVL树和红黑树就是两种不同的解决方案。

今天周五了,放松一下,知识非常简单,你get√了么?下周的知识要花费不少力气哈~


更多内容正在火速连载中,感谢您的关注!

分享好友

分享这个小栈给你的朋友们,一起进步吧。

飞机酱的IT之旅
创建时间:2020-04-28 18:20:39
飞机酱是一个Android开发攻城狮,除了要攻陷Android外,还会进攻数据结构、算法、网络、计算机系统等方面的知识。关注我,一起学IT吧。
展开
订阅须知

• 所有用户可根据关注领域订阅专区或所有专区

• 付费订阅:虚拟交易,一经交易不退款;若特殊情况,可3日内客服咨询

• 专区发布评论属默认订阅所评论专区(除付费小栈外)

栈主、嘉宾

查看更多
  • 大大纸飞机
    栈主

小栈成员

查看更多
  • ☀️
  • 小雨滴
  • 人工智能频道
  • 栈栈
戳我,来吐槽~