# 如何使用 JavaScript 实现二叉树，二叉平衡树和红黑树

（图太难画了，有空补，逃 ~）

## 二叉树

### 二叉树的遍历

BinaryTree.prototype.preorderTraversal = function (node, printer) {
if (node === null) return;

printer ? printer(node.value) : this.printer(node.value);
this.preorderTraversal(node.left, printer);
this.preorderTraversal(node.right, printer);
};

BinaryTree.prototype.inorderTraversal = function (node, printer) {
if (node === null) return;

printer ? printer(node.value) : this.inorderTraversal(node.left);
this.printer(node.value, printer);
this.inorderTraversal(node.right, printer);
};

BinaryTree.prototype.postorderTraversal = function (node, printer) {
if (node === null) return;

this.postorderTraversal(node.left, printer);
this.postorderTraversal(node.right, printer);
printer ? printer(node.value) : this.printer(node.value);
};

BinaryTree.prototype.levelOrderTraversal = function (node, printer) {
if (node === null) return;

const queue = [];
queue.push(node);

while (queue.length) {
const currNode = queue.shift();

printer ? printer(node.value) : this.printer(currNode.value);

if (currNode.left) {
queue.push(currNode.left);
}

if (currNode.right) {
queue.push(currNode.right);
}
}
};

## 二叉树搜索树

### 实现二叉搜索树

export default class BinarySearchTreeNode extends BinaryTreeNode {
/**
* @param {*} value
* @param {function} compareFunction
* @return {*}
*/
constructor(value, compareFunction) {
super(value, compareFunction);

this.compareFunction = compareFunction;
}

/**
* @param {*} value
* @return {BinarySearchTreeNode}
*/
insert(value) {}

/**
* @param {*} value
* @return {boolean}
*/
find(value) {}

/**
* @param {*} value
* @return {boolean | Error}
*/
remove(value) {}

/**
* @param {*} value
* @return {boolean}
*/
contains(value) {}

/**
* @return {BinarySearchTreeNode}
*/
findMin() {}
}

- 树为空，插入root节点

- 树为不为空，找到父节点，插入父节点的左边 or 右边
/**
* @param {*} value
* @return {BinarySearchTreeNode}
*/
insert(value) {
// curr.node.value === null
if (this.nodeValueComparator.equal(this.value, null)) {
this.value = value;
return this;
}

// curr.node.value < value
if (this.nodeValueComparator.lessThan(this.value, value)) {
// curr.node !== null
if (this.right) {
return this.right.insert(value);
}

// curr.node.right === null
const newNode = new BinarySearchTreeNode(value, this.compareFunction);
this.setRight(newNode);

return newNode;
}

// curr.node.value > value
if (this.nodeValueComparator.greaterThan(this.value, value)) {
// curr.node.left !== null
if (this.left) {
return this.left.insert(value);
}

// curr.node.left === null
const newNode = new BinarySearchTreeNode(value, this.compareFunction);
this.setLeft(newNode);

return newNode;
}

// curr.node.value === value
return this;
}

- 删除的是叶子节点

-> 找到父节点，将父节点的左子树 or 右子树 设为null

-> 如果没有父节点，则是根节点，将root设置为null

- 删除的是度为1的节点

-> 找到父节点，用子树替代当前位置

-> 如果没有父节点，则是根节点，将root指向子树

- 删除的是度为2的节点

-> 找到父节点，找到前驱或者后继节点，替代当前节点，然后删除前驱或后继

-> 如果没有父节点，则是根节点，特殊处理

- 以上删除的节点可能是根节点
/**
* @param {*} value
* @return {boolean | Error}
*/
remove(value) {
const nodeToRemove = this.find(value)

if (!nodeToRemove) {
throw new Error('item not exit in this tree')
}

const parent = nodeToRemove.parent;

// degree === 0 node is a leaf and has no child
if (!nodeToRemove.left && !nodeToRemove.right) {
if (parent) {
parent.removeChild(nodeToRemove)
} else {
nodeToRemove.setValue(null)
}
}
// degree === 2 has tew children
else if (nodeToRemove.left && nodeToRemove.right) {
const nextBiggerNode = nodeToRemove.right.findMin();

if (!this.nodeComparator.equal(nextBiggerNode, nodeToRemove.right)) {
this.remove(nextBiggerNode.value);
nodeToRemove.setValue(nextBiggerNode.value)
} else {
nodeToRemove.setValue(nodeToRemove.right.value);
nodeToRemove.setRight(nodeToRemove.right.right);
}
}
// degree === 1 has only one child
else {
const childNode = nodeToRemove.left || nodeToRemove.right;

if (parent) {
parent.replaceChild(nodeToRemove, childNode)
// childNode.parent = parent
} else {
BinaryTreeNode.coypNode(childNode, nodeToRemove)
}
}

nodeToRemove.parent = null;

return true;
}

