前言
二叉搜索树存在一个问题: 当往树中插入的数据一大部分大于某个节点或小于某个节点，这样就会导致树的一条边非常深。为了解决这个问题就出现了自平衡树这种解决方案。
本文将详解两种自平衡树：AVL树和红黑树并用TypeScript将其实现，欢迎各位感兴趣的开发者阅读本文。
写在前面
本文讲解的两种自平衡树均基于二叉搜索树实现，对二叉搜索树不了解的开发者请移步: TypeScript实现二叉搜索树
AVL自平衡树
AVL树(Adelson-Velskii-Landi 树)是一种自平衡二叉搜索树，任何一个节点左右两侧子树的高度之差最多为1，添加或删除节点时，AVL树会尽可能尝试转换为完全树。
实现思路
AVL树是一颗二叉搜索树，因此我们可以继承二叉搜索树，重写二叉树的部分方法即可。
AVL树的术语
在AVL树中插入或移除节点和二叉搜索树完全相同，然而AVL树的不同之处在于我们需要校验它的平衡因子，根据平衡因子来判断树是否需要调整，接下来我们就来看下AVL树的相关术语:
- 节点的高度和平衡因子
- 平衡操作 - 树的旋转
节点的高度是从节点到任意子节点的边的最大值，下图描述了一个包含节点高度的树。
- 节点35左子节点高度是1，右子节点高度是2
- 节点45左子节点高度是2，右子节点高度是1
- 节点45取最大子节点边的高度即2
- 节点35到节点45的高度是1而节点45的高度是2，因此节点35的高度是3
节点的平衡因子是指在AVL树中，需要对每个节点计算右子树高度(hr)和左子树高度(hl)之间的差值，该值(hr - hl)应为0、1或-1。如果结果不是这三个值之一，则需要平衡该AVL树，下图中的树描述了每个节点的平衡因子。
- 当前节点只有左子节点时，平衡因子为-1
- 当前节点只有右子节点时。平衡因子为+1
- 当前节左、右子节点都拥有时，平衡因子为+1
平衡操作 - 树的旋转 添加或删除节点后，我们需要计算节点的高度获取平衡因子，根据平衡因子判断是否需要进行旋转来平衡这颗树。树的平衡有以下场景：
- 左-左(LL): 向右的单旋转
- 右-右(RR): 向左的单旋转
- 左-右(LR): 向右的双旋转
- 右-左(RL): 向左的双旋转
节点高度计算
- 声明一个方法，该方法接收一个参数: 要获取高度的节点
- 递归获取当前节点左子树的高度和右子树的高度，返回较大一方的值
- 递归基线条件：节点为null
平衡因子计算
- 声明一个方法，该方法接收一个参数：要获取平衡因子的节点
- 计算当前节点左子树和右子树的高度，计算他们的差值
- 根据差值返回不同的条件
树的旋转
我们根据计算出的平衡因子来进行如下相对应的旋转
左-左(LL): 向右的单旋转
当节点的左侧子节点的高度大于右侧子节点的高度时，并且左侧子节点也是平衡或左侧较重，此时就需要对平衡树进行LL操作，下图描述了这个过程
- 与平衡树操作相关的节点有三个(X、Y、Z)
- 将节点X置与Y
- 将节点Y的左子节点置为节点X的右子节点
- 将X的右子节点置为节点Y
- 更新节点
右-右(RR): 向左的单旋转
当节点右侧子节点的高度大于左侧子节点的高度时，并且右侧子节点也是平衡或右侧较重，此时就需要对平衡树进行RR操作，下图描述了这个过程
- 与平衡树操作相关的节点有三个(X、Y、Z)
- 将节点X至于节点Y
- 将节点Y的右子节点置为节点X的左子节点
- 将节点X的左子节点置为节点Y
左-右(LR): 向右的双旋转
当左侧子节点的高度大于右侧子节点的高度时，并且左侧子节点右侧较重，此时就需要对平衡树进行左旋转来修复，这样就会形成左-左的情况，然后在对不平衡的节点进行一个右旋转来修复，下图描述了需要进行LR的场景
- 进行RR旋转
- 进行LL旋转
右-左(RL): 向左的双旋转
当右侧子节点的高度大于左侧子节点的高度时，并且右侧子节点左侧较重，此时就需要对平衡树进行右旋转进行修复，这样会形成右-右的情况，然后在对不平衡的节点进行一个左旋转来修复，下图描述了需要进行RL的场景
- 进行LL旋转
- 进行RR旋转
插入和移除节点
向AVL树中插入或移除节点的逻辑与二叉搜索树一样，唯一的不同之处在于插入后需要验证树是否平衡，如果不平衡则需要进行相应的旋转操作。
- 获取当前插入树节点的平衡因子
- 如果在向左侧子树插入节点后树不平衡了，我们需要比较插入的键是否小于左侧子节点的键。如果是则进行LL旋转，否则进行LR旋转
- 如果在向右侧子树插入节点后树不平衡了，我们需要比较插入的键是否小于右侧子节点的键。如果是则进行RR旋转，否则进行RL旋转
实现代码
- 新建AVLTree.ts文件
- 声明AVLTree类，继承BinarySearchTree类
export default class AVLTree<T> extends BinarySearchTree<T>{
constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
super(compareFn);
}
}
- 声明平衡因子枚举
enum BalanceFactor {
UNBALANCED_RIGHT = 1,
SLIGHTLY_UNBALANCED_RIGHT = 2,
BALANCED = 3,
SLIGHTLY_UNBALANCED_LEFT = 4,
UNBALANCED_LEFT = 5
}
- 实现计算节点高度函数
private getNodeHeight(node: Node<T>): number{
if (node == null) {
return -1;
}
return Math.max(this.getNodeHeight(<Node<T>>node.left), this.getNodeHeight(<Node<T>>node.right)) + 1;
}
- 实现平衡因子计算函数
private getBalanceFactor(node: Node<T>) {
// 计算差值
const heightDifference = this.getNodeHeight(<Node<T>>node.left) - this.getNodeHeight(<Node<T>>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;
}
}
- 实现树的四种旋转
/**
* 左左情况: 向右的单旋转
*
* b a
* / \ / \
* a e -> rotationLL(b) -> c b
* / \ / \
* c d d e
*
* @param node
*/
private rotationLL(node: Node<T>) {
// 创建tmp变量, 存储node的左子节点
const tmp = <Node<T>>node.left;
// node的左子节点修改为tmp的右子节点
node.left = tmp.right;
// tmp的右子节点修改为node
tmp.right = node;
// 更新节点
return tmp;
}
/**
* 右右情况: 向左的单旋转
*
* a b
* / \ / \
* c b -> rotationRR(a) -> a e
* / \ / \
* d e c d
* @param node
*/
private rotationRR(node: Node<T>) {
// 将节点X置于节点Y
const tmp = <Node<T>>node.right;
// 将Y的右子节点置为X的左子节点
node.right = tmp.left;
// 将X的左子节点置为Y
tmp.left = node;
// 更新节点
return tmp;
}
/**
* 左右情况: 向右的双旋转, 先向右旋转然后向左旋转
* @param node
*/
private rotationLR(node: Node<T>) {
node.left = this.rotationRR(<Node<T>>node.left);
return this.rotationLL(node);
}
/**
* 右左情况: 向左的双旋转,先向左旋转然后向右旋转
* @param node
*/
private rotationRL(node: Node<T>) {
node.right = this.rotationLL(<Node<T>>node.right);
return this.rotationRR(node);
}
- 重写插入和移除节点函数
// 向树AVL树中插入节点
insert(key: T) {
this.root = this.insertNode(<Node<T>>this.root, key)
}
protected insertNode(node: Node<T>, key:T) {
if (node == null) {
return new Node(key);
}else if(this.compareFn(key, node.key) === Compare.LESS_THAN) {
node.left = this.insertNode(<Node<T>>node.left, key);
}else if(this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
node.right = this.insertNode(<Node<T>>node.right, key);
}else {
return node; // 重复的键
}
// 计算平衡因子判断树是否需要平衡操作
const balanceState = this.getBalanceFactor(node);
// 向左侧子树插入节点后树失衡
if (balanceState === BalanceFactor.UNBALANCED_LEFT) {
// 判断插入的键是否小于左侧子节点的键
if (this.compareFn(key, <T>node.left?.key) === Compare.LESS_THAN) {
// 小于则进行LL旋转
node = this.rotationLL(node);
} else {
// 否则进行LR旋转
return this.rotationLR(node);
}
}
// 向右侧子树插入节点后树失衡
if (balanceState === BalanceFactor.UNBALANCED_RIGHT) {
// 判断插入的键是否小于右侧子节点的键
if (this.compareFn(key, <T>node.right?.key) === Compare.BIGGER_THAN) {
// 小于则进行RR旋转
node = this.rotationRR(node);
} else {
// 否则进行RL旋转
return this.rotationRL(node);
}
}
// 更新节点
return node;
}
// 移除节点
protected removeNode(node: Node<T>, key: T) {
node = <Node<T>>super.removeNode(node, key);
if (node == null) {
return node;
}
// 获取树的平衡因子
const balanceState = this.getBalanceFactor(node);
// 左树失衡
if (balanceState === BalanceFactor.UNBALANCED_LEFT) {
// 计算左树的平衡因子
const balanceFactorLeft = this.getBalanceFactor(<Node<T>>node.left);
// 左侧子树向左不平衡
if (balanceFactorLeft === BalanceFactor.BALANCED || balanceFactorLeft === BalanceFactor.UNBALANCED_LEFT) {
// 进行LL旋转
return this.rotationLL(node);
}
// 右侧子树向右不平衡
if (balanceFactorLeft === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
// 进行LR旋转
return this.rotationLR(<Node<T>>node.left);
}
}
// 右树失衡
if (balanceState === BalanceFactor.UNBALANCED_RIGHT) {
// 计算右侧子树平衡因子
const balanceFactorRight = this.getBalanceFactor(<Node<T>>node.right);
// 右侧子树向右不平衡
if (balanceFactorRight === BalanceFactor.BALANCED || balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_RIGHT) {
// 进行RR旋转
return this.rotationRR(node);
}
// 右侧子树向左不平衡
if (balanceFactorRight === BalanceFactor.SLIGHTLY_UNBALANCED_LEFT) {
// 进行RL旋转
return this.rotationRL(<Node<T>>node.right);
}
}
return node;
}
完整代码请移步: AVLTree.ts
编写测试代码
上面我们实现AVL树，接下来我们通过一个例子来测试下上述代码是否正确执行
const avlTree = new AVLTree();
const printNode = value=>{
console.log(value);
}
/**
* 测试树失衡
* 30 30 30
* / \ / \ / \
* 27 60 -> 12 60 -> remove(10) 12 60
* / / \ \
* 12 10 27 27
* /
* 10
*/
avlTree.insert(30);
avlTree.insert(27);
avlTree.insert(60);
avlTree.insert(12);
avlTree.insert(10);
avlTree.remove(10);
// 后序遍历
avlTree.preOrderTraverse(printNode);
执行结果如下:
红黑树
红黑树:故名思义，即树中的节点不是红的就是黑的，它也是一个自平衡二叉树。上面我们实现了AVL树，我们在向AVL树中插入或移除节点可能会造成旋转，所以我们需要一个包含多次插入和删除的自平衡树，红黑树是比较好的。插入或删除频率比较低，那么AVL树比红黑树更好。
实现思路
红黑树的每个节点都需要遵循以下原则：
- 节点不是红的就是黑的
- 树的根节点是黑的
- 所有叶节点都是黑的
- 如果一个节点是红的，那么它的两个子节点都是黑的
- 不能有两个相邻的红节点，一个红节点不能有红的父节点或子节点
- 从给定的节点找到它的后代节点(NULL叶节点)的所有路径包含相同数量的黑色节点。
插入节点
向红黑树中插入节点的逻辑与二叉树一样，除了插入的逻辑外，我们还需要在插入后给节点应用一种颜色，并且验证树是否满足红黑树的条件以及是否还是自平衡的。
- 我们需要创建一个新的节点类用来描述红黑树: 节点的颜色、父节点的引用
- 重写insert方法，如果树是空的则创建一个新的红黑树节点作为根节点，将根节点的颜色设为黑色
- 如果插入时，树不为空我们会像二叉搜索树一样在正确的位置插入节点，节点插入完成后判断红黑树的规则是否得到满足
- 重写插入节点函数，插入时保存父节点的引用，返回节点的引用验证插入后树的属性
验证红黑树属性
要验证红黑树是否还是平衡的以及满足它的所有要求，我们需要使用两个概念：重新填色和旋转。
在向树中插入节点后，新节点将会是红色。这不会影响黑色节点数量的规则(规则6)，但会影响规则5: 两个后代红节点不能共存。如果插入节点的父节点是黑色，那么没有问题。但是如果插入节点的父节点是红色，那么会违反规则5。要解决这个冲突，我们就只需要改变父节点、祖父节点和叔节点，下图描述了这个过程
验证红黑树的属性:
-
从插入的节点开始，我们要验证它的父节点是否是红色，以及这个节点不为黑色。
-
验证父节点是祖父节点的左侧子节点还是右侧子节点
-
如果父节点是祖父节点的左侧子节点会有3种情形
- 叔节点是红色，此时我们只需要重新进行填色即可
- 节点是父节点的右侧子节点，此时我们需要进行左旋转
- 节点是父节点的左侧子节点，此时我们需要进行右旋转
-
如果父节点是祖父节点的右侧子节点也会有3种情形
- 叔节点是红色，重新填色即可
- 节点是左侧子节点，右旋转
- 节点是右侧子节点，左旋转
-
设置根节点颜色，由于根节点必须为黑色，我们进行上述操作后，根节点的颜色可能会被改变，因此我们需要将其设为黑色
实现代码
- 新建RedBlackTree.ts文件
- 声明RedBlackTree类，创建RedBlackNode辅助类，继承BinarySearchTree类
export class RedBlackNode<K> extends Node<K> {
public left: RedBlackNode<K> | undefined;
public right: RedBlackNode<K> | undefined;
public parent: RedBlackNode<K> | undefined;
public color: number;
constructor(public key: K) {
super(key);
this.color = Colors.RED;
}
isRed() {
return this.color === Colors.RED;
}
}
export default class RedBlackTree<T> extends BinarySearchTree<T> {
protected root: RedBlackNode<T> | undefined;
constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
super(compareFn);
}
}
- 重写insert方法
insert(key: T) {
if (this.root == null) {
// 树为空，创建一个红黑树节点
this.root = new RedBlackNode(key);
// 红黑树的特点2: 根节点的颜色为黑色
this.root.color = Colors.BLACK;
} else {
// 在合适的位置插入节点, insertNode方法返回新插入的节点
const newNode = this.insertNode(this.root, key);
// 节点插入后，验证红黑树属性
this.fixTreeProperties(newNode);
}
}
protected insertNode(node: RedBlackNode<T>, key: T): RedBlackNode<T> {
// 当前插入key小于当前节点的key
if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
if (node.left == null) { // 当前节点的左子节点为null
// 在当前节点的左子节点创建一个红黑树节点
node.left = new RedBlackNode(key);
// 保存父节点的引用
node.left.parent = node;
// 返回节点的引用
return node.left;
} else {
// 当前节点的左子节点不为null, 递归寻找合适的位置将其插入
return this.insertNode(node.left,key);
}
} else if (node.right == null) { // 右子节点为null
// 在当前节点的右子节点创建一个红黑树节点
node.right = new RedBlackNode(key);
// 保存父节点的引用
node.right.parent = node;
// 返回节点的引用
return node.right;
} else {
// 递归寻找合适的位置将其插入
return this.insertNode(node.right, key);
}
}
- 实现红黑树属性校验方法
private fixTreeProperties(node: RedBlackNode<T>) {
/**
* 从插入的节点开始验证:
* 1. 当前节点存在且节点的父节点颜色是红色
* 2. 当前节点的颜色不为黑色
*/
while (node && node.parent && node.parent.color === Colors.RED && node.color !== Colors.BLACK) {
// 保证代码可读性: 保存当前节点的父节点引用以及祖父节点引用
let parent = node.parent;
const grandParent = <RedBlackNode<T>>parent.parent;
// 父节点是祖父节点的左侧子节点: 情形A
if (grandParent && grandParent.left === parent) {
// 获取叔节点
const uncle =grandParent.left;
// 情形1A: 叔节点也是红色 -- 只需要重新填色
if (uncle && uncle.color === Colors.RED) {
grandParent.color = Colors.RED;
parent.color = Colors.BLACK;
uncle.color = Colors.BLACK;
node = grandParent;
} else {
// 情形2A: 节点是父节点是右侧子节点 -- 左旋转
if (node === parent.right) {
this.rotationRR(parent);
node = parent;
parent = <RedBlackNode<T>>node.parent;
}
// 情形3A: 节点是父节点的左侧子节点 -- 右旋转
this.rotationLL(grandParent);
parent.color = Colors.BLACK;
grandParent.color = Colors.RED;
node = parent;
}
} else { // 父节点是右侧子节点: 情形B
// 获取叔节点
const uncle = grandParent.left;
// 情形1B: 叔节点是红色 -- 只需要填色
if (uncle && uncle.color === Colors.RED) {
grandParent.color = Colors.RED;
parent.color = Colors.BLACK;
uncle.color = Colors.BLACK;
node = grandParent;
} else {
// 情形2B: 节点是左侧子节点 -- 右旋转
if (node === parent.left) {
this.rotationLL(parent);
node = parent;
parent = <RedBlackNode<T>>node.parent;
}
// 情形3B: 节点是右侧子节点 -- 左旋转
this.rotationRR(grandParent);
parent.color = Colors.BLACK;
grandParent.color = Colors.RED;
node = parent;
}
}
}
// 设置根节点颜色
this.root != null? this.root.color = Colors.BLACK : this.root;
}
- 实现左旋转与右旋转
// 向右的单旋转
private rotationLL(node: RedBlackNode<T>) {
const tmp = <RedBlackNode<T>>node.left;
node.left = tmp.right;
if (tmp.right && tmp.right.key) {
tmp.right.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.right = node;
node.parent = tmp;
}
}
// 向左的单旋转
private rotationRR(node: RedBlackNode<T>) {
const tmp = <RedBlackNode<T>>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;
}
完整代码请移步: RedBlackTree.ts
编写测试代码
上面我们实现了红黑树，接下来我们来测试下我们实现的方法是否都能正确执行
const redBlackTree = new RedBlackTree();
redBlackTree.insert(1);
redBlackTree.insert(2);
redBlackTree.insert(3);
redBlackTree.insert(4);
redBlackTree.insert(5);
redBlackTree.insert(6);
redBlackTree.insert(7);
redBlackTree.insert(8);
redBlackTree.insert(9);
const printNode = value => console.log(value);
redBlackTree.preOrderTraverse(printNode);
执行结果如下:
文末彩蛋
至此，我们学完了二叉搜索树以及它两种自平衡树的实现。
接下来，我们来玩个寻宝游戏，这个游戏规则如下:
- 上图藏着这个宝藏的文件名
- 已知这个文件的开头为: 24e9e
- 解出文件名后，拼上 www.kaisir.cn/uploads/ 这个地址(访问时用https)，在浏览器访问即可获取宝藏
友情提示: 寻找宝藏会用到二叉搜索树，传送门: TypeScript实现二叉搜索树
写在最后
- 文中如有错误，欢迎在评论区指正，如果这篇文章帮到了你，欢迎点赞和关注😊
- 本文首发于掘金，未经许可禁止转载💌
