coding……
但行好事 莫问前程

Java编程拾遗『排序二叉树』

在HashMap那篇文章讲过,在Java8中,HashMap是通过数组 + 链表 + 红黑树组织的,当链表中元素个数大于8时,会将链表转化成红黑树。而且Java API中TreeMap也是通过红黑树实现的,所以讲解红黑树,对于我们更好的了解源码实现有着重要的意义。红黑树也是一种特殊的排序二叉树,所以本篇文章先来介绍一下排序二叉树这一数据结构的相关细节,然后再用一片文章介绍一下红黑树数据结构以及Java API中红黑树的实现。

1. 基本概念

1.1 树

(Tree)是一种抽象数据类型或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  • 每个节点有零个或多个子节点;
  • 没有父节点的节点称为根节点;
  • 每一个非根节点有且只有一个父节点;
  • 除了根节点外,每个子节点可以分为多个不相交的子树

 在树中,存在以下术语:

  • 节点的度:一个节点含有的子树的个数称为该节点的度
  • 树的度:一棵树中,最大的节点的度称为树的度
  • 叶节点终端节点:度为零的节点
  • 非终端节点分支节点:度不为零的节点
  • 父亲节点父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点
  • 孩子节点子节点:一个节点含有的子树的根节点称为该节点的子节点
  • 兄弟节点:具有相同父节点的节点互称为兄弟节点
  • 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推
  • 深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0
  • 高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0
  • 堂兄弟节点:父节点在同一层的节点互为堂兄弟
  • 节点的祖先:从根到该节点所经分支上的所有节点
  • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙
  • 森林:由m(m>=0)棵互不相交的树的集合称为森林

1.2 二叉树

二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序,不能随意颠倒。

1.3 排序二叉树

排序二叉树(sorted binary tree),也称为二叉查找树、二叉搜索树有序二叉树,是指一棵空树或者具有下列性质的二叉树:

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;
  • 任意节点的左、右子树也分别为二叉查找树;
  • 没有键值相等的节点。

2. 基本算法

基于上述排序二叉树的特点,下面看一下排序二叉树的基础算法。

2.1 遍历

2.1.1 二叉树遍历

二叉树的遍历可分为深度优先遍历和广度优先遍历,深度优先遍历又可以细分为前序遍历、中序遍历和后序遍历。如果把左节点和右节点的位置固定不动,那么根节点放在左节点的左边,称为前序(pre-order)、根节点放在左节点和右节点的中间,称为中序(in-order)、根节点放在右节点的右边,称为后序(post-order)对广度优先而言,遍历没有前序中序后序之分:给定一组已排序的子节点,其“广度优先”的遍历只有一种唯一的结果

深度优先遍历

  • 前序遍历(Pre-Order Traversal)

指先访问根,然后访问子树的遍历方式,如下图所示:

上图前序遍历结果为:F、B、A、D、C、E、F、G、I、H

  • 中序遍历(In-Order Traversal)

指先访问左子树,然后访问根,最后访问右子树的遍历方式

上图中序遍历结果为:A、B、C、D、E、F、G、H、I

  • 后序遍历(Post-Order Traversal)

指先访问子树,然后访问根的遍历方式

上图中序遍历结果为:A、C、E、D、B、H、I、G、F

广度优先遍历

和深度优先遍历不同,广度优先遍历会先访问离根节点最近的节点,二叉树的广度优先遍历又称按层次遍历。

上图广度优先遍历结果为:F、B、G、A、D、I、C、E、H

2.1.2 排序二叉树遍历

对于排序二叉树的遍历,我们一般指上面讲的中序遍历,通过遍历可以得到一个从小到大的序列。算法如下:

  • 访问左子树
  • 访问当前节点
  • 访问右子树

比如,遍历访问下面的二叉树:

 从根节点开始,但先访问根节点的左子树,一直到最左边的节点,所以第一个访问的是1,1没有右子树,返回上一层,访问3,然后访问3的右子树,4没有左子树,所以访问4,然后是4的右子树6,依次类推,访问顺序就是有序的:1、3、4、6、7、8、9。

2.2 查找

排序二叉树查找比较方便,根据排序二叉树左子树元素总是小于父节点,右子树元素总是大于父节点的特点,在二叉搜索树b中查找x的过程为:

  1. 若b是空树,则搜索失败,否则:
  2. 若x等于b的根节点的数据域之值,则查找成功;否则:
  3. 若x小于b的根节点的数据域之值,则搜索左子树;否则:
  4. 查找右子树。

