算法-基础篇-②数据结构-D(树)

holic-x...大约 31 分钟

算法-基础篇-②数据结构-D(树)

学习核心

二叉树概念核心、分类
- 普通二叉树
- 二叉搜索树：始终遵循"left<root<right"的条件
- AVL：AVL结构、理解AVL的旋转操作思路
二叉树的操作
- 遍历：广度优先遍历（BFS，层次遍历）、深度优先遍历（前序、中序、后序遍历）
- 增删节点

学习资料

Hello-算法（树）open in new window

二叉树基础

1.二叉树概念核心

二叉树（binary tree）是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。与链表类似，二叉树的基本单元是节点，每个节点包含值、左子节点引用和右子节点引用

/* 二叉树节点类 */
class TreeNode {
    int val;         // 节点值
    TreeNode left;   // 左子节点引用
    TreeNode right;  // 右子节点引用
    TreeNode(int x) { val = x; }
}

二叉树的每个节点都有两个引用（指针），分别指向左子节点（left-child node）和右子节点（right-child node），该节点被称为这两个子节点的父节点（parent node）。当给定一个二叉树的节点时，将该节点的左子节点及其以下节点形成的树称为该节点的左子树（left subtree），同理可得右子树（right subtree）

二叉树常见术语

根节点（root node）：位于二叉树顶层的节点，没有父节点
叶节点（leaf node）：没有子节点的节点，其两个指针均指向 None
边（edge）：连接两个节点的线段，即节点引用（指针）
节点所在的层（level）：从顶至底递增，根节点所在层为 1
节点的度（degree）：节点的子节点的数量。在二叉树中，度的取值范围是 0、1、2
二叉树的高度（height）：从根节点到最远叶节点所经过的边的数量
节点的深度（depth）：从根节点到该节点所经过的边的数量
节点的高度（height）：从距离该节点最远的叶节点到该节点所经过的边的数量

2.二叉树基本操作

初始化二叉树

/**
     * 1.初始化二叉树
     * @return
     */
public static TreeNode initTreeNode(){
    // 定义二叉树节点
    TreeNode root = new TreeNode(1);
    TreeNode node1 = new TreeNode(2);
    TreeNode node2 = new TreeNode(3);
    TreeNode node3 = new TreeNode(4);
    TreeNode node4 = new TreeNode(5);
    TreeNode node5 = new TreeNode(6);

    // 构建各个节点的关系（构建节点间的引用关系）
    root.left = node1;
    root.right = node2;
    node1.left = node3;
    node1.right = node4;
    node2.left = node5;

    // 返回根节点
    return root;
}

插入和删除节点

首先自行画图理解节点的插入和删除操作，插入操作可能会改变二叉树原有的逻辑结构，而删除节点则意味着删除该节点及其所有子树。对于二叉树的操作而言，插入和删除操作一般是搭配使用的

![image-20240929153839017](1.算法-基础篇-02-数据结构-D(树) .assets/image-20240929153839017.png)

以上述图示为例，在n1节点和n2节点之间插入P节点，可以看到实际操作可以分为三步：创建节点P、将n1的左节点指向P、将P的左节点指向n2

对于删除节点操作而言：将n1的左节点指向n2，达到删除P节点的目的

TreeNode P = new TreeNode(0);
// 在 n1 -> n2 中间插入节点 P
n1.left = P;
P.left = n2;
// 删除节点 P
n1.left = n2;

3.常见二叉树类型

完美二叉树（perfect binary tree，又称为满二叉树）所有层的节点都被完全填满。在完美二叉树中，叶节点的度为 0 ，其余所有节点的度都为 2 ；若树的高度为 h ，则节点总数为 2^h+1−1 ，呈现标准的指数级关系，反映了自然界中常见的细胞分裂现象

完全二叉树（complete binary tree）只有最底层的节点未被填满，且最底层节点尽量靠左填充（完美二叉树也是一棵完全二叉树）

完满二叉树（full binary tree）除了叶节点之外，其余所有节点都有两个子节点

平衡二叉树（balanced binary tree）中任意节点的左子树和右子树的高度之差的绝对值不超过 1

![image-20240929155514554](1.算法-基础篇-02-数据结构-D(树) .assets/image-20240929155514554.png)

4.二叉树的退化

二叉树的两种极端体现：

