数据结构之——AVL树

一、AVL 树的概念与起源

AVL 树，即高度平衡的二叉搜索树，由俄罗斯科学家 G.M.Adelson-Velskii 和 E.M.Landis 共同发明。AVL 树可以定义为高度平衡二叉搜索树，其中每个结点与平衡因子相关联，该平衡因子通过从其左子树的子树中减去其右子树的高度来计算。如果每个结点的平衡因子在 -1 到 1 之间，则称树是平衡的，否则，树将是不平衡的并且需要重新平衡。

AVL 树通过不让它倾斜来控制二叉搜索树的高度。高度为 h 的二叉搜索树中的所有操作所花费的时间是 O (h)。但是，如果二叉搜索树变得偏斜，它可以扩展到 O (n)。通过将高度限制为 log n，AVL 树将每个操作的上限强加为 O (log n)，其中 n 是结点的数量。

例如，高度为 h 的 AVL 树，节点数 N 最多为 2^h - 1；最少为 Nh = F【h + 2】 - 1，这里的 F【h + 2】是 Fibonacci polynomial 的第 h + 2 个数。最少节点数可以用数学归纳法证明，如 N0 = 0（表示 AVL Tree 高度为 0 的节点总数），N1 = 1（表示 AVL Tree 高度为 1 的节点总数），N2 = 2（表示 AVL Tree 高度为 2 的节点总数），Nh = N【h - 1】 + N【h - 2】 + 1（表示 AVL Tree 高度为 h 的节点总数）。换句话说，当节点数为 N 时，高度 h 最多为 logN + 2。

二、AVL 树的结构与特性

（一）AVL 树的结构

AVL 树的节点结构通常包含以下几个部分：

值：存储具体的数据元素。
平衡因子：用于衡量节点左右子树的高度差。平衡因子的计算方法为右子树的高度减去左子树的高度。例如，节点 A 的左子树高度为 2，右子树高度为 1，那么节点 A 的平衡因子为 2 - 1 = 1。
左右子树引用：分别指向该节点的左子树和右子树，通过这些引用可以构建出树的结构。
父节点引用：用于在插入和删除节点时调整平衡因子等操作，方便快速找到父节点。

例如，在一些编程语言的实现中，AVL 树的节点结构可能如下定义：

// AVLTreeNode类用于表示AVL树中的节点
class AVLTreeNode {

    // 用于存储节点的值，这里假设存储的是整数类型的值
    int value;

    // 平衡因子，用于衡量节点左右子树的高度差，以确定AVL树是否保持平衡
    // 平衡因子的计算通常是右子树高度减去左子树高度
    int balanceFactor;

    // 指向节点的左子节点的引用，如果左子节点不存在，则为null
    AVLTreeNode leftChild;

    // 指向节点的右子节点的引用，如果右子节点不存在，则为null
    AVLTreeNode rightChild;

    // 指向节点的父节点的引用，如果是根节点，则父节点为null
    AVLTreeNode parent;

    // AVLTreeNode类的构造函数，用于创建一个新的AVL树节点
    // 传入的参数value将被赋给节点的value成员变量
    public AVLTreeNode(int value) {
        // 将传入的参数value赋值给当前节点的value成员变量，以初始化节点的值
        this.value = value;

        // 初始化平衡因子为0，因为新创建的节点初始时认为是平衡的
        balanceFactor = 0;

        // 初始化左子节点引用为null，因为新创建节点时可能还没有左子节点
        leftChild = null;

        // 初始化右子节点引用为null，因为新创建节点时可能还没有右子节点
        rightChild = null;

        // 初始化父节点引用为null，因为新创建节点时可能是根节点，没有父节点
        parent = null;
    }
}

（二）AVL 树的特性

AVL 树具有以下重要特性：

左右子树都是 AVL 树：这意味着整个树的平衡性质是递归定义的。即不仅根节点要满足平衡条件，其所有子树也都必须是 AVL 树。
高度差绝对值不超过 1：每个结点的左右子树的高度之差的绝对值不能超过 1。这一特性保证了树的高度相对较低，从而使得查找、插入和删除操作的时间复杂度在平均和最坏情况下都是 O (log n)。其中 n 是结点的数量。例如，在一个高度为 h 的 AVL 树中，节点数最多为 2^h - 1，最少为 Nh = F【h + 2】 - 1，这里的 F【h + 2】是 Fibonacci polynomial 的第 h + 2 个数。

综上所述，AVL 树通过其特殊的节点结构和严格的平衡特性，在保证高效查找、插入和删除操作方面具有显著优势。

三、AVL 树的实现方法

（一）插入操作

