《恋上数据结构第1季》平衡二叉搜索树、AVL 树

简介: 《恋上数据结构第1季》平衡二叉搜索树、AVL 树
数据结构与算法笔记目录《恋上数据结构》 笔记目录

想加深 Java 基础推荐看这个Java 强化笔记目录

我的《恋上数据结构》源码(第1季 + 第2季):https://github.com/szluyu99/Data_Structure_Note

AVL 树是在 二叉搜索树 的基础上学习的。

二叉搜索树缺点分析

在这里插入图片描述

  • 当 n 比较大时,两者的性能差异比较大
  • 比如 n = 1000000 时,二叉搜索树的最低高度是 20,最高高度是 1000000;

由此可见,二叉搜索树添加节点时可能会导致二叉搜索树退化成链表;
删除节点时也可能会导致二叉搜索树退化成链表;

有没有办法防止二叉搜索树退化成链表?让添加、删除、搜索的复杂度维持在 O(logn)?

改进二叉搜索树

平衡(Balance)

平衡:当节点数量固定时,左右子树的高度越接近,这棵二叉树就越平衡(高度越低)
在这里插入图片描述

理想平衡

最理想的平衡,就是像完全二叉树、满二叉树那样,高度是最小的;
在这里插入图片描述

如何改进二叉搜索树?

首先,节点的添加、删除顺序是无法限制的,可以认为是随机的:

  • 所以,改进方案是:在节点的添加、删除操作之后,想办法让二叉搜索树恢复平衡(减小树的高度)

在这里插入图片描述
如果接着继续调整节点的位置,完全可以达到理想平衡,但是付出的代价可能会比较大;

  • 比如调整的次数会比较多,反而增加了时间复杂度
  • 总结来说,比较合理的改进方案是:用尽量少的调整次数达到适度平衡即可

一棵达到适度平衡的二叉搜索树,可以称之为:平衡二叉搜索树

平衡二叉搜索树(Balanced Binary Search Tree)

英文简称为:BBST

经典常见的平衡二叉搜索树有:

  • AVL树
    Windows NT 内核中广泛使用
  • 红黑树
    C++ STL(比如 map、set )
    Java 的 TreeMap、TreeSet、HashMap、HashSet
    Linux 的进程调度
    Ngix 的 timer 管理

一般也称它们为:自平衡的二叉搜索树(Self-balancing Binary Search Tree)

AVL树

AVL 树是最早发明的自平衡二叉搜索树之—

平衡因子(Balance Factor):某结点的左右子树的高度差

AVL树的特点:

  • 每个节点的平衡因子只可能是 1、0、-1