## AVL树

### 实现AVL树

export default class AvlTree extends BinarySearchTree {
/**
* @param {*} value
*/
insert(value) { }

/**
* @param {*} value
*/
remove(value) {}

/**
* @param {BinarySearchTreeNode} node
*/
balance(node) {}

/**
* @param {BinarySearchTreeNode} rootNode
*/
rotateLeftLeft(rootNode) {}

/**
* @param {BinarySearchTreeNode} rootNode
*/
rotateLeftRight(rootNode) {}

/**
* @param {BinarySearchTreeNode} rootNode
*/
rotateRightRight(rootNode) { }

/**
* @param {BinarySearchTreeNode} rootNode
*/
rotateRightLeft(rootNode) {}
}

- 当前节点不会失衡，父节点，祖先节点可能会失衡

- 失衡会像上逐级传播

insert

/**
* @param {*} value
*/
insert(value) {
// BinarySearchTree.insert
super.insert(value);

// move up from current node to root to check balance factors
let currentNode = this.root.find(value);
while (currentNode) {
this.balance(currentNode);
currentNode = currentNode.parent;
}
}

balance

/**
* @param {BinarySearchTreeNode} node
*/
balance(node) {
// balance factor is not ok
if (node.balanceFactor > 1) {
// left rotate
if (node.left.balanceFactor > 0) {
// left-left rotate
this.rotateLeftLeft(node);
} else if (node.left.balanceFactor < 0) {
// left-right rotate
this.rotateLeftRight(node);
}
} else if (node.balanceFactor < -1) {
// right rotate
if (node.right.balanceFactor < 0) {
// right-right rotate
this.rotateRightRight(node);
} else if (node.right.balanceFactor > 0) {
// right-left rotate
this.rotateRightLeft(node);
}
}
}

balance2

/**
* @param {*} grand
* @returns {*}
*/
balance2(grand) {
const parent = grand.tallerChild();
const child = parent.tallerChild();

if (parent.isLeftChild(grand)) {
// left
if (child.isLeftChild(parent)) {
// left-left
rotateRight(grand);
} else {
// left-right
rotateLeft(parent);
rotateRight(grand);
}
} else {
// right
if (child.isRightChild(parent)) {
// right-right
rotateLeft(grand);
} else {
// right-left
rotateRight(parent);
rotateLeft(grand);
}
}
}

balance3

/**
* @param {*} grand
* @returns {*}
*/
balance3(grand) {
const parent = grand.tallerChild();
const child = parent.tallerChild();

if (parent.isLeftChild(grand)) {
// left
if (child.isLeftChild(parent)) {
// left-left
rotate(grand, node, node.right, parent, parent.right, grand);
} else {
// left-right
rotate(grand, parent, node.left, node, node.right, grand);
}
} else {
// right
if (child.isRightChild(parent)) {
// right-right
rotate(grand, grand, parent.left, parent, node.left, node);
} else {
// right-left
rotate(grand, grand, node.left, node, node.right, parent);
}
}
}

left-left-右旋-单旋

1. grandparent.left = parent.right

2. parent.parent = grandparent.parent

3. parent.right = grandparent

- 第1步和第2步可以交换

rotateLeftLeft

/**
* @param {BinarySearchTreeNode} rootNode
*/
rotateLeftLeft(rootNode) {
const leftNode = rootNode.left;
rootNode.setLeft(null);

if (rootNode.parent) {
rootNode.parent.setLeft(leftNode);
} else if (rootNode === this.root) {
this.root = leftNode;
}

if (leftNode.right) {
rootNode.setLeft(leftNode.right);
}

leftNode.setRight(rootNode);
}

left-right-左旋-右旋-双旋

1.先对parent节点左旋,变化为rotateLeftLeft情形

2.处理rotateLeftLeft情形

rotateLeftRight

/**
*
* @param {BinarySearchTreeNode} rootNode
*/
rotateLeftRight(rootNode) {
const leftNode = rootNode.left;
rootNode.setLeft(null);

const leftRightNode = leftNode.right;
leftNode.setRight(null);

if (leftRightNode.left) {
leftNode.setRight(leftRightNode.left);
leftRightNode.setLeft(null);
}

rootNode.setLeft(leftRightNode);

leftRightNode.setLeft(leftNode);

this.rotateLeftLeft(rootNode);
}

right-right-左旋-单旋

1. grandparent.right = parent.left