一种是所有节点的左右节点都被填满（参考完美二叉树，可以充分发挥二叉树"分治"的优势）
一种是所有节点都偏向某一侧（二叉树退化为链表），此时所有操作都会退化为线性操作，时间复杂度退化至O(n)

在最佳结构和最差结构下，二叉树的叶节点数量、节点总数、高度等达到极大值或极小值。

说明	完美二叉树	链表
第`i`层的节点数量	2^i-1	1
高度为`h`的树的叶节点数量	2^h	1
高度为`h`的树的节点总数	2^h+1-1	h+1
节点总数为`n`的树的高度	log₂(n+1)-1	n-1

二叉树遍历

从物理结构的角度来看，树是一种基于链表的数据结构，因此其遍历方式是通过指针逐个访问节点。然而，树是一种非线性数据结构，这使得遍历树比遍历链表更加复杂，需要借助搜索算法来实现。

二叉树常见的遍历方式包括层序遍历、前序遍历、中序遍历和后序遍历等

1.广度优先遍历（层序遍历）

层序遍历：从顶部到底部逐层遍历，每层都按照从左到右的顺序访问节点（本质上属于广度优先遍历（breadth-first traversal），也称广度优先搜索（breadth-first search, BFS），它体现了一种“一圈一圈向外扩展”的逐层遍历方式）

广度优先遍历通常借助“队列”来实现。队列遵循“先进先出”的规则，而广度优先遍历则遵循“逐层推进”的规则

// BFS 广度优先遍历（层次遍历）
public static List<Integer> printBFS(TreeNode root){
    // 初始化队列，加入根节点
    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.add(root);
    // 初始化列表，用于保存遍历的序列
    List<Integer> list = new ArrayList<>();
    // 遍历队列中的节点（遍历某个节点执行出队，并判断其是否有左右节点，有则分别先后入队，以此类推进行遍历操作）
    while(!queue.isEmpty()){
        // 遍历当前节点，执行出队操作
        TreeNode node = queue.poll(); // 队列出队
        list.add(node.val); // 将其加入遍历序列（只有节点出队时才加入遍历序列）
        // 判断当前节点是否有左节点
        if(node.left != null){
            queue.add(node.left); // 存在左节点，则将其左节点入队
        }
        // 判断当前节点是否有右节点
        if(node.right != null){
            queue.add(node.right);// 存在右节点，则将其右节点入队
        }
    }
    // 返回遍历序列
    return list;
}

复杂度分析：

时间复杂度（O(n)）：所有节点被访问一次，使用 O(n) 时间，其中 n 为节点数量
空间复杂度（O(n)）：在最差情况下，即满二叉树时，遍历到最底层之前，队列中最多同时存在 (n+1)/2 个节点，占用 O(n) 空间

2.深度优先遍历（前序、中序、后序遍历）

前序、中序和后序遍历都属于深度优先遍历（depth-first traversal），也称深度优先搜索（depth-first search, DFS），它体现了一种“先走到尽头，再回溯继续”的遍历方式

![image-20240929162715811](1.算法-基础篇-02-数据结构-D(树) .assets/image-20240929162715811.png)

深度优先遍历通常基于递归实现：前序preOrder、中序midOrder、后序postOrder（所谓的前中后，可以理解为根节点的在这个顺序中的位置，左节点一定比右节点先遍历）

前序遍历：root->left->right
中序遍历：left->root->right
后序遍历：left->right->root

// 前序遍历
public static List<Integer> preOrder(TreeNode root,List<Integer> list){
    // 判断当前节点是否为空
    if(root == null){
        return list;
    }
    // root->left->right
    list.add(root.val);
    preOrder(root.left, list);
    preOrder(root.right, list);
    return list;
}

// 中序遍历
public static List<Integer> midOrder(TreeNode root,List<Integer> list){
    // 判断当前节点是否为空
    if(root == null){
        return list;
    }
    // left->root->right
    midOrder(root.left, list);
    list.add(root.val);
    midOrder(root.right, list);
    return list;
}

// 后序遍历
public static List<Integer> postOrder(TreeNode root,List<Integer> list){
    // 判断当前节点是否为空
    if(root == null){
        return list;
    }
    // left->right->root
    postOrder(root.left, list);
    postOrder(root.right, list);
    list.add(root.val);
    return list;
}

