二叉排序树

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

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

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

定义

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

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

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

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

如下就是一棵简单的二叉排序树:
image
当对这棵树进行中序遍历时,其结果将按照从小到大排序。

查询操作

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

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

插入操作

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

删除操作

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

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

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

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

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

问题

一棵普通的二叉排序树也会出现不平衡问题,如果插入的数据都在树的一侧,就会使得树的深度迅速增大,每次二分查找可以排除的数据很少,从而查询速度严重下降,比如下方这棵树:
image
要查找值为2的元素,使用二分法和使用链表速度差不多。

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

坚持原创技术分享,您的支持将鼓励我继续创作!
0%