当前位置: 首页 > 编程笔记 >

红黑树的插入详解及Javascript实现方法示例

何峰
2023-03-14
本文向大家介绍红黑树的插入详解及Javascript实现方法示例,包括了红黑树的插入详解及Javascript实现方法示例的使用技巧和注意事项,需要的朋友参考一下

红黑树的性质

一棵满足以下性质的二叉搜索树是一棵红黑树

  1. 每个结点或是黑色或是红色。
  2. 根结点是黑色的。
  3. 每个叶结点(NIL)是黑色的。
  4. 如果一个结点是红色的,则它的两个子结点都是黑色的。
  5. 对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。

性质1和性质2,不用做过多解释。

性质3,每个叶结点(NIL)是黑色的。这里的叶结点并不是指上图中结点1,5,8,15,而是指下图中值为null的结点,它们的颜色为黑色,且是它们父结点的子结点。

性质4,如果一个结点是红色的(图中用白色代替红色),则它的两个子结点都是黑色的,例如结点2,5,8,15。但是,如果某结点的两个子结点都是黑色的,该结点未必是红色的,例如结点1。

性质5,对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点。例如,从结点2到其所有后代叶结点的简单路径上,黑色结点的数量都为2;从根结点11到其所有后代叶结点的简单路径上,黑色结点的数量都为3。

这样的一棵树有什么特点呢?

通过对任何一条从根到叶结点的简单路径上各个结点的颜色进行约束,红黑树确保没有一条路径会比其他路径长出2倍,因为是近似于平衡的。——《算法导论》

由于性质4,红黑树中不会出现两个红色结点相邻的情形。树中最短的可能出现的路径是都是黑色结点的路径,树中最长的可能出现的路径是红色结点和黑色结点交替的路径。再结合性质5,每条路径上均包含相同数目的黑色结点,所以红黑树确保没有一条路径会比其他路径长出2倍。

红黑树的插入

首先以二叉搜索树的方式插入结点,并将其着为红色。如果着为黑色,则会违背性质5,不便调整;如果着为红色,可能会违背性质2或性质4,可以通过相对简单的操作,使其恢复红黑树的性质。

一个结点以二叉搜索树的方式被插入后,可能出现以下几种情况:

情形1

插入结点后,无父结点,结点插入成为根结点,违背性质2,将结点调整为黑色,完成插入。

情形2

插入结点后,其父结点为黑色,没有违背任何性质,不用调整,完成插入。例如下图中插入结点13。

情形3

插入结点后,其父结点为红色,违背了性质4,需要采取一系列的调整。例如下图中插入结点4。

那么一系列的调整是什么呢?

如果插入结点node的父结点father为红色,则结点father必然存在黑色的父结点grandfather,因为如果结点father不存在父结点的话,就是根结点,而根结点是黑色的。那么结点grandfather的另一个子结点,我们可以称之为结点uncle,即结点father的兄弟结点。结点uncle可能为黑色,也可能为红色。

先从最简单的情形分析,因为复杂的情形可以转化为简单的情形,简单的情形就是结点uncle为黑色的情形。

情形3.1

如上图(a)中,情形是这样的,node 为红,father 为红,grandfather 和 uncle 为黑,α,β,θ,ω,η 都是结点对应的子树。假设整棵二叉搜索树中,只有node和father因违背性质4而无法成为正常的红黑树,此时将图(a)调整成图(b),则可以恢复成正常的红黑树。整个调整过程中实际分为两步,旋转和变色。

什么是旋转?

如上图(c)是一棵二叉搜索树的一部分,其中 x, y 是结点,α,β,θ 是对应结点的子树。由图可知,α < x < β < y < θ ,即 α子树中的所有结点都小于x,结点 x都小于 β子树中的所有结点,β子树中的所有结点的值都小于结点 y 的值,结点 y 的值都小于 θ子树中的所有结点。在二叉搜索树中,如果结点y的值比结点x的值大,那么结点x在结点y的左子树中,如图(c);或者结点y在结点x的右子树中,如图(d)。故 α < x < β < y < θ ,也可以用图(d)的结构来表现。这就是旋转,它不会破坏二叉搜索树的性质。