// 初始化传入空List（list存储的是遍历的次序）

二叉树数组表示

1.完美二叉树的数组表示

以完美二叉树为例，将所有节点按照层序遍历的顺序存储在一个数组中，则每个节点都对应唯一的数组索引。

基于此，通过层次遍历序列得到完美二叉树数组，给定数组中的任意一个节点，都可以通过映射公式来访问其左右节点

2.任意二叉树的数组表示

完美二叉树是一个特例，在二叉树的中间层通常存在许多 None 。由于层序遍历序列并不包含这些 None ，因此我们无法仅凭该序列来推测 None 的数量和分布位置。这意味着存在多种二叉树结构都符合该层序遍历序列

基于此，可以考虑在层次遍历序列中显式写出所有none，以此准确映射对应的位置，例如上述的层次遍历顺序为：

{ 1, 2, 3, 4, null, 6, 7, 8, 9, null, null, 12, null, null, 15 }，相当于将这个任意二叉树通过空节点补齐为完美二叉树

对于完全二叉树，由于其NULL都是出现在数组末尾，这意味着可以省略存储所有None值，非常方便

3.优点和局限性分析

二叉树的数组表示主要有以下优点

数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快
不需要存储指针，比较节省空间
允许随机访问节点

然而，数组表示也存在一些局限性

数组存储需要连续内存空间，因此不适合存储数据量过大的树
增删节点需要通过数组插入与删除操作实现，效率较低
当二叉树中存在大量 None 时，数组中包含的节点数据比重较低，空间利用率较低

二叉搜索树

1.二叉搜索树概念核心

二叉搜索树（binary search tree）满足以下条件

条件1：对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值
条件2：任意节点的左、右子树也是二叉搜索树，即同样满足条件1

2.二叉搜索树的操作

将二叉搜索树封装为一个类 BinarySearchTree ，并声明一个成员变量 root ，指向树的根节点

节点查找

给定目标节点值 num ，可以根据二叉搜索树的性质来查找。声明一个节点 cur ，从二叉树的根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系。

若 cur.val < num ，说明目标节点在 cur 的右子树中，因此执行 cur = cur.right
若 cur.val > num ，说明目标节点在 cur 的左子树中，因此执行 cur = cur.left
若 cur.val = num ，说明找到目标节点，跳出循环并返回该节点

/**
     * 查找查找二叉树节点
     * @return
     */
public static TreeNode search(int target,TreeNode root){
    // 定义检索指针从根节点开始
    TreeNode cur = root;
    // 循环查找
    while(cur != null){
        // 将当前节点值和目标值进行比较，如果当前值匹配则检索成功，否则进入左右子树校验
        if(target == cur.val){
            return cur;
        }else if(target < cur.val){
            cur = cur.left; // 进入左节点进行比较
        }else  if(target > cur.val){
            cur = cur.right; // 集合
        }
    }
    return null;
}

插入节点

给定一个待插入元素num，为了保持二叉树"左子树<根节点<右子树"的性质，插入流程分析如下：

【查找插入位置】：和查找操作类似，从根节点出发，根据当前节点值和num的大小关系循环向下搜索，直到越过叶子节点（遍历至NULL时跳出循环）
【在该位置插入节点】：初始化节点num，然后将新节点置于None的位置

public static TreeNode insert(int target,TreeNode root){
    // 1.判断根节点是否为null，如果为NULL直接新建节点即可。根节点不为NULL，检索节点插入位置，然后执行插入操作
    if(root == null){
        return new TreeNode(target);
    }

    // 2.查找插入位置（如果存在重复节点，则不执行任何操作直接返回）
    // 定义检索指针从根节点开始,pre保存上一轮循环的节点
    TreeNode cur = root, pre=null;
    // 循环查找
    while(cur != null){
        // 将当前节点值和目标值进行比较，如果当前值匹配则检索成功，否则进入左右子树校验
        if(target == cur.val){
            return root; // 节点重复，不执行任何操作，直接返回原来的root
        }
        // 确认插入位置
        pre = cur; // 保存插入位置的父节点信息
        if(target < cur.val){
            cur = cur.left; // 进入左节点进行比较
        }else  if(target > cur.val){
            cur = cur.right; // 进入右节点进行比较
        }
    }

    // 3.新建节点进行插入（此时以pre作为父节点进行插入）
    TreeNode node = new TreeNode(target);
    // 根据节点值进行判断插入位置
    if(pre.val<target){
        pre.right = node; // 插入左边
    }else{
        pre.left = node; // 插入右边
    }
    return root;
}