AVL 树的插入操作首先按照二叉搜索树的规则进行插入。具体来说，如果树为空，则插入的节点成为根节点；如果树不为空，则从根节点开始，比较要插入的节点值与当前节点值的大小，若小于当前节点值则向左子树继续寻找插入位置，若大于则向右子树寻找。找到合适位置后，将新节点插入。

插入节点后，需要修改平衡因子。如果新节点插入在父节点的左子树中，则父节点的平衡因子减 1；如果插入在右子树中，则父节点的平衡因子加 1。然后向上更新平衡因子，一直更新到根节点或者遇到平衡因子为 0 的节点停止。如果父节点的平衡因子变为 2 或 -2，则需要进行旋转操作。

（二）旋转操作

旋转操作的原则是保持搜索树的规则，使子树变平衡。AVL 树有四种旋转方式：左单旋、右单旋、左右双旋、右左双旋。

左单旋：新结点插入在较高右子树右侧时进行左单旋。例如，节点 A 的右子树较高，新节点插入在 A 的右子树的右侧。此时，先将 A 的右子树的左子树（记为 subRL）连接到 A 上，然后将 A 连接到其右子树的左子树上，最后更新平衡因子，A 和其右子树的平衡因子都变为 0。
右单旋：新结点插入在较高左子树左侧时进行右单旋。与左单旋类似，先将节点 A 的左子树的右子树（记为 subLR）连接到 A 上，然后将 A 连接到其左子树的右子树上，最后更新平衡因子。
左右双旋：新结点插入在较高左子树右侧时进行左右双旋。先对较高左子树进行左单旋，再对整棵树进行右单旋。例如，新节点插入在节点 A 的左子树的右侧，先以 A 的左子树为中心进行左单旋，再以 A 为中心进行右单旋。在旋转前，需要记录 A 的左子树的右子树（记为 subLR）的平衡因子，根据平衡因子的值来调整旋转后的平衡因子。如果 subLR 的平衡因子为 1，则在旋转后将 A 的左子树的平衡因子设为 -1，其他为 0；如果为 -1，则将 A 的平衡因子设为 1，其他为 0；如果为 0，则所有平衡因子设为 0。
右左双旋：新结点插入在较高右子树左侧时进行右左双旋。先对较高右子树进行右单旋，再对整棵树进行左单旋。操作过程与左右双旋类似，同样需要根据旋转前较高右子树的左子树的平衡因子来调整旋转后的平衡因子。

四、AVL 树的应用场景

AVL 树由于其高效的查找、插入和删除操作，在多个领域有着广泛的应用。

（一）数据库索引

数据库系统常用 AVL 树作为索引结构。据统计，在大型数据库中，AVL 树能够在平均和最坏情况下提供高效的查找、插入和删除操作，其时间复杂度为 O (log n)。通过维护平衡的树结构，AVL 树可以确保快速的数据访问和更新，从而提高查询效率。例如，在一个拥有百万条数据的数据库中，使用 AVL 树作为索引结构进行查找操作，相比普通二叉搜索树，可以大大减少查找时间。

（二）文件系统

在文件系统中，AVL 树可用于管理文件目录和元数据。文件系统需要频繁地插入、删除和查找文件，而 AVL 树的平衡特性确保这些操作可以在对数时间内完成。例如，在一个包含数千个文件的文件系统中，使用 AVL 树管理文件目录，可以快速定位特定文件，提高文件系统的性能。

（三）内存管理

在操作系统和虚拟内存管理中，AVL 树可以用于管理空闲内存块。内存分配和释放操作需要快速、高效地管理空闲内存块，AVL 树通过保持平衡确保这些操作在对数时间内完成，提高内存管理的效率。例如，当系统需要分配一块内存时，可以使用 AVL 树快速找到合适大小的空闲内存块进行分配。

（四）动态集合

AVL 树适用于实现动态集合数据结构，例如集合、地图和多重集合。在这些应用中，集合元素的插入、删除和查找操作都需要高效的执行，AVL 树的平衡特性能够满足这些需求。例如，在一个动态集合中，使用 AVL 树可以快速地进行元素的插入和删除操作，同时保证集合的有序性。

五、AVL 树与其他数据结构的比较

（一）与二叉树比较

二叉树是一种简单的数据结构，每个节点最多有两个子节点。然而，二叉树没有自平衡机制，这可能导致树的不平衡，进而影响搜索效率。在极端情况下，二叉树可能退化为线性链表，此时查找、插入和删除操作的时间复杂度变为。

相比之下，AVL 树是一种高度平衡的二叉搜索树，通过严格的平衡条件保证了树的高度相对较低。每个结点的左右子树的高度之差的绝对值不能超过 1，这使得 AVL 树在查找、插入和删除操作中具有较快的时间复杂度，平均和最坏情况下都是，其中是结点的数量。

（二）与红黑树比较