node 为红,father 为红,grandfather 和 uncle 为黑的具体情形一

图(a)中,node 为 father 的左子结点, father 为 grand 的左子结点,node < father < θ < grand < uncle。这种情形中 father < grand,即可以表现为 father 是 grand 的左子树,也可以表现为 grand 是 father 的右子树,故将图(a)中 father 和 grand 旋转,旋转虽然不会破坏二叉搜索树的性质,但是旋转之后,会破坏红黑树的性质,所以还需要调整结点的颜色。

变色

所以图(a)旋转过后,还要将 grand 变为红色,father 变为黑色,变成图(b),完成插入。

node 为红,father 为红,grandfather 和 uncle 为黑的具体情形二

node 为 father 的右子结点, father 为 grand 的右子结点,如下图(e),就是具体情形一的翻转。

即,uncle < grand < θ < father < node ,将图(e)中 father 和 grand 旋转,变色后,变成图(f),完成插入。

node 为红,father 为红,grandfather 和 uncle 为黑的具体情形三

node 为 father 的右子结点, father 为 grand 的左子结点,如下图(m)。

将图(m)中 node 和 father 旋转后,变成图(n),将father看作新的node,就成为了具体情形一,再次旋转,变色后,完成插入。

node 为红,father 为红,grandfather 和 uncle 为黑的具体情形四

node 为 father 的右子结点, father 为 grand 的左子结点,如下图(i),就是具体情形三的翻转。

将图(i)中 node 和 father 旋转后,变成图(j),将father看作新的node,就成为了具体情形二,再次旋转,变色后,完成插入。

情形3.2

node ,father 和 uncle 为红,grandfather 为黑。

如上图(k),不旋转,而是将grand着红,father和uncle着黑,同时将grand作为新的node,进行情形的判断。如果grand作为新的node后,变成了情形2,则插入完成;如果变成了情形3.1,则调整后,插入完成;如果仍是情形3.2,则继续将grand,father和uncle变色,和node结点上移,如果新的node结点没有父节点了,则变成了情形1,将根结点着为黑色,那么插入完成。

综上

node的情形 操作
情形1 node为红,无father 将node重新着色
情形2 node为红,father为黑
情形3.1 node,father为红,grand,uncle为黑 旋转一次或两次,并重新着色
情形3.2 node,father,uncle为红,grand为黑 将father, uncle,grand重新着色, grand作为新的node

代码

// 结点
function Node(value) {
 this.value = value
 this.color = 'red' // 结点的颜色默认为红色
 this.parent = null
 this.left = null
 this.right = null
}

function RedBlackTree() {
 this.root = null
}

RedBlackTree.prototype.insert = function (node) {
 // 以二叉搜索树的方式插入结点
 // 如果根结点不存在,则结点作为根结点
 // 如果结点的值小于node,且结点的右子结点不存在,跳出循环
 // 如果结点的值大于等于node,且结点的左子结点不存在,跳出循环
 if (!this.root) {
 this.root = node
 } else {
 let current = this.root
 while (current[node.value <= current.value ? 'left' : 'right']) {
  current = current[node.value <= current.value ? 'left' : 'right']
 }
 current[node.value <= current.value ? 'left' : 'right'] = node
 node.parent = current
 }
 // 判断情形
 this._fixTree(node)
 return this
}

RedBlackTree.prototype._fixTree = function (node) {
 // 当node.parent不存在时,即为情形1,跳出循环
 // 当node.parent.color === 'black'时,即为情形2,跳出循环
 while (node.parent && node.parent.color !== 'black') {
 // 情形3
 let father = node.parent
 let grand = father.parent
 let uncle = grand[grand.left === father ? 'right' : 'left']
 if (!uncle || uncle.color === 'black') {
  // 叶结点也是黑色的
  // 情形3.1
  let directionFromFatherToNode = father.left === node ? 'left' : 'right'
  let directionFromGrandToFather = grand.left === father ? 'left' : 'right'
  if (directionFromFatherToNode === directionFromGrandToFather) {
  // 具体情形一或二
  // 旋转
  this._rotate(father)
  // 变色
  father.color = 'black'
  grand.color = 'red'
  } else {
  // 具体情形三或四
  // 旋转
  this._rotate(node)
  this._rotate(node)
  // 变色
  node.color = 'black'
  grand.color = 'red'
  }
  break // 完成插入,跳出循环
 } else {
  // 情形3.2
  // 变色
  grand.color = 'red'
  father.color = 'black'
  uncle.color = 'black'
  // 将grand设为新的node
  node = grand
 }
 }

 if (!node.parent) {
 // 如果是情形1
 node.color = 'black'
 this.root = node
 }
}