![image-20240929224612422](1.算法-基础篇-02-数据结构-D(树) .assets/image-20240929224612422.png)

插入过程中需注意两点：

二叉搜索树不允许重复节点（违反定义），如果查找位置时发现节点已存在则不执行任何操作直接返回
在遍历的过程中可以定义一个pre指针保存上一轮循环的节点，当遍历到null的时候，可以根据其父节点pre完成节点插入操作

删除节点

删除节点的思路类似，需要在二叉树中找到目标节点，然后再将其删除。为了确保删除操作完成后的搜索二叉树要满足"左子树<根节点<右子树"的性质，需要根据目标节点的子节点数量，根据0、1、2三种情况执行相应的删除操作

【情况1】当待删除节点的度是0时，表示该节点为叶子节点，可直接删除（根据其pre将对应子节点置为NULL）
【情况2】当待删除节点的度为 1 时，将待删除节点替换为其子节点即可
【情况3】当待删除节点的度为 2 时，无法直接删除，而需要使用一个节点替换该节点。由于要保持二叉搜索树“左子树 < 根节点 < 右子树”的性质，因此这个节点可以是右子树的最小节点或左子树的最大节点。假设选择右子树的最小节点（中序遍历的下一个节点），则删除操作流程如下所示
- 找到待删除节点在“中序遍历序列”中的下一个节点，记为 tmp
- 用 tmp 的值覆盖待删除节点的值，并在树中递归删除节点 tmp

![image-20240929230336060](1.算法-基础篇-02-数据结构-D(树) .assets/image-20240929230336060.png)

/**
 * 二叉搜索树
 */
public class BinarySearchTree {

    /**
     * initTreeNode：初始化二叉树
     */
    public static TreeNode initTreeNode() {
        // 定义二叉树节点
        TreeNode root = new TreeNode(8);
        TreeNode node1 = new TreeNode(4);
        TreeNode node2 = new TreeNode(12);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(6);
        TreeNode node5 = new TreeNode(10);
        TreeNode node6 = new TreeNode(14);
        TreeNode node7 = new TreeNode(1);
        TreeNode node8 = new TreeNode(3);
        TreeNode node9 = new TreeNode(5);
        TreeNode node10 = new TreeNode(7);
        TreeNode node11 = new TreeNode(9);
        TreeNode node12 = new TreeNode(11);
        TreeNode node13 = new TreeNode(13);
        TreeNode node14 = new TreeNode(15);

        // 构建各个节点的关系（构建节点间的引用关系）
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node3.left = node7;
        node3.right = node8;
        node4.left = node9;
        node4.right = node10;
        node5.left = node11;
        node5.right = node12;
        node6.left = node13;
        node6.right = node14;

        // 返回根节点
        return root;
    }


    /**
     * 查找二叉树节点
     *
     * @return
     */
    public static TreeNode search(int target, TreeNode root) {
        // 定义检索指针从根节点开始
        TreeNode cur = root;
        // 循环查找
        while (cur != null) {
            // 将当前节点值和目标值进行比较，如果当前值匹配则检索成功，否则进入左右子树校验
            if (target == cur.val) {
                return cur;
            } else if (target < cur.val) {
                cur = cur.left; // 进入左节点进行比较
            } else if (target > cur.val) {
                cur = cur.right; // 进入右节点进行比较
            }
        }
        return null;
    }


