当前位置：首页 > article >正文

数据结构(7.3_2)——平衡二叉树

article 2024/11/15 9:49:38

平衡二叉树，简称平衡树(AVL树)----树上任一结点的左子树和右子树的高度之差不超过1.

结点的平衡因子=左子树高-右子树高

//平衡二叉树结点
typedef struct AVLNode {
    int key;//数据域
    int blalance;//平衡因子
    struct AVLNode* lchild, * rchild;
}AVLNode,*AVLTree;

平衡二叉树的插入

在二叉排序树中插入新结点后，如何保持平衡？

调整最小不平衡子树

LL：

RR：

LR：

RL：

代码思路：

右旋转：

// 右旋转
Node *rightRotate(Node *y) {
    Node *x = y->left;
    Node *T2 = x->right;

    // 执行旋转
    x->right = y;
    y->left = T2;

    // 更新高度
    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

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

左旋转：

// 左旋转
Node *leftRotate(Node *x) {
    Node *y = x->right;
    Node *T2 = y->left;

    // 执行旋转
    y->left = x;
    x->right = T2;

    // 更新高度
    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

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