红黑树js
2023-09-25 本站作者 【 字体:大 中 小 】
红黑树是一种自平衡的二叉查找树,它能够自动保持树的平衡。在红黑树中,每个节点不是红色的就是黑色的。这种树具有以下特征:
- 根节点是黑色的
- 每个叶节点都是黑色的空节点(NIL节点)
- 每个红色节点的两个子节点都是黑色的
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
红黑树JS实现
红黑树在计算机领域中应用广泛,很多编程语言和数据结构中都有实现。在JavaScript中,红黑树的实现通常使用对象或者类的形式来表示节点。下面是一个简单的红黑树JS实现:
```javascript class Node { constructor(value) { this.value = value; this.left = null; this.right = null; this.parent = null; this.color = \"red\"; } } class RedBlackTree { constructor() { this.root = null; } insert(value) { let node = new Node(value); // ... } // ... } ```插入节点
当我们想要向红黑树中插入一个新节点时,需要考虑以下几种情况:
- 树为空,插入的节点为根节点
- 插入节点的父节点为黑色,无需对树进行调整
- 插入节点的父节点为红色,需要对树进行旋转和重新着色
下面是红黑树中插入节点的JavaScript代码实现:
```javascript insert(value) { let node = new Node(value); if (!this.root) { this.root = node; node.color = \"black\"; return; } let current = this.root; while (current) { if (node.value < current.value) { if (!current.left) { current.left = node; node.parent = current; break; } else { current = current.left; } } else { if (!current.right) { current.right = node; node.parent = current; break; } else { current = current.right; } } } this.fixInsert(node); } ```调整树的平衡
在插入新节点之后,红黑树可能会失去平衡。为了保持树的平衡,我们需要对树进行旋转和颜色修改。下面是红黑树中调整树平衡的JavaScript代码实现:
```javascript fixInsert(node) { while (node.parent && node.parent.color === \"red\") { if (node.parent === node.parent.parent.left) { let uncle = node.parent.parent.right; if (uncle && uncle.color === \"red\") { node.parent.color = \"black\"; uncle.color = \"black\"; node.parent.parent.color = \"red\"; node = node.parent.parent; continue; } if (node === node.parent.right) { node = node.parent; this.rotateLeft(node); } node.parent.color = \"black\"; node.parent.parent.color = \"red\"; this.rotateRight(node.parent.parent); } else { let uncle = node.parent.parent.left; if (uncle && uncle.color === \"red\") { node.parent.color = \"black\"; uncle.color = \"black\"; node.parent.parent.color = \"red\"; node = node.parent.parent; continue; } if (node === node.parent.left) { node = node.parent; this.rotateRight(node); } node.parent.color = \"black\"; node.parent.parent.color = \"red\"; this.rotateLeft(node.parent.parent); } } this.root.color = \"black\"; } ```旋转节点
旋转是红黑树中常用的操作之一,它用于保持树的平衡。在JavaScript中,旋转操作可以分为左旋和右旋。下面是红黑树中左旋和右旋的JavaScript代码实现:
```javascript rotateLeft(node) { let right = node.right; node.right = right.left; if (right.left) { right.left.parent = node; } right.parent = node.parent; if (!node.parent) { this.root = right; } else if (node === node.parent.left) { node.parent.left = right; } else { node.parent.right = right; } right.left = node; node.parent = right; } rotateRight(node) { let left = node.left; node.left = left.right; if (left.right) { left.right.parent = node; } left.parent = node.parent; if (!node.parent) { this.root = left; } else if (node === node.parent.right) { node.parent.right = left; } else { node.parent.left = left; } left.right = node; node.parent = left; } ```删除节点
在删除节点时,我们也需要考虑一些情况:
- 要删除的节点没有子节点
- 要删除的节点只有一个子节点
- 要删除的节点有两个子节点
要保持树的平衡,我们需要对树进行重新颜色和旋转操作。下面是红黑树中删除节点的JavaScript代码实现:
```javascript delete(value) { let node = this.find(value); if (!node) { return; } let replacement; if (node.left && node.right) { replacement = this.findMin(node.right); node.value = replacement.value; node = replacement; } if (node.left) { replacement = node.left; } else { replacement = node.right; } if (replacement) { replacement.parent = node.parent; if (!node.parent) { this.root = replacement; } else if (node === node.parent.left) { node.parent.left = replacement; } else { node.parent.right = replacement; } node.left = node.right = node.parent = null; if (node.color === \"black\") { this.fixDelete(replacement); } } else if (!node.parent) { this.root = null; } else { if (node.color === \"black\") { this.fixDelete(node); } if (node.parent) { if (node === node.parent.left) { node.parent.left = null; } else { node.parent.right = null; } node.parent = null; } } } fixDelete(node) { while (node !== this.root && node.color === \"black\") { if (node === node.parent.left) { let sibling = node.parent.right; if (sibling.color === \"red\") { sibling.color = \"black\"; node.parent.color = \"red\"; this.rotateLeft(node.parent); sibling = node.parent.right; } if (sibling.left.color === \"black\" && sibling.right.color === \"black\") { sibling.color = \"red\"; node = node.parent; continue; } else if (sibling.right.color === \"black\") { sibling.left.color = \"black\"; sibling.color = \"red\"; this.rotateRight(sibling); sibling = node.parent.right; } if (sibling.right.color === \"red\") { sibling.color = node.parent.color; node.parent.color = \"black\"; sibling.right.color = \"black\"; this.rotateLeft(node.parent); node = this.root; } } else { let sibling = node.parent.left; if (sibling.color === \"red\") { sibling.color = \"black\"; node.parent.color = \"red\"; this.rotateRight(node.parent); sibling = node.parent.left; } if (sibling.right.color === \"black\" && sibling.left.color === \"black\") { sibling.color = \"red\"; node = node.parent; continue; } else if (sibling.left.color === \"black\") { sibling.right.color = \"black\"; sibling.color = \"red\"; this.rotateLeft(sibling); sibling = node.parent.left; } if (sibling.left.color === \"red\") { sibling.color = node.parent.color; node.parent.color = \"black\"; sibling.left.color = \"black\"; this.rotateRight(node.parent); node = this.root; } } } node.color = \"black\"; } ```猜你喜欢
白嫖macbookpro
会声会影怎么把照片制成视频
IOS14.4BETA1更新了什么
小技巧教你恢复U盘误删文件
windows8中资源管理器中按钮消失的找回方法
Win10怎么把qq放到桌面?
组装台式电脑去哪(组装台式电脑哪些配件比较关键?)
华为matex2多少钱
Windows10系统如何彻底关闭小娜后台程序
英雄疾风剑豪符文怎么配(英雄联盟疾风剑豪铭文)
太原市旅游攻略 太原最值得去的地方
密云古北水镇旅游攻略 密云古北水镇一日游攻略
银川沙湖旅游攻略 银川沙湖几月份去最好
黔东南旅游攻略 贵州黔东南旅游攻略自由行
青海湖旅游住宿攻略 青海湖环湖住宿攻略
丽江大理洱海旅游攻略 丽江大理攻略最佳旅游攻略
长春旅游攻略景点必去 长春市区旅游攻略必去景点
康定新都桥旅游攻略 新都桥必去的几个景点
普陀山自驾旅游攻略 普陀山旅游自驾游攻略
南昌旅游攻略景点必去 南昌必看的旅游点