    /**
     * 插入节点
     *
     * @return
     */
    public static TreeNode insert(int target, TreeNode root) {
        // 1.判断根节点是否为null，如果为NULL直接新建节点即可。根节点不为NULL，检索节点插入位置，然后执行插入操作
        if (root == null) {
            return new TreeNode(target);
        }

        // 2.查找插入位置（如果存在重复节点，则不执行任何操作直接返回）
        // 定义检索指针从根节点开始,pre保存上一轮循环的节点
        TreeNode cur = root, pre = null;
        // 循环查找
        while (cur != null) {
            // 将当前节点值和目标值进行比较，如果当前值匹配则检索成功，否则进入左右子树校验
            if (target == cur.val) {
                return root; // 节点重复，不执行任何操作，直接返回原来的root
            }
            // 确认插入位置
            pre = cur; // 保存插入位置的父节点信息
            if (target < cur.val) {
                cur = cur.left; // 进入左节点进行比较
            } else if (target > cur.val) {
                cur = cur.right; // 进入右节点进行比较
            }
        }

        // 3.新建节点进行插入（此时以pre作为父节点进行插入）
        TreeNode node = new TreeNode(target);
        // 根据节点值进行判断插入位置
        if (pre.val < target) {
            pre.right = node; // 插入左边
        } else {
            pre.left = node; // 插入右边
        }
        return root;
    }


    // 删除节点（找到节点位置，然后根据节点的度分情况讨论进行删除）
    public static void remove(int target, TreeNode root) {
        // 判断树是否为空
        if (root == null) {
            return; // 树为空，不执行任何操作
        }

        // 1.树不为空，查找删除节点
        TreeNode cur = root, pre = null;
        while (cur != null) {
            if (cur.val == target) {
                break; // 位置定位成功，直接跳出循环，cur指向当前待删除节点位置
            }
            // 记录上一轮循环的cur节点位置
            pre = cur;
            // 根据值判断从左子树还是右子树进行查找
            if (cur.val > target) {
                cur = cur.left; // 待删除节点在cur的左子树
            } else if (cur.val < target) {
                cur = cur.right; // 待删除节点在cur的右子树
            }
        }

        // 判断待删除节点是否存在，如果不存在则不执行任何操作
        if (cur == null) {
            return;
        }

        // 待删除节点存在，则根据待删除节点的度分情况讨论进行操作

        // 删除节点度为0
        if (cur.left == null && cur.right == null) {
            // 判断删除的是否为root节点
            if (cur != root) {
                // 执行删除操作（根据pre的值进行判断）
                if (pre.left == cur) {
                    pre.left = null; // target在左边，置为null
                } else if (pre.right == cur) {
                    pre.right = null; // target在右边，置为null
                }
            } else {
                // 删除的是根节点
                root = null;
            }
        }

        // 删除节点度为1
        if (cur.left == null || cur.right == null) {
            // 判断删除的是否为root节点
            if (cur != root) {
                // 执行删除操作（根据pre的值进行判断）
                if (pre.left == cur) {
                    pre.left = cur.left; // 将cur的左子树作为pre的左子树
                } else if (pre.right == cur) {
                    pre.right = cur.right; // 将cur的右子树作为pre的右子树
                }
            } else {
                // 删除的是根节点
                root = null;
            }
        }

        // 删除节点度为2
        if (cur.left != null && cur.right != null) {
            // 获取中序遍历中cur的下一个节点(此处找的是右子树的最小节点，即中序遍历的下一个节点)
            TreeNode temp = cur.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            // 递归删除节点temp
            remove(temp.val, root);
            // 用tmp覆盖cur
            cur.val = temp.val;
        }

    }


    public static void main(String[] args) {
        BinarySearchTree bsh = new BinarySearchTree();
        TreeNode root = bsh.initTreeNode();
        TreeNode searchRes = bsh.search(5, root);
        System.out.println("查找结果：" + (searchRes == null ? "null" : searchRes.val));

        // 模拟插入操作
        bsh.insert(16, root);
        TreeNode res = bsh.search(16, root);
        System.out.println("查找结果：" +( res == null ? "null" : res.val));

        // 模拟删除操作
        bsh.remove(16,root);
        TreeNode res1 = bsh.search(16, root);
        System.out.println("删除【16】后：" + (res1 == null ? "null" : res.val));
        // 模拟删除操作
        bsh.remove(5,root);
        TreeNode res2 = bsh.search(5, root);
        System.out.println("删除【5】后：" + (res2 == null ? "null" : res.val));
    }
}

3.中序遍历有序

二叉树的中序遍历遵循："left->root->right"的规则，而二叉搜索树满足"左节点<根节点<右节点"的关系，因此通过中序遍历二叉搜索树得到的序列是升序的

基于此，在二叉搜索树中获取有序数据的时间只需要O(n)时间，而无序进行额外的排序，操作效率非常高

4.二叉搜索树的效率

