阅读 1206

TypeScript实现AVL树与红黑树

前言

二叉搜索树存在一个问题: 当往树中插入的数据一大部分大于某个节点或小于某个节点,这样就会导致树的一条边非常深。为了解决这个问题就出现了自平衡树这种解决方案。

本文将详解两种自平衡树: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

cbc49be1691ce1ef9474eb728a9b90e7

节点的平衡因子是指在AVL树中,需要对每个节点计算右子树高度(hr)和左子树高度(hl)之间的差值,该值(hr - hl)应为0、1或-1。如果结果不是这三个值之一,则需要平衡该AVL树,下图中的树描述了每个节点的平衡因子。

  • 当前节点只有左子节点时,平衡因子为-1
  • 当前节点只有右子节点时。平衡因子为+1
  • 当前节左、右子节点都拥有时,平衡因子为+1

26ebe531626732bc1d98c757df889b80

平衡操作 - 树的旋转 添加或删除节点后,我们需要计算节点的高度获取平衡因子,根据平衡因子判断是否需要进行旋转来平衡这颗树。树的平衡有以下场景:

  • 左-左(LL): 向右的单旋转
  • 右-右(RR): 向左的单旋转
  • 左-右(LR): 向右的双旋转
  • 右-左(RL): 向左的双旋转

节点高度计算

  • 声明一个方法,该方法接收一个参数: 要获取高度的节点
  • 递归获取当前节点左子树的高度和右子树的高度,返回较大一方的值
  • 递归基线条件:节点为null

平衡因子计算

  • 声明一个方法,该方法接收一个参数:要获取平衡因子的节点
  • 计算当前节点左子树和右子树的高度,计算他们的差值
  • 根据差值返回不同的条件

树的旋转

我们根据计算出的平衡因子来进行如下相对应的旋转

左-左(LL): 向右的单旋转

当节点的左侧子节点的高度大于右侧子节点的高度时,并且左侧子节点也是平衡或左侧较重,此时就需要对平衡树进行LL操作,下图描述了这个过程

  • 与平衡树操作相关的节点有三个(X、Y、Z)
    29efdee0ff6836f94ef51919d9a240f0
  • 将节点X置与Y
    8568b80c447964de8c5ae8ea44891b95
  • 将节点Y的左子节点置为节点X的右子节点
    95b0c4e36d484f79aff2acdb6d2a565f
  • 将X的右子节点置为节点Y
    11c699dd202cf3be43a8551de6d5229b
  • 更新节点
    b8f780eea5394a773190bfaf7ab7ca75
右-右(RR): 向左的单旋转

当节点右侧子节点的高度大于左侧子节点的高度时,并且右侧子节点也是平衡或右侧较重,此时就需要对平衡树进行RR操作,下图描述了这个过程

  • 与平衡树操作相关的节点有三个(X、Y、Z)
    17413b001055473c3aa97b7dace7915a
  • 将节点X至于节点Y
    1a4d78d0fe68cf7aaff9c482433af852
  • 将节点Y的右子节点置为节点X的左子节点
    d0d882a8bb71d50a611d9a20f9eda91b
  • 将节点X的左子节点置为节点Y
    7d70cb1e2d2daad50a7f44555b3eead2
左-右(LR): 向右的双旋转

当左侧子节点的高度大于右侧子节点的高度时,并且左侧子节点右侧较重,此时就需要对平衡树进行左旋转来修复,这样就会形成左-左的情况,然后在对不平衡的节点进行一个右旋转来修复,下图描述了需要进行LR的场景

1ac165b5591422b5c037e88d47746231

  • 进行RR旋转
  • 进行LL旋转

665af59d89c0389a7c724fe116db4caa

右-左(RL): 向左的双旋转

当右侧子节点的高度大于左侧子节点的高度时,并且右侧子节点左侧较重,此时就需要对平衡树进行右旋转进行修复,这样会形成右-右的情况,然后在对不平衡的节点进行一个左旋转来修复,下图描述了需要进行RL的场景

4a0aadc16d3db86065c9020b8dda006f

  • 进行LL旋转
  • 进行RR旋转

460e0e0bc5fdbb55e6c6c03ddb740a4c

插入和移除节点

向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);
复制代码

执行结果如下:

c9a07e0ac807f92e7c48dc85ad61bbe2

红黑树

红黑树:故名思义,即树中的节点不是红的就是黑的,它也是一个自平衡二叉树。上面我们实现了AVL树,我们在向AVL树中插入或移除节点可能会造成旋转,所以我们需要一个包含多次插入和删除的自平衡树,红黑树是比较好的。插入或删除频率比较低,那么AVL树比红黑树更好。

实现思路

红黑树的每个节点都需要遵循以下原则:

  1. 节点不是红的就是黑的
  2. 树的根节点是黑的
  3. 所有叶节点都是黑的
  4. 如果一个节点是红的,那么它的两个子节点都是黑的
  5. 不能有两个相邻的红节点,一个红节点不能有红的父节点或子节点
  6. 从给定的节点找到它的后代节点(NULL叶节点)的所有路径包含相同数量的黑色节点。

插入节点

向红黑树中插入节点的逻辑与二叉树一样,除了插入的逻辑外,我们还需要在插入后给节点应用一种颜色,并且验证树是否满足红黑树的条件以及是否还是自平衡的。

  • 我们需要创建一个新的节点类用来描述红黑树: 节点的颜色、父节点的引用
  • 重写insert方法,如果树是空的则创建一个新的红黑树节点作为根节点,将根节点的颜色设为黑色
  • 如果插入时,树不为空我们会像二叉搜索树一样在正确的位置插入节点,节点插入完成后判断红黑树的规则是否得到满足
  • 重写插入节点函数,插入时保存父节点的引用,返回节点的引用验证插入后树的属性

验证红黑树属性

要验证红黑树是否还是平衡的以及满足它的所有要求,我们需要使用两个概念:重新填色和旋转。

在向树中插入节点后,新节点将会是红色。这不会影响黑色节点数量的规则(规则6),但会影响规则5: 两个后代红节点不能共存。如果插入节点的父节点是黑色,那么没有问题。但是如果插入节点的父节点是红色,那么会违反规则5。要解决这个冲突,我们就只需要改变父节点、祖父节点和叔节点,下图描述了这个过程

3531ed12959d51f49e47cf79f8fef9b2

验证红黑树的属性:

  • 从插入的节点开始,我们要验证它的父节点是否是红色,以及这个节点不为黑色。

  • 验证父节点是祖父节点的左侧子节点还是右侧子节点

  • 如果父节点是祖父节点的左侧子节点会有3种情形

    1. 叔节点是红色,此时我们只需要重新进行填色即可
    2. 节点是父节点的右侧子节点,此时我们需要进行左旋转
    3. 节点是父节点的左侧子节点,此时我们需要进行右旋转
  • 如果父节点是祖父节点的右侧子节点也会有3种情形

    1. 叔节点是红色,重新填色即可
    2. 节点是左侧子节点,右旋转
    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);
复制代码

执行结果如下:

314a102b08e51e5868f00a739894b8c7

文末彩蛋

至此,我们学完了二叉搜索树以及它两种自平衡树的实现。

接下来,我们来玩个寻宝游戏,这个游戏规则如下:

  • 上图藏着这个宝藏的文件名
  • 已知这个文件的开头为: 24e9e
  • 解出文件名后,拼上 www.kaisir.cn/uploads/ 这个地址(访问时用https),在浏览器访问即可获取宝藏

友情提示: 寻找宝藏会用到二叉搜索树,传送门: TypeScript实现二叉搜索树

写在最后

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于掘金,未经许可禁止转载💌