(绝对值 ≤ 1,如果超过 1,称之为 “失衡")

  • 每个节点的左右子树高度差不超过1
  • 搜索、添加、删除的时间复杂度是 $O(logn)$

在这里插入图片描述

BST 对比 AVLTree

输入数据:35, 37, 34, 56, 25, 62, 57, 9, 74, 32, 94, 80, 75, 100, 16, 82
在这里插入图片描述

继承 BST

在这里插入图片描述

这里 AVLTree 要继承的 BST,与之前学习的 二叉搜索树 几乎一样,有点小区别;

  • 在添加节点之后增加了 afterAdd() 用于调整平衡;
  • 在删除节点之后增加了 afterRemove() 用于调整平衡;

注意:BST 要继承 BinaryTree

import java.util.Comparator;

/**
 * 二叉搜索树
 */
@SuppressWarnings("unchecked")
public class BST<E> extends BinaryTree<E> {

    // 比较器,根据传入的比较器实现 compareTo() 方法
    private Comparator<E> comparator;

    public BST(Comparator<E> comparator) { // 可以传一个比较器
        this.comparator = comparator;
    }

    public BST() { // 不传比较器,相当于传入一个 null
        this(null); //
    }

    /**
     * 添加元素
     */
    public void add(E element) {
        elementNotNullCheck(element); // 不能传入空节点

        // 传入第一个节点, 若根节点为null, 则该节点为根节点
        if (root == null) {
            root = createNode(element, null);
            size++;
            // 新添加节点之后的处理
            afterAdd(root);
            return;
        }
        // 添加的不是第一个节点, 找到父节点
        Node<E> parent = root;
        Node<E> node = root;
        int cmp = 0;
        do {
            // 比较【传入节点的元素值】与【父节点的元素值】
            cmp = compareTo(element, node.element); // 方向
            parent = node; // 父节点
            if (cmp > 0) { // 传入节点比父节点要大, 往右
                node = node.right;
            } else if (cmp < 0) { // 传入节点比父节点要小, 往左
                node = node.left;
            } else { // 相等,最好是覆盖掉, 也可以采取其他操作, 看具体需求
                node.element = element;
                return;
            }
        } while (node != null);

        // 上面只是找到了要添加位置的父节点, 下面要将元素添加进去
        Node<E> newNode = createNode(element, parent);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }
        size++;

        // 新添加节点之后的处理
        afterAdd(newNode);
    }

    /**
     * 根据传入的值删除元素
     */
    public void remove(E element) {
        remove(node(element));
    }
    // 根据节点删除元素
    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节点(node的度必然是1或者0)
        Node<E> replacement = node.left != null ? node.left : node.right;

        if (replacement != null) { // node是度为1的节点
            // 更改parent
            replacement.parent = node.parent;
            // 更改parent的left、right的指向
            if (node.parent == null) { // node是度为1的节点并且是根节点
                root = replacement;
            } else if (node == node.parent.left) {
                node.parent.left = replacement;
            } else { // node == node.parent.right
                node.parent.right = replacement;
            }

            // 删除节点后的调整
            afterRemove(node);
        } else if (node.parent == null) { // node是叶子节点并且是根节点
            root = null;

            // 删除节点后的调整
            afterRemove(node);
        } else { // node是叶子节点,但不是根节点
            if (node == node.parent.left) {
                node.parent.left = null;
            } else { // node == node.parent.right
                node.parent.right = null;
            }

            // 删除节点后的调整
            afterRemove(node);
        }
    }

    /**
     * 添加node之后的调整
     */
    protected void afterAdd(Node<E> node) {}

    /**
     * 删除node之后的调整
     */
    protected void afterRemove(Node<E> node) {}

    // 根据元素值获取节点元素
    private Node<E> node(E element) {
        elementNotNullCheck(element);

        Node<E> node = root;
        while (node != null) {
            int cmp = compareTo(element, node.element);
            if (cmp < 0) {
                node = node.left;
            } else if (cmp > 0) {
                node = node.right;
            } else { // cmp == 0
                return node;
            }
        }
        return null;
    }

    // 节点元素比较
    private int compareTo(E e1, E e2) {
        if (comparator != null) { // 传入比较器则通过比较器比较
            return comparator.compare(e1, e2);
        }
        // 没传比较器,元素内部必须自行实现了 Comparable 接口
        return ((Comparable<E>) e1).compareTo(e2);
    }

    // 检测传入的节点是否为空
    private void elementNotNullCheck(E element) {
        if (element == null) { // 不能传入空节点
            throw new IllegalArgumentException("element must not null");
        }
    }

}

AVL树基础

public class AVLTree<E> extends BST<E> {

    public AVLTree(Comparator<E> comparator) {
        super(comparator);
    }

    public AVLTree() {
        this(null);
    }

    // AVL树的节点,需要计算平衡因子,因此比普通二叉树多维护一个height属性(将height放入普通二叉树里没有用处,浪费空间)
    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 (rightHeight > leftHeight) return right;
            // 高度一样则返回同方向的,左子节点则返回左,否则返回右
            return isLeftChild() ? left : right;
        }

        @Override
        public String toString() {
            String parentString = "null";
            if (parent != null) {
                parentString = parent.element.toString();
            }
            return element + "_p(" + parentString + ")_h(" + height + ")";
        }
    }
    
    /**
     * 重写父类中的 createNode
     * 返回 AVLNode
     */
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent);
    }

    /**
     * 判断传入节点是否平衡(平衡因子的绝对值 <= 1)
     */
    private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
    }

    /**
     * 更新高度
     */
    private void updateHeight(Node<E> node) {
        ((AVLNode<E>) node).updateHeight();
    }
}

添加节点导致的失衡

示例:往下面这棵子树中添加 13

  • 最坏情况:可能会导致所有祖先节点都失衡
  • 父节点、非祖先节点,都不可能失衡

在这里插入图片描述

修复平衡的操作

  • LL – 右旋转(单旋)
  • RR – 左旋转(单旋)
  • LR – 先左旋,再右旋(双旋)
  • RL – 先右旋,再左旋(双旋)

有些教程里面:

  • 把右旋转叫做 zig,旋转之后的状态叫做 zigged
  • 把左旋转叫做 zag,旋转之后的状态叫做 zagged

LL – 右旋转(单旋)

p 成为这颗子树的根节点

  • g.left = p.right
  • p.right = g

