TOP

从2-3-4树模型到红黑树实现(一)
2019-12-01 18:14:54 】 浏览:36
Tags:2-3-4 模型 实现

从2-3-4树模型到红黑树实现

前言

红黑树,是一个高效的二叉查找树。其定义特性保证了树的路径长度在黑色节点上完美平衡,使得其查找效率接近于完美平衡的二叉树。

但是红黑树的实现逻辑很复杂,各种旋转,颜色变化,直接针对其分析,大多数都是死记硬背各种例子,不太容易有个直观的理解。实际上,红黑树是实现手段,是其他概念模型为了方便在二叉树上实现进而定义的节点颜色这个信息。如果从概念模型入手,再一一对应,就容易理解的多了。而红黑树能够对应的模型有2-3树,2-3-4树等,下面我们会以2-3-4树作为概念模型,对红黑树进行分析。

2-3-4树

2-3-4树是对完美平衡二叉树的扩展,其定义为:

  • 在一个节点中,可以存在1-3个key
  • 2-节点,拥有1个key和2个子节点。
  • 3-节点,拥有2个key和3个子节点。
  • 4-节点,拥有3个key和4个子节点。
  • 子节点为空的节点称为叶子节点。
  • 任意从根节点到叶子节点的路径拥有相同的长度,即路径上的链接数相同。

下图就是一个2-3-4树:

查找

2-3-4树的查找很简单,类似于二叉树,步骤如下:

  • 将查找key和节点内的key逐一对比。
  • 如果命中,则返回节点内key的对应值。
  • 如果节点内的key都不命中,则沿着合适的链接到下一节点重复该过程直到找到或者无后续节点。

举个例子,如果我们要在上面的2-3-4树中查询11,其步骤如下:

插入

2-3-4树的插入,不会发生在中间节点,只会在叶子节点上进行插入。

在叶子节点上新增key,会使得2-节点变为3-节点,3-节点变为4-节点。而原本的4-节点就没有空间可以插入key了。为了解决这个问题,可以将4-节点中间的key推送给其父节点,剩下的2个key形成2个2-节点。效果如下

通过将4-的叶子节点拆分,产生了新的叶子节点可供key插入,同时将中间key送入父节点。该操作不会破坏树的平衡性和高度。但如果叶子节点的父节点也是4-节点,这个操作就无法进行了。为了解决这个问题,有两种思路:

  • 自底向上,从4-叶子节点开始分裂,如果分类后其父节点也是4-节点,继续向上分裂,直到到达根节点。如果根节点也是4-节点,分裂后树的高度+1。
  • 自顶向下,从根节点到插入所在的叶子节点路径上,遇到4-节点就将其分裂。

两种方法都能解决问题,不过自顶向下不需要递归,实现起来更简单。通过这种处理方式,确保了1)最后到达的叶子节点必然是2-或者3-节点,搜索路径上不存在4-节点。

树的生长

2-3-4树是向上生长的。这句话可以从根节点的分裂理解:如果根节点是一个4-节点,当新增key时,根节点会分裂,将中间的key推入父节点。根节点没有父节点,因此中间的key就会成为新的根节点。如下所示:

整颗树的生长可以看成是叶子节点不断的新增key,并且在成为4-节点后被下一次的新增动作分解为2个2-节点,同时将一个key送入父节点。随着这个过程的不断进行,不断有key从叶子节点向根节点汇聚,直到根节点成为4-节点并在下一次新增时被分类,进而让树升高1。

删除

删除是整个操作中最为复杂的部分,因为删除可能发生在任意节点上,并且删除后可能破坏2-3-4树的完美平衡。在这里,我们先来处理一些简单的情况,最后再思考可以推而广之的策略。

删除最大key

