专栏首页Java阿呆java源码之二叉查找树与二叉平衡树

java源码之二叉查找树与二叉平衡树

二叉排序树

解决查询速度慢的方案除了哈希表外,还可以使用二叉排序树。查询慢主要是因为不知道元素的位置,使用hash函数映射虽然解决了问题,但其并不稳定,当出现大量的哈希碰撞后其表现更像一个链表,查询速度大大降低。 二叉排序树的方案则是使元素有序,这样便可以使用二分法进行查找了,虽然效率相比hash函数低一些,但可以通过AVL树、红黑树等增加稳定性。

定义

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

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
  • 它的左、右子树也分别为二叉排序树

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

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

查询操作

二叉排序树的查找时间复杂度为O(lg n),查找使用二分法。要在上图中找到元素37,只需要四次操作即可。 首先,找到根元素22,37比22大,所以淘汰左子树,再找到35,淘汰左子树,再找到41,进入左子树,得到37。可以看到其速度比挨个对比高了很多。

插入操作

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

删除操作

从二叉排序树中删除一个元素主要分为三种情况。 例如要从下面这个二叉排序树中删除一个元素:

  1. 删除的元素是叶结点,这时可以直接删除它。比如要删除值为1的元素,删除它对树没有任何影响。
  2. 删除的元素仅有左孩子或者仅有右孩子时,直接让其孩子顶替它即可。比如要删除元素35,只需要用41顶替它即可。
  3. 删除的元素既有左孩子又有右孩子,这时删除它相对复杂。一种好的方式是找到它的前驱或者后继来代替它。比如要删除元素9,就用6或者13代替它即可。

缺陷

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

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

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

平衡二叉树(AVL Tree)

二叉排序树很好的平衡了插入与查找的效率,但不平衡的二叉排序树效率大打折扣。AVL树就是一种解决此问题的方案。

定义

平衡二叉树(Self-Balancing Binary Search Tree 或Height-Balanced Binary Search Tree),是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1 。它是一种高度平衡的二叉排序树。意思是说,要么它是一棵空树,要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1 。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor),那么平衡二叉树上所有结点的平衡因子只可能是-1 、0 和1。 如下图就是一棵AVL树:

实现原理

平衡二叉树构建的基本思想就是在构建二叉排序树的过程中,每当插入一个结点时,先检查是否因插入而破坏了树的平衡性,若是,则找出最小不平衡子树。在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。最小不平衡子树是指距离插入结点最近的,且平衡因子的绝对值大于1 的结点为根的子树。 下面通过一个实例,了解平衡二叉树的构建过程。 假如我们要将数组int[] a = {3, 2, 1, 4, 5, 6, 7, 10, 9}构建成一棵二叉排序树,如果直接按照二叉排序树的定义,会得到下面的结果:

以下为创建过程:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • java源码之树与二叉树

    树(Tree)是n(n≥0) 个结点的有限集。n=0 时称为空树。在任意一棵非空树中:

    Java阿呆
  • 线程基本概念

    一般来说创建线程有三种方式: 方式一:继承java.lang.Thread类,覆写run()方法 方式二:实现java.lang.Runnable接口,实现ru...

    Java阿呆
  • 线程池

    1、任务优先向CorePool中提交,创建核心线程执行任务 2、在CorePool满了之后,任务被提交提交到任务队列,等待线程池空闲 3、在任务队列满了之后,...

    Java阿呆
  • 大数据新机遇,教育系统将建设完整安全体系

    随着网络规模的扩大,Web应用承载的业务系统越来越复杂,Web系统也受到越来越多的攻击和威胁。大数据时代,网络安全也直接影响到每一个用户的个人信息安全,但是大数...

    安恒信息
  • 【干货】史上最好的排序和数据结构入门

    工作已经有一段时间了,有的时候会跟同事们打趣:“如果你让我现在去手写一个快速排序,我怕是真的写不出来”。

    Java3y
  • 使用PHP实现数组的笛卡尔积来处理商品规格

    在优化商城项目的时候,选择将商品的内容、规格、库存和价格分三个表来写。将多个规格的id合并存在一个字段中,按照从小到大的顺序来排列,使用逗号分隔

    沈唁
  • 基于Anaconda实现网络安装

    anaconda是RedHat、CentOS、Fedora等Linux发行版的安装管理程序。它可以提供文本、图形等安装管理方式,并支持Kickstart等脚本提...

    用户1456517
  • Java集合从菜鸟到大神演变

    先来看一张集合概况图,这里从上到下列举了几个最经常用的集合 ? 1、集合接口 java.util.Collection 是一个集合接口。它提供了对集合对象进行基...

    Java技术栈
  • 设计模式行为型:观察者模式(ObserverPattern)

    定义对象之间的一种一对多依赖关系,使得每一个对象发生状态的变化时,其相关依赖对象皆得到通知并被自动更新,又称为发布-订阅模式、模型-视图模式、源-监听器模式或从...

    码农架构
  • Kubernetes 学习笔记——使用 Heml 安装和使用 OpenFaaS

    下载 Kubernetes 的 OpenFaaS 驱动程序 faas-netes:

    coding01

扫码关注云+社区

领取腾讯云代金券