给定一组数据，考虑使用数组或二叉搜索树存储。二叉搜索树的各项操作的时间复杂度都是对数阶，具有稳定且高效的性能。只有在高频添加、低频查找删除数据的场景下，数组比二叉搜索树的效率更高

操作	无序数组	二叉搜索树
查找元素	O(n)	O(log n)
插入元素	O(1)	O(log n)
删除元素	O(n)	O(log n)

在理想情况下，二叉搜索树是“平衡”的，这样就可以在 log⁡n 轮循环内查找任意节点。然而，如果在二叉搜索树中不断地插入和删除节点，可能导致二叉树倾斜的链表形式，这时各种操作的时间复杂度也会退化为 O(n)

二叉搜索树的应用

用作系统中的多级索引，实现高效的查找、插入、删除操作
作为某些搜索算法的底层数据结构
用于存储数据流，以保持其有序状态

AVL 树（*）

场景分析："二叉搜索树"什么时候退化为链表？

在多次插入和删除操作后，二叉搜索树可能退化为链表。在这种情况下，所有操作的时间复杂度将从 O(log⁡n) 劣化为 O(n)

案例1：参考下述图示案例（经过两次删除操作，二叉搜索树逐步退化为链表形式）

案例2：参考下述图示案例（完美二叉树中插入两个节点后，树严重向左倾斜，查找操作的时间复杂度也随之劣化）

1962 年 G. M. Adelson-Velsky 和 E. M. Landis 在论文“An algorithm for the organization of information”中提出了 AVL 树。论文中详细描述了一系列操作，确保在持续添加和删除节点后，AVL 树不会退化，从而使得各种操作的时间复杂度保持在 O(log⁡n) 级别。换句话说，在需要频繁进行增删查改操作的场景中，AVL 树能始终保持高效的数据操作性能，具有很好的应用价值

1.AVL 树概念核心

AVL 树既是二叉搜索树，也是平衡二叉树，同时满足这两类二叉树的所有性质，因此是一种平衡二叉搜索树（balanced binary search tree）

height属性：AVL树的相关操作涉及到节点高度，因此对于AVL树的节点需要增设height属性用于记录节点高度。节点高度”是指从该节点到它的最远叶节点的距离，即所经过的“边”的数量。需要特别注意的是，叶节点的高度为 0 ，而空节点的高度为 −1

平衡因子：节点的平衡因子（balance factor）定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为 0 （设平衡因子为 f ，则一棵 AVL 树的任意节点的平衡因子皆满足 −1≤f≤1 ）

操作工具函数：定义操作工具函数便于节点操作，此处提供获取和更新节点的高度、获取节点平衡因子

/**
 * AVL 节点定义
 */
class AVLTreeNode {
    // 定义节点值
    int val;
    // 定义节点高度（该节点到离它最远的节点距离，即所经过的边数量）
    int height;
    // 定义左节点
    AVLTreeNode left;
    // 定义右节点
    AVLTreeNode right;
    // 构造函数
    public AVLTreeNode(int val) {
        this.val = val;
    }

    // 操作工具函数：获取、更新节点高度

    /* 获取节点高度 */
    int height(AVLTreeNode node) {
        // 空节点高度为 -1 ，叶节点高度为 0
        return node == null ? -1 : node.height;
    }

    /* 更新节点高度 */
    void updateHeight(AVLTreeNode node) {
        // 节点高度等于最高子树高度 + 1
        node.height = Math.max(height(node.left), height(node.right)) + 1;
    }

    /* 获取平衡因子 */
    int balanceFactor(AVLTreeNode node) {
        // 空节点平衡因子为 0
        if (node == null)
            return 0;
        // 节点平衡因子 = 左子树高度 - 右子树高度
        return height(node.left) - height(node.right);
    }
}

2.AVL树旋转

核心：先构建AVL树的基础结构（属性定义、工具类定义），然后分析AVL树旋转的各个情况，基于这些情况进行拆装

AVL 树的特点在于“旋转”操作，它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡。换句话说，旋转操作既能保持“二叉搜索树”的性质，也能使树重新变为“平衡二叉树”。

将平衡因子绝对值 >1 的节点称为“失衡节点”。根据节点失衡情况的不同，旋转操作分为四种：右旋、左旋、先右旋后左旋、先左旋后右旋

