AVL 树和平衡二叉搜索树

作者: freemanIT | 来源:发表于2022-03-21 17:38 被阅读0次

二叉搜索树遇到的问题

树中添加元素, 可能从小到大添加, 会形成链表, 高度会越来越高
删除节点元素时, 同样也会造成退化成链表的情况

如何使得树降低高度, 保持平衡

节点数量保持不变, 左右子树高度越接近, 这棵树就越平衡, 高度越低

最理想的平衡, 完全二叉树, 满二叉树, 高度是最小的

在添加和删除节点操作之后, 调整二叉搜索树高度, 恢复平衡

但是调整次数过多, 代价越大, 反而增加时间复杂度, 所以要用尽量少的调整次数使得一棵树适度平衡, 这样的树称为平衡二叉搜索树

平衡二叉搜索树

简称BBST

常见平衡二叉搜索树, AVL 树, 在Windows NT 内核中广泛使用

红黑树

C++, STL 比如map, set

Java, TreeMap, TreeSet, HashMap, HashSet

Linux 的进度调度

Ngix 的timer 管理

一般称为自平衡的二叉搜索树

AVL 树

平衡因子

Balance Factor, 某节点的左右子树的高度差

AVL 树的特点:

每个节点的平衡因子只可能是1, 0, -1, 绝对值<=1, 超过1, 则失衡
每个节点左右子树高度差不超过1
搜索, 添加, 删除时间复杂度O(logn)

平衡因子

平衡对比

普通二叉搜索树

avl树

继承关系图

添加元素导致的失衡

最坏情况, 所有祖先节点都失衡

父节点, 非祖先节点, 都不可能失衡

添加导致的失衡

LL-右旋转

右旋

g.left = p.right
p.right = g
p 成为这棵树的根节点
符合T0 < n < T1 < p < T2 < g < T3, 达到平衡
修复T2, p, g 的parent 属性, 更新g, p 高度

    public void add(E element) {
        elementNotNullCheck(element);
        // 只有一个根节点
        if (root == null) {
            root = createNode(element, null);
            size++;
            afterAdd(root);
            return;
        }
        
        // 其他节点
        // 找到父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        while (node != null) {
            cmp = compare(element, node.element);
            parent = node;
            if (cmp > 0) {
                node = node.right;
            } else if (cmp < 0) {
                node = node.left;
            } else {
                node.element = element;
                return;
            }
        }
        Node<E> newNode = createNode(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;
        afterAdd(newNode);;
    }

    @Override
    protected void afterAdd(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {
                // 更新高度
                updateHeight(node);
            } else {
                // 恢复平衡
                rebalance(node);
                // 整棵树恢复平衡
                break;
            }
        }
    }

    private void rotateRight(Node<E> grand) {
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRotate(grand, parent, child);
    }
    
    private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        // parent 成为子树的根节点
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else { // grand 是根节点
            root = parent;
        }
        // 更新child 的parent
        if (child != null) {
            child.parent = grand;
        }
        // 更新grand 的parent
        grand.parent = parent;
        // 更新高度
        updateHeight(grand);
        updateHeight(parent);
    }

RR - 左旋转

左旋

g.right = p.left
p.left = g
p 为根节点
符合T0 < n < T1 < p < T2 < g < T3, 达到平衡
修复T1, p, g 的parent 属性
更新g, p 高度

    private void rotateRight(Node<E> grand) {
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRotate(grand, parent, child);
    }

LR- RR左旋, LL右旋

RR-LL

RL- LL右旋, RR 左旋