旋转后仍然是一颗 二叉搜索树:T0 < n < T1 < p < T2 < g < T3
在这里插入图片描述
还需要注意维护的内容

  • T2pgparent 属性
  • 先后更新 gp 的高度
/**
 * 右旋转
 */
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);
}

RR – 左旋转(单旋)

p 成为这颗子树的根节点

  • g.right = p.left
  • p.left = g

旋转后仍然是一颗 二叉搜索树:T0 < g < T1 < o < T2 < n < T3
在这里插入图片描述
还需要注意维护的内容

  • T1pgparent 属性
  • 先后更新 gp 的高度
/**
 * 左旋转
 */
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);
}

LR – 先左旋,再右旋(双旋)

LR 就是 先进行 左旋转 – RR、再进行 右旋转 – LL

  • 先左旋转:p.right = n.leftn.left = p
  • 再右旋转:g.left = n.rightn.right = g

旋转后仍然是一颗 二叉搜索树:T0 < p < T1 < n < T2 < g < T3
在这里插入图片描述

RL – 先右旋,再左旋(双旋)

RL 就是 先进行 右旋转 – LL、再进行 左旋转 – RR

  • 先右旋转:p.left = n.rightn.right = p
  • 再左旋转:g.right = n.leftn.left = g

旋转后仍然是一颗 二叉搜索树:T0 < g < T1 < n < T2 < p < T3
在这里插入图片描述

旋转之后维护的内容

/**
 * 公共代码:不管是左旋转、右旋转,都要执行的
 * @param grand 失衡节点
 * @param parent 失衡节点的tallerChild
 * @param child child g和p需要交换的子树(本来是p的子树, 后面会变成g的子树)
 */
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节点
        root = parent;
    }

    // 更新child的parent
    if (child != null) {
        child.parent = grand;
    }

    // 更新grand的parent
    grand.parent = parent;

    // 更新高度
    updateHeight(grand);
    updateHeight(parent);
}

添加之后的修复图解

输入数据:13, 14, 15, 12, 11, 17, 16, 8, 9, 1

输入13:正常
输入14:正常
输入15:==13失衡==,RR,左旋转
在这里插入图片描述
输入12:正常
输入11:==13失衡==,LL,右旋转
在这里插入图片描述
输入17:正常
输入16:==15失衡==,RL,先右选择、再左旋转
在这里插入图片描述
输入8:正常
输入9:==11失衡==,LR,先左旋转、再右旋转
在这里插入图片描述
输入1:==12失衡==,LL,右旋转
在这里插入图片描述

添加之后的修复 - 代码实现

/**
 * 增加节点后的调整
 */
@Override
protected void afterAdd(Node<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) { // 如果平衡
            // 更新高度
            updateHeight(node);
        } else { // 如果不平衡
            // 恢复平衡
            rebalance(node);
            // 只要恢复了最下面的子树的平衡, 则整棵树恢复平衡
            break;
        }
    }
}
/**
 * 恢复平衡
 * @param grand 高度最低的那个不平衡节点
 */
private void rebalance(Node<E> grand) {
    Node<E> parent = ((AVLNode<E>) grand).tallerChild();
    Node<E> node = ((AVLNode<E>) parent).tallerChild();
    if (parent.isLeftChild()) {//L
        if (node.isLeftChild()) {//LL
            rotateRight(grand);//LL则右旋
        } else {//LR
            rotateLeft(parent);
            rotateRight(grand);
        }
    } else {//R
        if (node.isLeftChild()) {//RL
            rotateRight(parent);
            rotateLeft(grand);
        } else {//RR
            rotateLeft(grand);//RR则左旋
        }
    }
}

统一所有的旋转操作

在这里插入图片描述

/**
 * 统一旋转
 */
private void rotate(
    Node<E> r, // 子树的根节点
    Node<E> b, Node<E> c,
    Node<E> d,
    Node<E> e, Node<E> f) {
    // 让d成为这颗子树的根结点
    d.parent = r.parent;
    if (r.isLeftChild()) {
        r.parent.left = d;
    } else if (r.isRightChild()) {
        r.parent.right = d;
    } else {
        root = d;
    }
    // b-c
    b.right = c;
    if (c != null) {
        c.parent = b;
    }
    updateHeight(b);

    // e-f
    f.left = e;
    if (e != null) {
        e.parent = f;
    }
    updateHeight(f);

    // b-d-f
    d.left = b;
    d.right = f;
    b.parent = d;
    f.parent = d;
    updateHeight(d);
}
private void rebalance(Node<E> grand) {
    Node<E> parent = ((AVLNode<E>) grand).tallerChild();
    Node<E> node = ((AVLNode<E>) parent).tallerChild();
    if (parent.isLeftChild()) {//L
        if (node.isLeftChild()) {//LL
            rotate(grand, node, node.right, parent, parent.right, grand);
        } else {//LR
            rotate(grand, parent, node.left, node, node.right, grand);
        }
    } else {//R
        if (node.isLeftChild()) {//RL
            rotate(grand, grand, node.left, node, node.right, parent);
        } else {//RR
            rotate(grand, grand, parent.left, parent, node.left, node);
        }
    }
}