RedBlackTree.prototype._rotate = function (node) {
 // 旋转 node 和 node.parent
 let y = node.parent
 if (y.right === node) {
 if (y.parent) {
  y.parent[y.parent.left === y ? 'left' : 'right'] = node
 }
 node.parent = y.parent
 if (node.left) {
  node.left.parent = y
 }
 y.right = node.left
 node.left = y
 y.parent = node
 } else {
 if (y.parent) {
  y.parent[y.parent.left === y ? 'left' : 'right'] = node
 }
 node.parent = y.parent
 if (node.right) {
  node.right.parent = y
 }
 y.left = node.right
 node.right = y
 y.parent = node
 }
}

let arr = [11, 2, 14, 1, 7, 15, 5, 8, 4, 16]
let tree = new RedBlackTree()
arr.forEach(i => tree.insert(new Node(i)))
debugger

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对小牛知识库的支持。

 类似资料:
  • 本文向大家介绍图解红黑树及Java进行红黑二叉树遍历的方法,包括了图解红黑树及Java进行红黑二叉树遍历的方法的使用技巧和注意事项,需要的朋友参考一下 红黑树 红黑树是一种数据结构与算法课堂上常常提到但又不会细讲的树,也是技术面试中经常被问到的树,然而无论是书上还是网上的资料,通常都比较刻板难以理解,能不能一种比较直观的方式来理解红黑树呢?本文将以图形的方式来解释红黑树的插入与删除操作。 对树结构

  • 主要内容:1 HashMap的概述,2 主要类属性,3 主要内部类,3.1 Node,3.2 TreeNode,4 构造器,4.1 HashMap(),4.2 HashMap(initialCapacity),4.3 HashMap(initialCapacity loadFactor),4.4 HashMap(m),5 put方法,5.1 顶层put方法,5.2 putVal插入键值对,5.3. put方法流程图总结,,,,,,,,,,,,,,,基于JDK1.8对HashMap集合的主要方法源

  • 本文向大家介绍java算法实现红黑树完整代码示例,包括了java算法实现红黑树完整代码示例的使用技巧和注意事项,需要的朋友参考一下 红黑树 定义 红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。 红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树: 红链接均为左链接;没有任何一个结点同时和两条红链接相连;该树

  • 本文向大家介绍PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】,包括了PHP实现绘制二叉树图形显示功能详解【包括二叉搜索树、平衡树及红黑树】的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了PHP实现绘制二叉树图形显示功能。分享给大家供大家参考,具体如下: 前言: 最近老师布置了一个作业:理解并实现平衡二叉树和红黑树,本来老师是说用C#写的,但是我学的C#基本都还给老师

  • 本文向大家介绍数据结构之红黑树详解,包括了数据结构之红黑树详解的使用技巧和注意事项,需要的朋友参考一下 1.简介 红黑树是一种自平衡二叉查找树。它的统计性能要好于平衡二叉树(AVL树),因此,红黑树在很多地方都有应用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化,这些修改提供了更好的性能,以及

  • 红黑树与AVL的比较: AVL是严格平衡树,因此在增加或者删除节点的时候,根据不同情况,旋转的次数比红黑树要多; 红黑是用非严格的平衡来换取增删节点时候旋转次数的降低; 所以简单说,如果你的应用中,搜索的次数远远大于插入和删除,那么选择AVL,如果搜索,插入删除次数几乎差不多,应该选择RB。 红黑树详解: https://xieguanglei.github.io/blog/post/red-bl