平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。

平衡二叉树(AVL)

首先平衡二叉树是一颗搜索二叉树,因此其节点、树定义与BST一致,这里仅仅就其插入操作保持自平衡来阐述。

保持自平衡(旋转)

要将不平衡的二叉搜索树转换为平衡的AVL树需要对树进行一次或多次旋转,旋转方式分为左单旋、右单旋、左-右双旋、右-左双旋。

左单旋

当前节点的平衡因子(左子树深度与右子树深度相减)为-2,而其右子树的根节点平衡因子也同样为负,直接对其进行左旋转(逆时针)。

function rotateLeft(AvlNode) {
    var node = AvlNode.right
    AvlNode.right = node.left
    node.left = AvlNode
    return node
}

传入需要旋转的子树根节点AvlNode,将其右节点赋值给新节点保存起来,然后AvlNode的右节点的左节点赋值给其右节点,接着把AvlNode赋值给AvlNode的右节点的左节点。最后返回传入节点的右节点,即AvlNode的初始右节点,完成左旋。

右单旋

当前节点的平衡因子(左子树深度与右子树深度相减)为2,而其右子树的根节点平衡因子也同样为正,直接对其进行右旋转(顺时针)。

function rotateRight(AvlNode) {
    var node = AvlNode.left
    AvlNode.left = node.right
    node.right = AvlNode
    return node
}

传入需要旋转的子树根节点AvlNode,将其左节点赋值给新节点保存起来,然后AvlNode的左节点的右节点赋值给其左节点,接着把AvlNode赋值给AvlNode的左节点的右节点。最后返回传入节点的左节点,即AvlNode的初始左节点,完成右旋。

左-右旋

单旋需要子树根节点的平衡因子符号与要旋转的根节点一致,但是当符号相反时,需要对子树根节点进行相反方向旋转,再对要旋转的根节点进行旋转。左右旋即,先对子树跟节点左旋,再对要旋转跟节点进行右旋。

function rotateLeftRight(AvlNode) {
    AvlNode.left = rotateLeft(AvlNode.left)
    return rotateRight(AvlNode)
}

右-左旋

单旋需要子树根节点的平衡因子符号与要旋转的根节点一致,但是当符号相反时,需要对子树根节点进行相反方向旋转,再对要旋转的根节点进行旋转。右左旋即,先对子树跟节点右旋,再对要旋转跟节点进行左旋。

function rotateRightLeft() {
    AvlNode.right = rotateRight(AvlNode.right)
    return rotateLeft(AvlNode)
}

平衡函数

对当前跟节点进行旋转平衡,首先需要一个获得当前节点深度函数getAvlTreeHeight

function getAvlTreeHeight(node) {
    if (!node) {
        return 0
    }
    else {
        //递归调用子节点深度
        var left = getAvlTreeHeight(node.left)
        var right = getAvlTreeHeight(node.right)
        return Math.Max(left, right) + 1
    }
}

对当前节点进行平衡处理

function balance(node) {
    if (node == null) {
        return node
    }
    if (getAvlTreeHeight(node.left) - getAvlTreeHeight(node.right) > 1) {
        if (getAvlTreeHeight(node.left.left) >= getAvlTreeHeight(node.left.right)) {
            //右旋
            node = rotateRight(node)
        } else {
            //左-右旋
            node = rotateLeftRight(node)
        }
    } else if (getAvlTreeHeight(node.right) - getAvlTreeHeight(node.left) > 1) {
        if (getAvlTreeHeight(node.right.right) >= getAvlTreeHeight(node.right.left)) {
            //左旋
            node = rotateLeft(node)
        } else {
            //右-左旋
            node = rotateRightLeft(node)
        }
    }
    return node
}

平衡二叉树的基础上,我们对插入操作进行修改。

function insert(data) {
    var node = new Node(data, null, null)
    if (this.root == null) {
        this.root = node 
    } else {
        this.root = insertNode(this.root, node)
    }
}

插入函数如上,新建节点,左右节点赋空,数据为传入的数据,根节点为空,则新节点为根节点,根节点部位空,执行插入节点函数insertNode操作。

function insertNode(fatherNode, newNode) {
    if (newNode.data < fatherNode.data) {
        if (fatherNode.left == null) {
            fatherNode.left = newNode
            return fatherNode
        } else {
            fatherNode.left = insertNode(fatherNode.left, newNode)
            //平衡父节点
            fatherNode = balance(fatherNode)
            return fatherNode
        }
    } else if (newNode.data > fatherNode.data) {
        if (fatherNode.right == null) {
            fatherNode.right = newNode
            return fatherNode
        } else {
            fatherNode.right = insertNode(fatherNode.right, newNode)
            //平衡父节点
            fatherNode = balance(fatherNode)
            return fatherNode
        }
    }
}

在每次插入节点后,递归调用对父节点的平衡函数,来保持每次插入操作之后整棵树的平衡。