删除节点导致的失衡

示例:删除子树中的 16

  • 可能会导致父节点祖先节点失衡(只有1个节点会失衡),其他节点,都不可能失衡

在这里插入图片描述
在这里插入图片描述

LL – 右旋转(单旋)

  • 如果绿色节点不存在,更高层的祖先节点可能也会失衡,需要再次恢复平衡,然后又可能导致更高层的祖先节点失衡...
  • 极端情况下,所有祖先节点都需要进行恢复平衡的操作,共 O(logn) 次调整

在这里插入图片描述

RR – 左旋转(单旋)

在这里插入图片描述

LR – RR左旋转,LL右旋转(双旋)

在这里插入图片描述

RL – LL右旋转,RR左旋转(双旋)

在这里插入图片描述

删除之后的修复

/**
 * 删除节点后的调整
 */
@Override
protected void afterRemove(Node<E> node) {
    while ((node = node.parent) != null) {
        if (isBalanced(node)) {
            // 更新高度
            updateHeight(node);
        } else {
            // 恢复平衡
            rebalance(node);
        }
    }
}

AVL树总结

添加

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

删除

  • 可能会导致父节点祖先节点失衡(只有1个节点会失衡)
  • 恢复平衡后,可能会导致更高层的祖先节点失衡【最多需要 O(logn) 次调整】

平均时间复杂度

  • 搜索:O(logn)
  • 添加:O(logn),仅需 O(1) 次的旋转操作
  • 删除:O(logn),最多需要 O(logn) 次的旋转操作

AVL树完整源码

package com.mj.tree;

import java.util.Comparator;

public class AVLTree<E> extends BST<E> {

    public AVLTree(Comparator<E> comparator) {
        super(comparator);
    }

    public AVLTree() {
        this(null);
    }