红黑树是一种弱平衡二叉树，相对 AVL 树来说，实现更加简单。红黑树的平衡要求较低，通过对节点颜色的限制来保持平衡。红黑树的插入和删除操作最多需要三次旋转，而 AVL 树在插入和删除操作中可能需要多次旋转来保持平衡，因此红黑树在插入和删除操作较多的场景下性能更好。

然而，在查找操作较多的场景下，AVL 树由于其严格的平衡特性，可能会比红黑树更快。例如，在一个拥有 10000 个节点的树中，进行查找操作时，AVL 树的平均查找次数可能会比红黑树少。

（三）与 B 树和 B + 树比较

B 树和 B + 树是多路搜索树，适用于大规模数据存储。B 树的每个节点可以拥有多个子节点，能够有效地减少磁盘 I/O 操作。B + 树在 B 树的基础上进行了改进，只有叶子节点存储实际数据，内部节点只存储索引，这使得 B + 树在范围查询和顺序访问方面具有更好的性能。

与 AVL 树相比，B 树和 B + 树更适合处理大规模数据存储的场景。AVL 树主要适用于内存中的数据结构，对于大规模数据存储在磁盘上的情况，B 树和 B + 树能够更好地利用磁盘的特性，减少磁盘 I/O 次数，提高查询效率。

例如，在一个数据库系统中，如果数据量非常大，使用 B + 树作为索引结构可以更好地满足大规模数据存储和高效查询的需求，而 AVL 树在这种场景下可能会因为内存限制和频繁的旋转操作而性能下降。

AVL 树的 C 语言代码实现示例

以下是用 C 语言实现 AVL 树的示例代码：

#include <stdio.h>
#include <stdlib.h>

// 定义AVL树节点结构体
typedef struct AVLTreeNode {
    // 节点存储的键值，用于比较和排序节点在树中的位置
    int key;
    // 节点的高度，用于衡量以该节点为根的子树的高度，方便后续进行平衡调整
    int height;
    // 指向节点左子树的指针，如果左子树不存在则为NULL
    struct AVLTreeNode *left;
    // 指向节点右子树的指针，如果右子树不存在则为NULL
    struct AVLTreeNode *right;
} AVLTreeNode;

// 比较两个整数并返回较大值的函数
int max(int a, int b) {
    // 使用三目运算符判断a和b的大小，返回较大值
    return (a > b)? a : b;
}