🟢 右旋（侧左边需右旋）

从底部->顶部看，二叉树中首个失衡节点是3，关注以该失衡节点为根节点的子树，将该节点标记为node，其左子节点记为child，执行右旋操作

结合图示分析，其核心是以child作为原点，将node右旋至其右节点位置，然后用child替代node之前的位置

![image-20240930091031288](1.算法-基础篇-02-数据结构-D(树) .assets/image-20240930091031288.png)

当节点child有右节点（grand_child）时（此时无法直接右旋覆盖），需要在右旋中添加一步，将grand_child作为node的左子节点，然后再执行右旋操作

结合图示分析，当child有右节点，需要以child为原点，将node右旋至其右节点位置，并将grand_child作为node的左子节点，然后用child替代node之前的位置

此处如何理解grandchild的处理，可以理解为当要执行右旋的时候发现child原有的右节点位置上已经有元素挡住了，因此右旋的过程中需要将这个元素进行处理，因为AVL满足搜索树特性，始终确保"left<root<right"，因此要将grandchild重新挂靠在node节点就只能挂在其左边（同理左旋也是类似的，左旋过程中发现child存在左节点grandchild，因此要将grandchild挂在node的右边）

上述图示分析中的"右旋操作"是一种抽象的概念表达，实际上是通过修改节点指针来实现的，代码分析如下

// 右旋操作
AVLTreeNode rightRotate(AVLTreeNode node) {
    // 定义相关节点（child：旋转原点（node的左节点）、grandchild：child的右节点）
    AVLTreeNode child = node.left;
    AVLTreeNode grandchild = child.right;
    // 执行右旋操作（即将node置于child的右节点位置，child替换原来node的位置）
    child.right = node;
    // 判断grandchild是否为null（如果不为null，需要先将grandchild作为node的左节点）
    node.left = grandchild;
    // 更新节点高度（更新node、child的节点高度）
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后的子树的根节点（此处可以理解为child替换原来node的位置，即传入的是node，右旋返回的是child替换了node的位置）
    return child;
}

🟢 左旋（侧右边需左旋）

类似地，如果考虑上述失衡二叉树的"镜像"，则执行"左旋操作"

步骤分析：

选定失衡节点node，将失衡节点node的右节点记为child，将child的左节点记为grandchild
执行左旋操作（将node置于child的左节点位置），且如果child存在左节点grandchild 则相应需在左旋过程中将grandchild作为node的左节点，最后返回child（相当于child替换了传入的node位置）

// 左旋操作
AVLTreeNode leftRotate(AVLTreeNode node) {
    // 1.定义相关操作节点
    AVLTreeNode child = node.right;
    AVLTreeNode grandchild = child.left;
    // 2.执行左旋操作
    child.left = node; // 将node置于child的左节点
    node.right = grandchild; // 如果存在grandchild，则需将grandchild作为node的右节点
    // 3.更新节点高度（更新node、child的值）
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后的子树的根节点（即旋转原点child，表示其替换了node的位置）
    return child;
}

右旋和左旋操作在逻辑上是镜像对称的，它们分别解决的两种失衡情况也是对称的。基于上述分析，左旋的场景是右旋的"镜像"，从代码层面上来看，将右旋的代码中的left和right相互对调则可以得到左旋的代码逻辑

🟢 先左旋后右旋

对于下图所示的失衡节点 3 ，仅使用左旋或右旋都无法使子树恢复平衡。此时需要先对 child 执行“左旋”，再对 node 执行“右旋”

🟢 先右旋后左旋

类似的，如果出现上述失衡二叉树的镜像情况，需要先对 child 执行“右旋”，再对 node 执行“左旋”

🟢 旋转的选择

图示展示的四种失衡情况与上述案例逐个对应，分别需要采用右旋、先左旋后右旋、先右旋后左旋、左旋的操作

如何敲定是左旋还是右旋？（可以简单理解为关注失衡子树（即从底部到顶部最近的失衡节点为根节点的子树），一边倒侧左边就右旋，一边倒侧右边就左旋，如果左右不平衡则先左后右或先右后左）