    // AVL树的节点,需要计算平衡因子,因此比普通二叉树多维护一个height属性(将height放入普通二叉树里没有用处,浪费空间)
    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 (rightHeight > leftHeight) return right;
            // 高度一样则返回同方向的,左子节点则返回左,否则返回右
            return isLeftChild() ? left : right;
        }

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

    /**
     * 增加节点后的调整
     */
    @Override
    protected void afterAdd(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) { // 如果平衡
                // 更新高度
                updateHeight(node);
            } else { // 如果不平衡
                // 恢复平衡
                rebalance(node);
                // AVL树中, 只要恢复了最下面的子树的平衡, 则整棵树恢复平衡
                break;
            }
        }
    }

    /**
     * 删除节点后的调整
     */
    @Override
    protected void afterRemove(Node<E> node) {
        while ((node = node.parent) != null) {
            if (isBalanced(node)) {
                // 更新高度
                updateHeight(node);
            } else {
                // 恢复平衡
                rebalance(node);
            }
        }
    }

    /**
     * 重写父类中的 createNode
     * 返回 AVLNode
     */
    @Override
    protected Node<E> createNode(E element, Node<E> parent) {
        return new AVLNode<>(element, parent);
    }

    /**
     * 判断传入节点是否平衡(平衡因子的绝对值 <= 1)
     */
    private boolean isBalanced(Node<E> node) {
        return Math.abs(((AVLNode<E>) node).balanceFactor()) <= 1;
    }

    /**
     * 更新高度
     */
    private void updateHeight(Node<E> node) {
        ((AVLNode<E>) node).updateHeight();
    }

    /**
     * 恢复平衡
     * @param grand 高度最低的那个不平衡节点
     */
    private void rebalance2(Node<E> grand) {
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        Node<E> node = ((AVLNode<E>) parent).tallerChild();
        if (parent.isLeftChild()) { // L
            if (node.isLeftChild()) { // LL
                rotateRight(grand); // LL则右旋
            } else { // LR
                rotateLeft(parent);
                rotateRight(grand);
            }
        } else { // R
            if (node.isLeftChild()) { // RL
                rotateRight(parent);
                rotateLeft(grand);
            } else { // RR
                rotateLeft(grand); // RR则左旋
            }
        }
    }

    private void rebalance(Node<E> grand) {
        Node<E> parent = ((AVLNode<E>) grand).tallerChild();
        Node<E> node = ((AVLNode<E>) parent).tallerChild();
        if (parent.isLeftChild()) {//L
            if (node.isLeftChild()) {//LL
                rotate(grand, node, node.right, parent, parent.right, grand);
            } else {//LR
                rotate(grand, parent, node.left, node, node.right, grand);
            }
        } else {//R
            if (node.isLeftChild()) {//RL
                rotate(grand, grand, node.left, node, node.right, parent);
            } else {//RR
                rotate(grand, grand, parent.left, parent, node.left, node);
            }
        }
    }

    /**
     * 统一旋转
     */
    private void rotate(
            Node<E> r, // 子树的根节点
            Node<E> b, Node<E> c,
            Node<E> d,
            Node<E> e, Node<E> f) {
        // 让d成为这颗子树的根结点
        d.parent = r.parent;
        if (r.isLeftChild()) {
            r.parent.left = d;
        } else if (r.isRightChild()) {
            r.parent.right = d;
        } else {
            root = d;
        }
        // b-c
        b.right = c;
        if (c != null) {
            c.parent = b;
        }
        updateHeight(b);

        // e-f
        f.left = e;
        if (e != null) {
            e.parent = f;
        }
        updateHeight(f);

        // b-d-f
        d.left = b;
        d.right = f;
        b.parent = d;
        f.parent = d;
        updateHeight(d);
    }
    /*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成为这颗子树的根结点
        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);
    }

    /**
     * 公共代码:不管是左旋转、右旋转,都要执行的
     * @param grand 失衡节点
     * @param parent 失衡节点的tallerChild
     * @param child child g和p需要交换的子树(本来是p的子树, 后面会变成g的子树)
     */
    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节点
            root = parent;
        }

        // 更新child的parent
        if (child != null) {
            child.parent = grand;
        }

        // 更新grand的parent
        grand.parent = parent;

        // 更新高度
        updateHeight(grand);
        updateHeight(parent);
    }

}

测试

package com.mj;

import com.mj.printer.BinaryTrees;
import com.mj.tree.AVLTree;

public class Main {
    // Integer类型的数据
    public static void test1(){
        Integer date[] = new Integer[] {
            75, 94, 21, 7, 93, 31, 83, 65, 43, 50, 57, 56
            };
        AVLTree<Integer> avl = new AVLTree<>();
        for (int i = 0; i < date.length; i++) {
            avl.add(date[i]);
            System.out.println("【" + date[i] + "】");
            BinaryTrees.println(avl);
            System.out.println("-----------------------------------------");
        }
    }

    // 删除
    public static void test2(){
        Integer data[] = new Integer[] {
                35, 37, 34, 56, 25, 62, 57, 9, 74, 32, 94, 80, 75, 100, 16, 82
        };
        
        AVLTree<Integer> avl = new AVLTree<>();
        for (int i = 0; i < data.length; i++) {
            avl.add(data[i]);
//            System.out.println("【" + data[i] + "】");
//            BinaryTrees.println(avl);
//            System.out.println("---------------------------------------");
        }
        
        for (int i = 0; i < data.length; i++) {
            avl.remove(data[i]);
            System.out.println("【" + data[i] + "】");
            BinaryTrees.println(avl);
            System.out.println("---------------------------------------");
        }
        
        
        BinaryTrees.println(avl);
    }
    public static void main(String[] args) {
        // test1();
        test2();
    }
}
【35】
             ┌──────────37_p(null)──────────┐
             │                              │
   ┌─────25_p(37)─────┐         ┌────────62_p(37)────────┐
   │                  │         │                        │
9_p(25)─┐        ┌─34_p(25) 56_p(62)─┐         ┌──────80_p(62)─────┐
        │        │                   │         │                   │
     16_p(9) 32_p(34)             57_p(56) 74_p(80)─┐         ┌─94_p(80)─┐
                                                    │         │          │
                                                 75_p(74) 82_p(94)   100_p(94)
---------------------------------------
【37】
             ┌───────────56_p(null)──────────┐
             │                               │
   ┌─────25_p(56)─────┐           ┌───────80_p(56)──────┐
   │                  │           │                     │
9_p(25)─┐        ┌─34_p(25) ┌─62_p(80)─┐           ┌─94_p(80)─┐
        │        │          │          │           │          │
     16_p(9) 32_p(34)   57_p(62)    74_p(62)─┐ 82_p(94)   100_p(94)
                                             │
                                          75_p(74)
---------------------------------------
【34】
         ┌─────────56_p(null)────────┐
         │                           │
   ┌─25_p(56)─┐           ┌───────80_p(56)──────┐
   │          │           │                     │
9_p(25)─┐  32_p(25) ┌─62_p(80)─┐           ┌─94_p(80)─┐
        │           │          │           │          │
     16_p(9)    57_p(62)    74_p(62)─┐ 82_p(94)   100_p(94)
                                     │
                                  75_p(74)
---------------------------------------
【56】
         ┌────────57_p(null)────────┐
         │                          │
   ┌─25_p(57)─┐           ┌──────80_p(57)─────┐
   │          │           │                   │
9_p(25)─┐  32_p(25) ┌─74_p(80)─┐         ┌─94_p(80)─┐
        │           │          │         │          │
     16_p(9)    62_p(74)    75_p(74) 82_p(94)   100_p(94)
---------------------------------------
【25】
         ┌────────57_p(null)────────┐
         │                          │
   ┌─16_p(57)─┐           ┌──────80_p(57)─────┐
   │          │           │                   │
9_p(16)    32_p(16) ┌─74_p(80)─┐         ┌─94_p(80)─┐
                    │          │         │          │
                62_p(74)    75_p(74) 82_p(94)   100_p(94)
---------------------------------------
【62】
         ┌───────57_p(null)───────┐
         │                        │
   ┌─16_p(57)─┐         ┌──────80_p(57)─────┐
   │          │         │                   │
9_p(16)    32_p(16) 74_p(80)─┐         ┌─94_p(80)─┐
                             │         │          │
                          75_p(74) 82_p(94)   100_p(94)
---------------------------------------
【57】
         ┌─────74_p(null)────┐
         │                   │
   ┌─16_p(74)─┐         ┌─80_p(74)─┐
   │          │         │          │
9_p(16)    32_p(16) 75_p(80)  ┌─94_p(80)─┐
                              │          │
                          82_p(94)   100_p(94)
---------------------------------------
【9】
    ┌─────74_p(null)────┐
    │                   │
16_p(74)─┐         ┌─80_p(74)─┐
         │         │          │
      32_p(16) 75_p(80)  ┌─94_p(80)─┐
                         │          │
                     82_p(94)   100_p(94)
---------------------------------------
【74】
    ┌─────75_p(null)────┐
    │                   │
16_p(75)─┐         ┌─94_p(75)─┐
         │         │          │
      32_p(16) 80_p(94)─┐ 100_p(94)
                        │
                     82_p(80)
---------------------------------------
【32】
          ┌─80_p(null)─┐
          │            │
    ┌─75_p(80)    ┌─94_p(80)─┐
    │             │          │
16_p(75)      82_p(94)   100_p(94)
---------------------------------------
【94】
          ┌─80_p(null)─┐
          │            │
    ┌─75_p(80)   ┌─100_p(80)
    │            │
16_p(75)     82_p(100)
---------------------------------------
【80】
          ┌─82_p(null)─┐
          │            │
    ┌─75_p(82)     100_p(82)
    │
16_p(75)
---------------------------------------
【75】
    ┌─82_p(null)─┐
    │            │
16_p(82)     100_p(82)
---------------------------------------
【100】
    ┌─82_p(null)
    │
16_p(82)
---------------------------------------
【16】
82_p(null)
---------------------------------------
【82】
---------------------------------------
相关文章
|
13天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
31 5
|
1月前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
68 16
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
26 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 数据管理
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
这篇文章通过需求分析、代码实现和测试验证,详细介绍了二叉排序树的创建、遍历和删除操作,以及二叉平衡树(AVL)的自平衡特性和单旋转操作,旨在提高树结构在数据管理中的效率和性能。
44 0
数据结构与算法学习二零:二叉排序树(BST)、平衡二叉树(AVL)
|
2月前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
34 0
|
2月前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
30 0
|
2月前
05(数据结构考研)树相关操作代码
05(数据结构考研)树相关操作代码
29 0
|
2月前
|
存储 算法 Java
数据结构和算法--分段树
数据结构和算法--分段树
18 0
|
2月前
【数据结构】二叉搜索树的功能实现详解
【数据结构】二叉搜索树的功能实现详解
29 0