LL-RR

    @Override
    protected void afterAdd(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {
                // 更新高度, 在遍历过程中更新高度
                updateHeight(node);
            } else {
                // 恢复平衡
                rebalance(node);
                // 整棵树恢复平衡
                break;
            }
        }
    }

    /**
     * 恢复平衡
     * @param node
     */
    private void rebalance(Node<E> grand) {
        Node<E> parent = ((AVLNode<E>)grand).tallerChild();
        Node<E> node = ((AVLNode<E>)parent).tallerChild();
        if (parent.isLeftChild()) {
            if (node.isLeftChild()) {// LL
                rotateRight(grand);
            } else {//LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else { //R
            if (node.isLeftChild()) {//RL
                rotateRight(parent);
                rotateLeft(grand);
            } else { //RR
                rotateLeft(grand);
            }
        }
    }

统一的操作

统一操作

    private void rotate(Node<E> r,
            Node<E> a, Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f, Node<E> g
            ) {
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }
        // a-b-c
        b.left = a;
        if (a != null) {
            a.parent = b;
        }
        b.right = c;
        if (c != null) {
            c.parent = b;
        }
        updateHeight(b);
        
        // e-f-g
        f.left = e;
        if (e != null) {
            e.parent = f;
        }
        f.right = g;
        if (g != null) {
            g.parent = f;
        }
        updateHeight(f);
        
        // b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        updateHeight(d);
    }

删除导致的失衡

删除导致失衡

删除节点16, 可能导致父节点, 祖先节点失衡, 其他节点, 都不可能失衡

LL- 右旋

删除右旋

如果途中绿色节点部分不存在, 更高层的祖先节点可能也会失衡, 需要再次恢复平衡, 可能直到根节点都需要调整, 共O(logn) 次调整

RR- 左旋

删除左旋

LR- RR左旋, LL右旋

删除RR-LL

RL- LL右旋, RR左旋

删除LL-RR

    private void remove(Node<E> node) {
        if (node == null) return;
        
        size--;
        
        if (node.hasTwoChildren()) {// 度为2 的节点
            // 找到后继节点
            Node<E> s = successor(node);
            // 用后继节点的值覆盖度为2 的节点
            node.element = s.element;
            // 删除后继节点
            node = s;
        }
        
        // 删除node 的节点, 度为1 或者0
        Node<E> replacement = node.left != null ? node.left : node.right;
        if (replacement != null) { // 度为1 的节点
            // 更改parent
            replacement.parent = node.parent;
            if (node.parent == null) {// node 是度为1 的节点且是根节点
                root = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else {
                node.parent.right = replacement;
            }
            // 被删除的节点调整
            afterRomove(node);
        } else if (node.parent == null) {// 叶子节点, 且为根节点 
            root = null;
            // 被删除的节点调整
            afterRomove(node);
        } else {// node 是叶子节点, 但不是根节点
            if (node == node.parent.left) {
                node.parent.left = null;
            } else { // node == node.parent.right
                node.parent.right = null;
            }
            // 被删除的节点调整
            afterRomove(node);
        }
    }

    @Override
    protected void afterRomove(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {
                // 更新高度
                updateHeight(node);
            } else {
                // 恢复平衡
                rebalance(node);
            }
        }
    }