选定失衡节点node，确定其child
然后思考要将node变成child的子节点应该要往哪个方向旋转
- 例如图示1右旋场景，以1为原点，要把3放在1的右边则需执行右旋操作；类似地，图示4左旋场景，以5为原点，要把3放在5的左边则需执行左旋操作
- 而对于不是一边倒的情况，则采用两种旋转方式将其变为一边倒的情况，回归场景1、4
  - 即对于图示2场景，需将child作为node看待进行旋转（此时1要放在2的左边，则以2原点执行左旋操作），然后就会得到一个一边倒的失衡子树，此时再正常进行右旋操作。即对于不是一边倒的失衡子树的处理，先对child进行旋转，然后再对node进行旋转（至于旋转方向的选择取决于对应的旋转原点参考）

以函数角度分析来看，则是对节点的平衡因子的分析，即看失衡节点和其子节点的平衡因子：

失衡节点的平衡因子	子节点的平衡因子	应采取的旋转方法
>1 左偏树	≥ 0	右旋
>1 左偏树	＜0	先左旋后右旋
< -1 右偏树	≤ 0	左旋
< -1 右偏树	＞0	先右旋后左旋

基于这个函数梳理，则可定义一个完整的旋转方案，能够完美应对各种失衡情况

// 旋转操作（执行旋转操作，使子树恢复平衡）
AVLTreeNode rotate(AVLTreeNode node){
    // 根据节点的平衡因子进行判断（判断node节点和其对应的子节点的平衡因子，采取相应的旋转方案）

    // 左偏树
    if(balanceFactor(node)>1){
        // 判断左节点的平衡因子
        if(balanceFactor(node.left)>=0){
            // 执行右旋
            return rightRotate(node);
        }else{
            // 先左旋后右旋(先对子节点左旋，后对node右旋)
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
    }

    // 右偏树
    if(balanceFactor(node)<-1){
        // 判断右节点的平衡因子
        if(balanceFactor(node.right)<=0){
            // 执行左旋
            return leftRotate(node);
        }else{
            // 先右旋后左旋(先对子节点右旋，后对node节点左旋)
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

    }

    // 平衡树（无需旋转，直接返回）
    return node;
}

3.AVL 树常用操作

插入节点

AVL 树的节点插入操作与二叉搜索树在主体上类似。唯一的区别在于，在 AVL 树中插入节点后，从该节点到根节点的路径上可能会出现一系列失衡节点。因此，需要从这个节点开始，自底向上执行旋转操作，使所有失衡节点恢复平衡。

/* 递归插入节点（辅助方法） */
AVLTreeNode insertHelper(AVLTreeNode node, int val) {
    if (node == null)
        return new AVLTreeNode(val);
    /* 1. 查找插入位置并插入节点 */
    if (val < node.val)
        node.left = insertHelper(node.left, val);
    else if (val > node.val)
        node.right = insertHelper(node.right, val);
    else
        return node; // 重复节点不插入，直接返回
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

删除节点

类似地，在二叉搜索树的删除节点方法的基础上，需要从底至顶执行旋转操作，使所有失衡节点恢复平衡

/* 递归删除节点（辅助方法） */
AVLTreeNode removeHelper(AVLTreeNode node, int val) {
    if (node == null)
        return null;
    /* 1. 查找节点并删除 */
    if (val < node.val)
        node.left = removeHelper(node.left, val);
    else if (val > node.val)
        node.right = removeHelper(node.right, val);
    else {
        if (node.left == null || node.right == null) {
            AVLTreeNode child = node.left != null ? node.left : node.right;
            // 子节点数量 = 0 ，直接删除 node 并返回
            if (child == null)
                return null;
            // 子节点数量 = 1 ，直接删除 node
            else
                node = child;
        } else {
            // 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
            AVLTreeNode temp = node.right;
            while (temp.left != null) {
                temp = temp.left;
            }
            node.right = removeHelper(node.right, temp.val);
            node.val = temp.val;
        }
    }
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

查找节点

AVL 树的节点查找操作与二叉搜索树一致

4.AVL树典型应用

组织和存储大型数据，适用于高频查找、低频增删的场景
用于构建数据库中的索引系统
红黑树也是一种常见的平衡二叉搜索树。相较于 AVL 树，红黑树的平衡条件更宽松，插入与删除节点所需的旋转操作更少，节点增删操作的平均效率更高

昵称

邮箱

网址

按正序
按倒序
按热度

算法-基础篇-②数据结构-D(树)

预览: