云题海 - 专业文章范例文档资料分享平台

当前位置:首页 > 算法导论 - 实验四 常见平衡树的实现与比较

算法导论 - 实验四 常见平衡树的实现与比较

  • 62 次阅读
  • 3 次下载
  • 2025/7/11 2:43:50

实验四 常见平衡树的实现与比较

1. 问题描述:

代码实现红黑和AVL树

2. 算法原理: a) 树的旋转知识

当我们在对红黑树进行插入和删除等操作时,对树做了修改,那么可能会违背红黑树的性质。

为了保持红黑树的性质,我们可以通过对树进行旋转,即修改树种某些结点的颜色及指针结构,以达到对红黑树进行

插入、删除结点等操作时,红黑树依然能保持它特有的性质(如上文所述的,五点性质)。

树的旋转,分为左旋和右旋,以下借助图来做形象的解释和介绍:

i. 左旋

如上图所示:

当在某个结点pivot上,做左旋操作时,我们假设它的右孩子y不是NIL[T],pivot可以为树内任意右孩子而不是NIL[T]的结点。

左旋以pivot到y之间的链为“支轴”进行,它使y成为该孩子树新的根,而y的左孩子b则成为pivot的右孩子。

ii. 右旋

右旋与左旋差不多,再此不做详细介绍。

b) 红黑树插入、删除操作的具体实现

i.

插入操作各种可能的情况

情况1:插入的是根结点。

原树是空树,此情况只会违反性质2。 对策:直接把此结点涂为黑色。

情况2:插入的结点的父结点是黑色。

此不会违反性质2和性质4,红黑树没有被破坏。 对策:什么也不做。

情况3:当前结点的父结点是红色且祖父结点的另一个子结点(叔叔结点)是红色。 此时父结点的父结点一定存在,否则插入前就已不是红黑树。

与此同时,又分为父结点是祖父结点的左子还是右子,对于对称性,我们只要解开一个方向就可以了。

在此,我们只考虑父结点为祖父左子的情况。

同时,还可以分为当前结点是其父结点的左子还是右子,但是处理方式是一样的。我们将此归为同一类。

对策:将当前节点的父节点和叔叔节点涂黑,祖父结点涂红,把当前结点指向祖父节点,从新的当前节点重新开始算法。

针对情况3,变化前(图片来源:saturnman)[插入4节点]:

变化后:

情况4:当前节点的父节点是红色,叔叔节点是黑色,当前节点是其父节点的右子 对策:当前节点的父节点做为新的当前节点,以新当前节点为支点左旋。 如下图所示,变化前[插入7节点]:

  • 收藏
  • 违规举报
  • 版权认领
下载文档10.00 元 加入VIP免费下载
推荐下载
本文作者:...

共分享92篇相关文档

文档简介:

实验四 常见平衡树的实现与比较 1. 问题描述: 代码实现红黑和AVL树 2. 算法原理: a) 树的旋转知识 当我们在对红黑树进行插入和删除等操作时,对树做了修改,那么可能会违背红黑树的性质。 为了保持红黑树的性质,我们可以通过对树进行旋转,即修改树种某些结点的颜色及指针结构,以达到对红黑树进行 插入、删除结点等操作时,红黑树依然能保持它特有的性质(如上文所述的,五点性质)。 树的旋转,分为左旋和右旋,以下借助图来做形象的解释和介绍: i. 左旋 如上图所示: 当在某个结点pivot上,做左旋操作时,我们假设它的右孩子y不是NIL[T],pivot可以为树内任意右孩子而不是NIL[T]的结点。 <

× 游客快捷下载通道(下载后可以自由复制和排版)
单篇付费下载
限时特价:10 元/份 原价:20元
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
VIP包月下载
特价:29 元/月 原价:99元
低至 0.3 元/份 每月下载150
全站内容免费自由复制
注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信:fanwen365 QQ:370150219
Copyright © 云题海 All Rights Reserved. 苏ICP备16052595号-3 网站地图 客服QQ:370150219 邮箱:370150219@qq.com