完整代码

    public class AVLTree<E> extends BST<E> {
    
    public AVLTree() {
        this(null);
    }
    
    public AVLTree(Comparator<E> comparator) {
        super(comparator);
    }
    
    @Override
    protected void afterAdd(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {
                // 更新高度
                updateHeight(node);
            } else {
                // 恢复平衡
                rebalance(node);
                // 整棵树恢复平衡
                break;
            }
        }
    }
    
    @Override
    protected void afterRomove(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {
                // 更新高度
                updateHeight(node);
            } else {
                // 恢复平衡
                rebalance(node);
            }
        }
    }
    
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent);
    }
    
    /**
     * 恢复平衡
     * @param node
     */
    private void rebalance2(Node<E> grand) {
        Node<E> parent = ((AVLNode<E>)grand).tallerChild();
        Node<E> node = ((AVLNode<E>)parent).tallerChild();
        if (parent.isLeftChild()) {
            if (node.isLeftChild()) {// LL
                rotateRight(grand);
            } else {//LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else { //R
            if (node.isLeftChild()) {//RL
                rotateRight(parent);
                rotateLeft(grand);
            } else { //RR
                rotateLeft(grand);
            }
        }
    }
    
    /**
     * 恢复平衡
     * @param node
     */
    private void rebalance(Node<E> grand) {
        Node<E> parent = ((AVLNode<E>)grand).tallerChild();
        Node<E> node = ((AVLNode<E>)parent).tallerChild();
        if (parent.isLeftChild()) {
            if (node.isLeftChild()) {// LL
                rotate(grand, node.left, node, node.right, parent, parent.right, grand, grand.right);
            } else {//LR
                rotate(grand, parent.left, parent, node.left, node, node.right, grand, grand.right);
            }
        } else { //R
            if (node.isLeftChild()) {//RL
                rotate(grand, grand.left, grand, node.left, node, node.right, parent, parent.right);
            } else { //RR
                rotate(grand, grand.left, grand, parent.left, parent, node.left, node, node.right);
            }
        }
    }
    
    private void rotate(Node<E> r,
            Node<E> a, Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f, Node<E> g
            ) {
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }
        // a-b-c
        b.left = a;
        if (a != null) {
            a.parent = b;
        }
        b.right = c;
        if (c != null) {
            c.parent = b;
        }
        updateHeight(b);
        
        // e-f-g
        f.left = e;
        if (e != null) {
            e.parent = f;
        }
        f.right = g;
        if (g != null) {
            g.parent = f;
        }
        updateHeight(f);
        
        // b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        updateHeight(d);
    }
    
    private void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;
        afterRotate(grand, parent, child);
        
    }
    
    private void rotateRight(Node<E> grand) {
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRotate(grand, parent, child);
    }
    
    private void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        // parent 成为子树的根节点
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else { // grand 是根节点
            root = parent;
        }
        // 更新child 的parent
        if (child != null) {
            child.parent = grand;
        }
        // 更新grand 的parent
        grand.parent = parent;
        // 更新高度
        updateHeight(grand);
        updateHeight(parent);
    }
    
    private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>)node).balanceFactor()) <= 1;
    }
    
    private void updateHeight(Node<E> node) {
        ((AVLNode<E>)node).updateHeight();
    }
    
    private static class AVLNode<E> extends Node<E> {
        int height = 1;
        public AVLNode(E element, Node<E> parent) {
            super(element, parent);
        }
        
        public int balanceFactor() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
            return leftHeight - rightHeight;
        }
        
        public void updateHeight() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
            height = 1 + Math.max(leftHeight, rightHeight);
        }
        
        public Node<E> tallerChild() {
            int leftHeight = left == null ? 0 : ((AVLNode<E>)left).height;
            int rightHeight = right == null ? 0 : ((AVLNode<E>)right).height;
            if (leftHeight > rightHeight) return left;
            if (leftHeight < rightHeight) return right;
            return isLeftChild() ? left : right;
        }

        @Override
        public String toString() {
            String parentStr = "null";
            if (parent != null) {
                parentStr = parent.element.toString();
            }
            return element + "_p(" + parentStr + ")_h(" + height + ")";
        }
    }
    
}

复杂度分析

添加

可能导致所有祖先节点失衡
只要让高度最低的失衡节点恢复平衡, 整棵树就平衡O(1) 调整

删除

可能导致父节点或祖先节点失衡, 只有一个节点会失衡
恢复平衡后, 可能导致更高层的祖先节点失衡, 最多O(logn)调整

平均复杂度

搜索, O(logn)
添加, O(logn), 仅需O(1) 调整
删除, O(logn), 最多需要O(logn) 次选择操作

AVL 树和平衡二叉搜索树

二叉搜索树遇到的问题

如何使得树降低高度, 保持平衡

平衡二叉搜索树

AVL 树

平衡因子

平衡对比

继承关系图

添加元素导致的失衡

LL-右旋转

RR - 左旋转

LR- RR左旋, LL右旋

RL- LL右旋, RR 左旋

统一的操作

删除导致的失衡

LL- 右旋

RR- 左旋

LR- RR左旋, LL右旋

RL- LL右旋, RR左旋

完整代码

复杂度分析

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读