共计 6583 个字符,预计需要花费 17 分钟才能阅读完成。
前面介绍了二叉树和二叉树搜索树的创建和使用,接下来我们继续学习关于树的更多知识。
BST 存在一个问题,就是当我们多次添加节点数,有可能造成一种情况,树的一条边可能会非常深,有非常多的层,而另一条分支却只有几层。当我们需要进行添加、移除和搜索某一节点时,可能会引起一些性能问题。为了解决这类问题,我们进行自平衡树的学习。自平衡树常见有两种:AVL 树和红黑树。
自平衡树
准备知识
节点的高度和平衡因子
节点高度 :从节点到任意子节点的彼岸的最大值。这个相对来说容易理解。那么获得节点高度的代码实现如下:
getNodeHeight(node) {if (node == null) {return -1;}
return Math.max(this.getNodeHeight(node.left), this.getNodeHeight(node.right)) + 1;
}
平衡因子 :每个节点左子树高度和右子树高度的差值。该值为 0、-1、1 时则为正常值,说明该二叉树已经平衡。若果该值不是这三个值之一,则需要平衡该树。遵循计算一个节点的平衡因子并返回其值的代码如下:
const BalanceFactor = {
UNBALANCED_RIGHT: 1,
SLIGHTLY_UNBALANCED_RIGHT: 2,
BALANCED: 3,
SLIGHTLY_UNBALANCED_LEFT: 4,
UNBALANCED_LEFT: 5
};
getBalanceFactor(node) {const heightDifference = this.getNodeHeight(node.left) - this.getNodeHeight(node.right);
switch (heightDifference) {
case -2:
return BalanceFactor.UNBALANCED_RIGHT;
case -1:
return BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT;
case 1:
return BalanceFactor.SLIGHTLY_UNBALANCED_LEFT;
case 2:
return BalanceFactor.UNBALANCED_LEFT;
default:
return BalanceFactor.BALANCED;
}
}
AVL 树
AVL 树是一种自平衡树,添加或移除节点时,AVL 会尝试保持自平衡,也就是会可能尝试转换为完全树。接下来介绍平衡树进行自平衡的操作,AVL 旋转
AVL 旋转
在对 AVL 进行添加或者移除节点后,我们需要计算节点的高度并验证是否需要进行平衡。旋转操作分为单旋转和双旋转两种。
左 - 左 LL(向右的单旋转)
/**
* Left left case: rotate right
*
* b a
* / \ / \
* a e -> rotationLL(b) -> c b
* / \ / \
* c d d e
*
* @param node Node<T>
*/
rotationLL(node){
const tmp = node.right;
node.left = tmp.right;
tmp.right = node;
return tmp;
}
右 - 右 RR(向左的单旋转)
/**
* Right right case: rotate left
*
* a b
* / \ / \
* c b -> rotationRR(a) -> a e
* / \ / \
* d e c d
*
* @param node Node<T>
*/
rotationLL(node) {
const tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}
左 - 右(LR):向右的双旋转
/**
* Left right case: rotate left then right
* @param node Node<T>
*/
rotationLR(node) {node.left = this.rotationRR(node.left);
return this.rotationLL(node);
}
右 - 左(RL):向左的双旋转
/**
* Right left case: rotate right then left
* @param node Node<T>
*/
rotationRL(node) {node.right = this.rotationLL(node.right);
return this.rotationRR(node);
}
完成平衡操作(旋转)的学习后,我们接下来完善一下 AVL 树添加或者移除节点的操作
添加节点
insert(key) {this.root = this.insertNode(this.root, key);
}
insertNode(node, key) {if (node == null) {return new Node(key);
} if (this.compareFn(key, node.key) === Compare.LESS_THAN) {node.left = this.insertNode(node.left, key);
} else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {node.right = this.insertNode(node.right, key);
} else {return node; // duplicated key}
// verify if tree is balanced
const balanceFactor = this.getBalanceFactor(node);
if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {if (this.compareFn(key, node.left.key) === Compare.LESS_THAN) {
// Left left case
node = this.rotationLL(node);
} else {
// Left right case
return this.rotationLR(node);
}
}
if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {if (this.compareFn(key, node.right.key) === Compare.BIGGER_THAN) {
// Right right case
node = this.rotationRR(node);
} else {
// Right left case
return this.rotationRL(node);
}
}
return node;
}
移除节点
removeNode(node, key) {node = super.removeNode(node, key); // {1}
if (node == null) {return node;}
// verify if tree is balanced
const balanceFactor = this.getBalanceFactor(node);
if (balanceFactor === BalanceFactor.UNBALANCED_LEFT) {
// Left left case
if (this.getBalanceFactor(node.left) === BalanceFactor.BALANCED
|| this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT
) {return this.rotationLL(node);
}
// Left right case
if (this.getBalanceFactor(node.left) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {return this.rotationLR(node.left);
}
}
if (balanceFactor === BalanceFactor.UNBALANCED_RIGHT) {
// Right right case
if (this.getBalanceFactor(node.right) === BalanceFactor.BALANCED
|| this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT
) {return this.rotationRR(node);
}
// Right left case
if (this.getBalanceFactor(node.right) === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {return this.rotationRL(node.right);
}
}
return node;
}
}
以上就是关于 AVL 树基础知识的学习,接下来我们介绍另一种平衡树——红黑树。
和 AVL 树一样,红黑树也是一个自平衡二叉树。红黑树本质上也是 AVL 树,但可以包含多次插入和删除。在红黑树中,每个节点都遵循以下规则:
- 顾名思义,每个节点不是红的就是黑的;
- 树的根节点就是黑的;
- 所有叶节点都是黑的;
- 如果一个节点是红的,那么他的两个子节点都是黑的
- 不能有两个相邻的红节点,一个红节点不能有红的父节点或子节点;
- 从给定的节点到他的后代节点(NULL 叶节点)的所有路径包含相同数量的黑色节点。
红黑树
创建红黑树的骨架
const BalanceFactor = {
UNBALANCED_RIGHT: 1,
SLIGHTLY_UNBALANCED_RIGHT: 2,
BALANCED: 3,
SLIGHTLY_UNBALANCED_LEFT: 4,
UNBALANCED_LEFT: 5
};
// 定义颜色类
const Colors = {
RED:'red',
BLACK:'black'
};
// 创建红黑树的节点类型
class RedBlackNode extends Node{constructor(key){super(key);
this.key = key;
this.color = Colors.RED;
this.parent = null;
}
isRed(){return this.color === Colors.RED;}
};
class RedBlackTree extends BinarySearchTree{constructor(compareFn = defaultCompare){super(compareFn);
this.compareFn = compareFn;
this.root = null;
};
}
旋转操作
向右单旋转
//rotationLL
static rotationLL(node){
const tmp = node.left;
node.left = tmp.right;
if(tmp.right && tmp.right.key){tmp.right.parent = node;}
tmp.right.parent = node.parent;
if (!node.parent){this.root = tmp;}else{if(node === node.parent.left){node.parent.left = tmp;}else{node.parent.right = tmp;}
tmp.right = node;
node.parent = tmp;
}
};
向左单旋转
//rotationRR
static rotationRR(node){
const tmp = node.right;
node.right = tmp.left;
if (tmp.left && tmp.left.key){tmp.left.parent = node;}
tmp.parent = node.parent;
if (!node.parent){this.root = tmp;}else{if(node === node.parent.left){node.parent.left = tmp;}else{node.parent.right = tmp;}
}
tmp.left = node;
node.parent = tmp;
}
验证节点颜色属性
// 插入节点后验证红黑树的属性
static fixTreeProperties(node){while (node && node.parent && node.parent.color.isRed() && node.color !== Colors.BLACK){
let parent = node.parent;
const grandParent = parent.parent;
//case A: 父节点是左侧子节点
if (grandParent && grandParent.left === parent){
const uncle = grandParent.right;
//case 1A:叔节点也是红色——只需要重新填色
if (uncle && uncle.color === Colors.RED){
grandParent.color = Colors.RED;
parent.color = Colors.BLACK;
uncle.color = Colors.BLACK;
node = grandParent;
}else{
// case 2A: 节点是右侧子节点——右旋转
if (node === parent.left){RedBlackTree.rotationRR(parent);
node = parent;
parent = node.parent;
}
//case 3A: 子节点是左侧子节点——左旋转
else if(node === parent.right){RedBlackTree.rotationRR(grandParent);
parent.color = Colors.BLACK;
grandParent.color = Colors.RED;
node = parent;
}
}
}
//case B: 父节点是右侧子节点
else{
const uncle = grandParent.left;
//case1B: 叔节点是红色——只需要重新填色
if(uncle && uncle.color === Colors.RED){
grandParent.color = Colors.RED;
parent.color = Colors.BLACK;
uncle.color = Colors.BLACK;
node = grandParent;
}
//case2B: 节点是左侧子节点—右旋转
if (node === parent.left){RedBlackTree.rotationLL(parent);
node = parent;
parent = node.parent;
}
//case3B: 节点是右侧子节点——左旋转
else if(node === parent.right){RedBlackTree.rotationRR(grandParent);
parent.color = Colors.BLACK;
grandParent.color = Colors.RED;
node = parent;
}
}
this.root.color = Colors.BLACK;
}
}
添加新节点
// 向红黑树插入新节点
insertNode(node,key){if(this.compareFn(key,node.key) === Compare.LESS_THAN){if(node.left === null){node.left = new RedBlackNode(key);
node.left.parent = node;
return node.left;
}
else{return this.insertNode(node.left,key);
}
}
else if(node.right === null){node.right = new RedBlackNode(key);
node.right.parent = node;
return node.right;
}
};
insert(key) {if (this.root === null){this.root = new RedBlackNode(key);
this.root.color = Colors.BLACK;
}else{const newNode = this.insertNode(this.root, key);
RedBlackTree.fixTreeProperties(newNode);
}
};
正文完
发表至: javascript
2019-08-23