// 计算给定节点的高度函数
// 如果节点为NULL，说明是空树或者到达了树的叶子节点的子节点（空子树），高度为0
// 否则返回节点自身存储的高度值
int height(AVLTreeNode *node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 创建一个新的AVL树节点的函数
// 接受一个键值作为参数，用于初始化新节点
AVLTreeNode* newAVLTreeNode(int key) {
    // 使用malloc动态分配内存来创建一个AVLTreeNode结构体大小的空间
    AVLTreeNode* node = (AVLTreeNode*) malloc(sizeof(AVLTreeNode));
    // 将传入的键值赋给新节点的key成员变量
    node->key = key;
    // 初始化新节点的左子树指针为NULL，表示暂时没有左子树
    node->left = NULL;
    // 初始化新节点的右子树指针为NULL，表示暂时没有右子树
    node->right = NULL;
    // 初始化新节点的高度为1，因为新创建的节点作为单独的节点时高度为1
    node->height = 1;
    // 返回创建好的新节点指针
    return node;
}

// 对AVL树进行右旋转操作的函数
// 传入要旋转的节点y，通常是在发现左子树过高需要进行平衡调整时调用
AVLTreeNode* rightRotate(AVLTreeNode *y) {
    // 将y的左子节点x保存起来，x将成为旋转后的新根节点
    AVLTreeNode *x = y->left;
    // 将x的右子节点T2保存起来，旋转后T2将成为y的左子节点
    AVLTreeNode *T2 = x->right;

    // 进行旋转操作，将x的右子节点指向y
    x->right = y;
    // 将y的左子节点指向T2
    y->left = T2;

    // 更新y的高度，通过比较其左右子树高度的最大值并加1来计算
    y->height = max(height(y->left), height(y->right)) + 1;
    // 更新x的高度，同样通过比较其左右子树高度的最大值并加1来计算
    x->height = max(height(x->left), height(x->right)) + 1;

    // 返回旋转后的新根节点x
    return x;
}

// 对AVL树进行左旋转操作的函数
// 传入要旋转的节点x，通常是在发现右子树过高需要进行平衡调整时调用
AVLTreeNode* leftRotate(AVLTreeNode *x) {
    // 将x的右子节点y保存起来，y将成为旋转后的新根节点
    AVLTreeNode *y = x->right;
    // 将y的左子节点T2保存起来，旋转后T2将成为x的右子节点
    AVLTreeNode *T2 = y->left;

    // 进行旋转操作，将y的左子节点指向x
    y->left = x;
    // 将x的右子节点指向T2
    x->right = T2;

    // 更新x的高度，通过比较其左右子树高度的最大值并加1来计算
    x->height = max(height(x->left), height(x->right)) + 1;
    // 更新y的高度，同样通过比较其左右子树高度的最大值并加1来计算
    y->height = max(height(y->left), height(y->right)) + 1;

    // 返回旋转后的新根节点y
    return y;
}

// 计算给定节点的平衡因子的函数
// 平衡因子定义为节点左子树高度减去右子树高度的值
// 如果节点为NULL，平衡因子为0
int getBalance(AVLTreeNode *node) {
    if (node == NULL) {
        return 0;
    }
    return height(node->left) - height(node->left) - height(node->right);
}

// 向AVL树中插入节点的函数
// 接受一个指向当前树的根节点的指针node和要插入的键值key作为参数
AVLTreeNode* insert(AVLTreeNode* node, int key) {
    // 如果当前节点为NULL，说明已经到达了合适的插入位置（空子树），创建一个新节点并返回
    if (node == NULL) {
        return newAVLTreeNode(key);
    }

    // 如果要插入的键值小于当前节点的键值，说明应该插入到当前节点的左子树中
    if (key < node->key) {
        // 递归调用insert函数在左子树中插入节点，并将返回的新节点指针赋给当前节点的左子树指针
        node->left = insert(node->left, key);
    }
    // 如果要插入的键值大于当前节点的键值，说明应该插入到当前节点的右子树中
    else if (key > node->key) {
        // 递归调用insert函数在右子树中插入节点，并将返回的新节点指针赋给当前节点的右子树指针
        node->right = insert(node->right, key);
    }
    // 如果要插入的键值等于当前节点的键值，说明节点已经存在，直接返回当前节点
    else {
        return node;
    }

    // 更新当前节点的高度，通过比较其左右子树高度的最大值并加1来计算
    node->height = 1 + max(height(node->left), height(node->right));

    // 计算当前节点的平衡因子
    int balance = getBalance(node);

    // 如果平衡因子大于1且要插入的键值小于当前节点左子节点的键值，说明出现了左左型不平衡
    // 需要进行先右旋转操作来恢复平衡
    if (balance > 1 && key < node->left->key) {
        return rightRotate(node);
    }

    // 如果平衡因子小于 -1且要插入的键值大于当前节点右子节点的键值，说明出现了右右型不平衡
    // 需要进行先左旋转操作来恢复平衡
    if (balance < -1 && key > node->right->key) {
        return leftRotate(node);
    }

    // 如果平衡因子大于1且要插入的键值大于当前节点左子节点的键值，说明出现了左右型不平衡
    // 需要先对左子树进行左旋转，再对当前节点进行右旋转操作来恢复平衡
    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // 如果平衡因子小于 -1且要最后一个if语句中多了一个判断条件，应该去掉多余的判断条件“height(node->left) - height(node->left)”，改为：

    // 如果平衡因子小于 -1且要插入的键值小于当前节点右子节点的键值，说明出现了右左型不平衡
    // 需要先对右子树进行右旋转，再对当前节点进行左旋转操作来恢复平衡
    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    // 如果插入节点后树仍然保持平衡，或者经过旋转操作已经恢复平衡，返回当前节点
    return node;
}

// 对AVL树进行前序遍历的函数
// 接受一个指向树的根节点的指针root作为参数
void preOrderTraversal(AVLTreeNode *root) {
    // 如果根节点不为NULL，说明树不为空
    if (root!= NULL) {
        // 先输出根节点的键值
        printf("%d ", root->key);
        // 然后递归调用preOrderTraversal函数遍历左子树
        preOrderTraversal(root->left);
        // 最后递归调用preOrderTraversal函数遍历右子树
        preOrderTraversal(root->right);
    }
}

可以使用以下方式调用这个函数：

int main() {
    AVLTreeNode *root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    printf("Preorder traversal of the AVL tree is: ");
    preOrderTraversal(root);
    printf("\n");

    return 0;
}

这段代码实现了 AVL 树的插入操作和前序遍历。插入操作会在插入节点后检查树的平衡性，并进行必要的旋转操作以保持树的平衡。前序遍历可以用于验证树的结构和节点的值。

在实际应用中，可以根据需要对代码进行扩展和修改，例如添加删除节点的功能、实现中序遍历或后序遍历等。同时，还可以使用 AVL 树来解决各种实际问题，如高效的搜索、排序和数据存储等。

总之，AVL 树是一种非常有用的数据结构，通过 C 语言实现可以更好地理解其原理和应用。

标签：node,左子,右子,AVL,平衡,数据结构,节点
From： https://blog.csdn.net/m0_71974552/article/details/143931221