js写一个红黑树代码
时间: 2023-02-20 21:03:59 浏览: 79
下面是一个用 JavaScript 实现的红黑树的代码示例:
```
class Node {
constructor(value, color) {
this.value = value;
this.color = color;
this.left = null;
this.right = null;
}
}
class RedBlackTree {
constructor() {
this.root = null;
}
insert(value) {
if (!this.root) {
this.root = new Node(value, "BLACK");
return;
}
let currentNode = this.root;
let newNode = new Node(value, "RED");
while (true) {
if (value < currentNode.value) {
if (!currentNode.left) {
currentNode.left = newNode;
this.fixTreeProperties(currentNode.left);
break;
} else {
currentNode = currentNode.left;
}
} else {
if (!currentNode.right) {
currentNode.right = newNode;
this.fixTreeProperties(currentNode.right);
break;
} else {
currentNode = currentNode.right;
}
}
}
}
fixTreeProperties(node) {
while (node !== this.root && node.color !== "BLACK" && node.parent.color === "RED") {
let grandParent = node.getGrandParent();
if (grandParent) {
if (node.parent === grandParent.left) {
let uncle = grandParent.right;
if (uncle && uncle.color === "RED") {
node.parent.color = "BLACK";
uncle.color = "BLACK";
grandParent.color = "RED";
node = grandParent;
continue;
}
if (node === node.parent.right) {
this.rotateLeft(node.parent);
node = node.left;
}
node.parent.color = "BLACK";
grandParent.color = "RED";
this.rotateRight(grandParent);
} else {
let uncle = grandParent.left;
if (uncle && uncle.color === "RED") {
node.parent.color = "BLACK";
uncle.color = "BLACK";
grandParent.color = "RED";
node = grandParent;
continue;
}
if (node === node.parent.left) {
this.rotateRight(node.parent);
node = node.right;
}
node.parent.color = "BLACK";
grandParent.color = "RED";
this.rotateLeft(grandParent);
}
}
}
this.root.color = "BLACK";
}
rotateLeft(node) {
let rightChild = node.right;
node.right = rightChild.left;
if (rightChild.left) {
rightChild.left.parent = node;
}
rightChild.parent =