2. parent.parent = grandparent.parent

3. parent.left = grandparent

- 第1步和第2步可以交换

rotateRightRight

/**
* @param {BinarySearchTreeNode} rootNode
*/
rotateRightRight(rootNode) {
const rightNode = rootNode.right;
rootNode.setRight(null);

if (rootNode.parent) {
rootNode.parent.setRight(rightNode);
} else if (rootNode === this.root) {
this.root = rightNode;
}

if (rightNode.left) {
rootNode.setRight(rightNode.left);
}

rightNode.setLeft(rootNode);
}

right-left-右旋-左旋-双旋

1.先对parent节点右旋,变化为rotateRightRight情形

2.处理rotateRightRight情形

rotateRightLeft

/**
* @param {BinarySearchTreeNode} rootNode
*/
rotateRightLeft(rootNode) {
const rightNode = rootNode.right;
rootNode.setRight(null);

const rightLeftNode = rightNode.left;
rightNode.setLeft(null);

if (rightLeftNode.right) {
rightNode.setLeft(rightLeftNode.right);
rightLeftNode.setRight(null);
}

rootNode.setRight(rightLeftNode);

rightLeftNode.setRight(rightNode);

this.rotateRightRight(rootNode);
}

- 和retateLeftLeft情况一致

1. grandparent.left = parent.right

2. parent.parent = grandparent.parent

3. parent.right = grandparent

- 第1步和第2步可以交换

rotateLeft

/**
* @param {*} rootNode
*/
rotateLeft(rootNode) {
const rightNode = rootNode.right;
rootNode.setRight(null);

if (rootNode.parent) {
rootNode.parent.setRight(rightNode);
} else if (rootNode === this.root) {
this.root = rightNode;
}

if (rightNode.left) {
rootNode.setRight(rightNode.left);
}

rightNode.setLeft(rootNode);
}

- 和rotateRightRight情况一直

1. grandparent.right = parent.left

2. parent.parent = grandparent.parent

3. parent.left = grandparent

- 第1步和第2步可以交换

rotateRight

/**
* @param {*} rootNode
*/
rotateRight(rootNode) {
const leftNode = rootNode.left;
rootNode.setLeft(null);

if (rootNode.parent) {
rootNode.parent.setLeft(leftNode);
} else if (rootNode === this.root) {
this.root = leftNode;
}

if (leftNode.right) {
rootNode.setLeft(leftNode.right);
}

leftNode.setRight(rootNode);
}

/**
* @param {*} r
* @param {*} a
* @param {*} b
* @param {*} c
* @param {*} d
* @param {*} e
* @param {*} f
*/
rotate(r, a, b, c, d, e, f) {
// d
d.parent = r.parent;
if (r.isLeftChild()) {
r.parent.setLeft(d);
} else if (r.isRightChild()) {
r.parent.setRight(d);
} else {
this.root = d;
}

//b-c
b.setRight(c);

// e-f
f.setLeft(e);

// b-d-f
d.setLeft(b);
d.setRight(f);
}

- 必定有旋转中心，右旋顺时针旋转，左旋逆时针旋转

- 旋转中心的节点上升，绕中心旋转的节点下沉

- grandparent的父节点更新为parent节点的父节点

- 右旋必定有节点成为旋转中心的右子树

- 左旋必定有节点成为旋转中心的左子树

- 注意判空

remove

/**
* @param {*} value
*/
remove(value) {
// BinarySearchTree.remove
super.remove(value);

//
this.balance(this.root);
}

## B树

- 一个节点，可以存储超过2个元素，可以超过连个节点

- 具有二叉搜索树的性质

- 平衡

m阶B树的性质

m阶：节点的度最大为m

- 1 <= 根节点的元素个数 <= m-1

- ceil(m/2) - 1 <= 非根节点的元素个数 <= m-1

- 子树（度）的个数 = 节点元素个数 + 1

- 2 <= 根节点子树的个数 <= m

- ceil(m/2) <= 非根节点子树的个数 <= m
- B树和二叉搜索树在逻辑上是等价的

- 多代（层级）节点合并就可以得到一个B树节点，反之，B树节点也可以分解

- 2代二叉搜索树合并的节点，最多具有4个子树（4阶B树）

- 3代二叉搜索树合并的节点，最多具有8个子树（8阶B树）

- n代二叉搜索树合并的节点，最多具有2^n个子树（2^n阶B树）

B树的具备二叉搜索树的性质，类似二分搜索的意思

- 1.B树中查找将要添加的位置，必定是叶子节点

- 2.添加可能导致当前叶子节点的元素个数 等于 B树的阶树 m 导致 上溢