在2-3-4树中,删除最大key必然是最右边的叶子节点上。如果叶子节点是3-节点或者4-节点,只需要将其中最大的key删除即可,不会对树的平衡性造成影响。但如果删除的key在2-节点上,情况就变得麻烦,因为删除2-节点,导致树的平衡被破坏。为了避免这个情况的发生,不能让删除发生在2-节点上。

为了让删除不落在2-节点上,可以将2-类型的叶子节点(最终要删除的那个),从其兄弟节点“借”一个key进行融合变成3-节点;也可以将父节点的key和兄弟节点的key融合,变成一个4-节点,主要保证变化过程中树的平衡性不被破坏即可。变换完成之后的节点类型是3-或4-,自然就可以成功删除了。变化的可能情况有:

变化的策略是:

  1. 将父节点的key,自身的key,兄弟节点的key的合并后形成一个逻辑节点。
  2. 变化一:新节点为4-节点的情况下,父节点还有key,则新节点替换目标节点;
  3. 变化二:新节点为5-节点的情况下,最小key还给兄弟节点,次小key还给父节点,剩余2个key设置到目标节点。
  4. 变化三:新节点为6-节点的情况下,最小key还给兄弟节点,次小key还给父节点,剩余3个key设置到目标节点。

向下的搜索,最终达到需要删除key的叶子节点。叶子节点的兄弟节点无法控制,而如果能保证目标key所在的叶子节点的父节点不是2-节点,就可以安全删除key而不会破坏树的结构。因此,在自顶向下的过程中,非根节点如果为2-节点,则通过变化成为非2-节点。这个转化,仅仅针对搜索路径的下一个节点而言,因此可能出现节点1被转化为非2-节点后,其子节点是2-节点,子节点转化为非2-节点时将父节点(节点1)恢复成2-节点。转化的最终目的是为了保证叶子节点的父节点是非2-节点即可,只不过为了达成这个保证,整个转化行为需要从根节点一直进行下去。因此如果在叶子节点的时候执行转化可能会导致子树高度减1,这种变化会影响到全局树的平衡。就需要循环向上迭代到根节点,比较复杂。而从根节点开始一路转化下去,则容易理解和实现,也不会影响树的平衡。

通过执行这种变化,在叶子节点中,就可以安全删除key

删除最小key

最小key的删除思路和操作方式和删除最大key相似,只不过搜索路径的方向是最左而已,其节点变化策略也是相似的,具体的变化有以下几种:

变化的策略是:

  1. 将父节点的key,自身的key,兄弟节点的key的合并后形成一个逻辑节点。
  2. 变化一:新节点为4-节点的情况下,父节点还有key,则新节点替换目标节点;
  3. 变化二:新节点为5-节点的情况下,最大key还给兄弟节点,次大key还给父节点,剩余2个key设置到目标节点。
  4. 变化三:新节点为6-节点的情况下,最大key还给兄弟节点,次大key还给父节点,剩余3个key设置到目标节点。

删除任意key

删除任一key就变得比较麻烦,key可能出现在中间节点上,删除的话,树的结构就被破坏了。这里,我们可以采用一个取巧的思路:如果删除的key是树的中间节点,将该key替换为其中序遍历的后继key;该后继key是删除key的节点的右子树的最小key

key的替换对树无影响;而将替换key删除,则转换为删除对应子树最小Key的问。删除最小Key,需要从根节点自顶向下变化2-节点才能保证叶子节点中key的成功删除。因此,删除任一Key的具体处理思路可以总结为:

  1. 从根节点开始自顶向下搜索,非根节点如果为2-节点,则通过变化成为非2-节点。
  2. 搜索发现目标key,将其替换为中序搜索后继key。
  3. 删除步骤2节点的右子树最小key。

左倾红黑树

2-3-4树是一种概念模型,直接按照这个概念模型用代码实现则比较复杂,主要的复杂有:

首页 上一页 1 2 3 4 下一页 尾页 1/4/4
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Centos7安装redis5.0.7 下一篇SSM 轻量级框架构建图书管理系统