这个步骤与在数组中进行二分查找或者说折半查找的思路是类似的,如果二叉树是比较平衡的,类似上图中左边的二叉树,则每次比较都能将比较范围缩小一半,效率很高。此外,在排序二叉树中,可以方便的查找最小最大值,最小值即为最左边的节点,从根节点一路查找左孩子即可,最大值即为最右边的节点,从根节点一路查找右孩子即可。

2.3 插入

在排序二叉树中,插入元素首先要找插入位置,即新节点的父节点,向一个二叉搜索树b中插入一个节点s的算法,过程为:

  1. 若b是空树,则将s所指节点作为根节点插入,否则:
  2. 若s->data等于b的根节点的数据域之值,则返回,否则:
  3. 若s->data小于b的根节点的数据域之值,则把s所指节点插入到左子树中,否则:
  4. 把s所指节点插入到右子树中。(新插入节点总是叶子节点)

依次插入7, 3, 4, 1, 9, 6, 8的过程,这个过程如下图所示:

2.4 删除

在二叉查找树删去一个结点,分三种情况讨论:

  1. 若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针直接删除即可
  2. 若*p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树(当*p是左子树)或右子树(当*p是右子树)即可,作此修改也不破坏二叉查找树的特性。
  3. 若*p结点的左子树和右子树均不空。在删去*p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:其一是令*p的左子树为*f的左/右(依*p是*f的左子树还是右子树而定)子树,*s为*p左子树的最右下的结点,而*p的右子树为*s的右子树;其二是令*p的直接前驱(in-order predecessor)或直接后继(in-order successor)替代*p,然后再从二叉查找树中删去它的直接前驱(或直接后继)。

下面分别来看一下

如果节点为叶子节点,则很简单,可以直接删掉,修改父节点的对应孩子为空即可。

如果节点只有一个孩子节点,则替换待删节点为孩子节点,或者说,在孩子节点和父节点之间直接建立链接。比如说,在下图中,左边二叉树中删除节点4,就是让4的父节点3与4的孩子节点6直接建立链接。

如果节点有两个孩子,则首先找该节点的后继(根据之前介绍的后继算法,后继为右子树中最小的节点,这个后继一定没有左孩子),找到后继后,替换待删节点为后继的内容,然后再删除后继节点。后继节点没有左孩子,这就将两个孩子的情况转换为了叶子节点或只有一个孩子的情况。

比如说,在下图中,从左边二叉树中删除节点3,3有两个孩子,后继为4,首先替换3的内容为4,然后再删除节点4。

3. 平衡排序二叉树

从前面的描述中可以看出,排序二叉树的形状与插入和删除的顺序密切相关,极端情况下,排序二叉树可能退化为一个链表,比如说,如果插入顺序为:1 3 4 6 7 8 9,则排序二叉树形状为:

退化为链表后,排序二叉树的优点就都没有了,即使没有退化为链表,如果排序二叉树高度不平衡,效率也会变的很低。所以为了解决这种问题,平衡二叉排序树就出现了。平衡二叉排序树Balanced Binary Tree)是一种结构平衡的二叉排序树,即叶节点高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。最早被发明的平衡二叉搜索树为AVL树(名字源于它的发明者G.M. Adelson-Velsky 和 E.M. Landis),在他们的算法中,在插入和删除节点时,通过一次或多次旋转操作来重新平衡树。初次之外,常见的平衡排序二叉树还有:

在TreeMap的实现中,用的并不是AVL树,而是红黑树,与AVL树类似,红黑树也是一种平衡的排序二叉树,也是在插入和删除节点时通过旋转操作来平衡的,但它并不是高度平衡的,而是大致平衡的,所谓大致是指,它确保,对于任意一条从根到叶子节点的路径,没有任何一条路径的长度会比其他路径长过两倍。红黑树减弱了对平衡的要求,但降低了保持平衡需要的开销,在实际应用中,统计性能高于AVL树。对于红黑树的算法细节及Java中的实现,会在下篇文章中讲解。

4. 排序二叉树特点

  • 排序二叉树保持了元素的顺序,而且是一种综合效率很高的数据结构,基本的保存、删除、查找的效率都为O(h),h为树的高度,在树平衡的情况下,h为log2(N),N为节点数
  • 基本的排序二叉树不能保证树的平衡,可能退化为一个链表,平衡排序二叉树可以保证二叉树平衡,避免二叉树退化为链表这种情况的产生。Java API中TreeMap就是通过红黑树实现的。

参考链接

  1. 排序二叉树
  2. 维基百科 – 二叉树
  3. 维基百科 – 树的遍历

赞(0) 打赏
Zhuoli's Blog » Java编程拾遗『排序二叉树』
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址