- 3.解决上溢：

- 假设上溢节点为中间的某个节点k

- 将k元素和父节点合并，并且将[0,k)和(k,m-1]位置的元素分裂为2个子节点

- 向上合并肯可能导致父节点上溢，进而传播到根节点 -> 高度+1

- 1.叶子节点,直接删除。元素个数低于最低限制 ceil(m/2) - 1 ,可能导致 下溢

-下溢解决：

- 此时节点元素个数必定等于ceil(m/2) - 2

- 如果相邻兄弟节点有至少ceil(m/2)个元素，可以借一个元素 => 右旋

- 兄弟节点的一个元素上升到父节点，父节点的一个元素下沉到当前节点

- 如果相邻兄弟节点只有ceil(m/2) - 1个元素，则合并

- 将父节点的元素挪下来和左右子树合并

- 合并后的元素个数 = ceil(m/2) - 1 + ceil(m/2) - 2 + 1 = 2ceil(m/2) - 2 < m - 1

- 向下合并可能导致父节点下溢，进而传播到根节点 -> 高度 - 1

- 2.非叶子节点，找到前驱或后继，替换待删除的元素，然后再删掉前驱或后继节点

- 非叶子节点的前驱或后继必定在叶子节点中

- 所以，删除的节点始终是叶子节点，同叶子节点的删除

4阶B树

## 红黑树

1.节点是要么是红色要么是黑色

2.根节点必是黑色

3.叶子节点都是黑色

- 按照空节点算

4.红色节点的子节点都是黑色

- 不能出现连续的红色节点（被黑色包裹）

- 存在连续的黑色节点节点

5.从任意节点到叶子节点的所有路径都包含相同数目的黑色节点

- 红黑树和4阶B树（2，3，4树）等价

- 黑色节点和它的红色子节点融合在一起形成一个4阶B树节点

- 红黑树的黑色节点个数和等价的4阶B树节点个数相等

### 实现红黑树

4阶B树的元素个数（1 <= x <= 3)，新元素的添加必定添加到叶子节点中（参考二叉搜索）；

(1)r<-b->r   (2)b->r  (3)r<-b  (4)b

(2)b的左，(3)b的右，(4)b的左右

(2)b右边r的左右，（3）b左边r的左右

LL/RR

1.parent右旋/左旋

2.parent和grandparent交换节点颜色

LR/RL

1.先对parent左旋/右旋 变换为 LL/RR情况

2.针对新的LL/RR处理

(1)b左边r的左右，(1)b右边r的左右

- 上溢解决

- 1.将uncle和parent染成黑色（分裂成B中的两个节点）

- 2.将grandparent染成红色当作新的待插入的节点，向上合并

- 3.插入新节点grandparent（递归），可能导致上溢向上传播直至根节点

/**
* @param {*} value
* @returns {*}
*/
insert(value) {
const insertedNode = super.insert(value);

if (this.nodeComparator.equal(insertedNode, this.root)) {
// make root always be black
this.makeNodeBlack(insertedNode);
} else {
// make all newly inserted nodes to be red
this.makeNodeRed(insertedNode);
}

// check all conditions and balance the nodes
this.balance(insertedNode);

return insertedNode;
}

/**
* @param {*} node
* @return {*}
*/
balance(node) {
if (this.nodeComparator.equal(this.root, node)) {
return;
}

if (this.isNodeBlack(node.parent)) {
return;
}

const grandParent = node.parent.parent;

if (node.uncle && this.isNodeRed(node.uncle)) {
this.makeNodeBlack(node.uncle);
this.makeNodeBlack(node.parent);

if (!this.nodeComparator.equal(this.root, grandParent)) {
this.makeNodeRed(grandParent);
} else {
return;
}

this.balance(grandParent);
} else if (!node.uncle || this.isNodeBlack(node.uncle)) {
if (grandParent) {
let newGrandParent;

if (this.nodeComparator.equal(grandParent.left, node.parent)) {
// left rotate
if (this.nodeComparator.equal(node.parent.left, node)) {
// left-left rotate
newGrandParent = this.leftLeftRotate(grandParent);
} else {
// left-right rotate
newGrandParent = this.leftRightRotate(grandParent);
}
} else {
// right rotate
if (this.nodeComparator.equal(node.parent.right, node)) {
// right-right rotate
newGrandParent = this.rightRightRotate(grandParent);
} else {
// right-left rotate
newGrandParent = this.rightLeftRotate(grandParent);
}
}

if (newGrandParent && newGrandParent.parent === null) {
this.root = newGrandParent;

this.makeNodeBlack(this.root);
}

this.balance(newGrandParent);
}
}
}

todo