跳转到主内容
趣航编程网 - 趣学编程,启航技术之路!

C++怎么实现一个AVL树_C++数据结构与AVL树实现

AVL树通过维持左右子树高度差不超过1来保证操作时间复杂度为O(log n),需在插入删除后更新高度并进行旋转调整。 AVL树是一种自平衡的二叉搜索树,它通过维持左右子树的高度差不超过1来保证树的整体高度始终接近log(n),从而确保查找、插入和删除操作的时间复杂度为O(log n)。在C++中实现AVL树需要理解二叉搜索树的基本结构,并加入平衡因子的维护与旋转操作。 AVL树节点设计 每个节点除了存储值外,还需要记录当前子树的高度,以便计算平衡因子(左子树高度减右子树高度):
struct Node { int data; Node* left; Node* right; int height;
Node(int value) : data(value), left(nullptr), right(nullptr), height(1) {}
}; 高度初始化为1,因为单个节点的高度是1(不是0)。 立即学习 “ C++免费学习笔记(深入) ”; 基本操作:获取高度与平衡因子 封装两个辅助函数用于判断是否失衡以及进行后续旋转:
int getHeight(Node* node) { return node ? node->height : 0; }

int getBalanceFactor(Node* node) { return node ? getHeight(node->left) - getHeight(node->right) : 0; }

这两个函数会在插入和删除后频繁调用,用来决定是否需要旋转调整。 四种旋转操作 当某个节点的平衡因子大于1或小于-1时,就需要通过旋转恢复平衡。共四种情况: 右旋(LL型) 适用于左子树过高且新节点插入在左侧路径上:
Node* rotateRight(Node* y) { Node* x = y->left; Node* T2 = x->right;
x->right = y;
y->left = T2;

y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

return x; // 新的根
}C函数速查手册(CHM版)C函数速查手册(CHM版)下载 左旋(RR型) 适用于右子树过高:
Node* rotateLeft(Node* x) { Node* y = x->right; Node* T2 = y->left;
y->left = x;
x->right = T2;

x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

return y; // 新的根
} 左右双旋(LR型) 先对左孩子左旋,再对当前节点右旋:
Node* rotateLeftRight(Node* node) { node->left = rotateLeft(node->left); return rotateRight(node); }
右左双旋(RL型) 先对右孩子右旋,再对当前节点左旋:
Node* rotateRightLeft(Node* node) { node->right = rotateRight(node->right); return rotateLeft(node); }
插入操作 插入逻辑类似BST,但在递归返回过程中更新高度并检查平衡性:
Node* insert(Node* root, int value) { if (!root) return new Node(value);
if (value < root->data)
    root->left = insert(root->left, value);
else if (value > root->data)
    root->right = insert(root->right, value);
else
    return root; // 不允许重复键

root->height = max(getHeight(root->left), getHeight(root->right)) + 1;

int balance = getBalanceFactor(root);

// LL型
if (balance > 1 && value < root->left->data)
    return rotateRight(root);

// RR型
if (balance < -1 && value > root->right->data)
    return rotateLeft(root);

// LR型
if (balance > 1 && value > root->left->data)
    return rotateLeftRight(root);

// RL型
if (balance < -1 && value < root->right->data)
    return rotateRightLeft(root);

return root;
} 删除操作 删除节点需处理三种情况(无子、一子、两子),找到中序后继替代值,然后递归删除:
Node* findMin(Node* root) { while (root && root->left) root = root->left; return root; }

Node remove(Node root, int value) { if (!root) return root;

if (value < root->data)
    root->left = remove(root->left, value);
else if (value > root->data)
    root->right = remove(root->right, value);
else {
    if (!root->left || !root->right) {
        Node* temp = root->left ? root->left : root->right;
        delete root;
        return temp;
    } else {
        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = remove(root->right, temp->data);
    }
}

if (!root) return root;

root->height = max(getHeight(root->left), getHeight(root->right)) + 1;
int balance = getBalanceFactor(root);

// 同样四种旋转修复
if (balance > 1 && getBalanceFactor(root->left) >= 0)
    return rotateRight(root);

if (balance < -1 && getBalanceFactor(root->right) <= 0)
    return rotateLeft(root);

if (balance > 1 && getBalanceFactor(root->left) < 0)
    return rotateLeftRight(root);

if (balance < -1 && getBalanceFactor(root->right) > 0)
    return rotateRightLeft(root);

return root;
} 完整使用示例 可以封装成类,并提供遍历接口验证结构正确性:
class AVLTree { public: Node* root; AVLTree() : root(nullptr) {}
void insert(int value) { root = insert(root, value); }
void remove(int value) { root = remove(root, value); }

void inorder(Node* node) {
    if (node) {
        inorder(node->left);
        cout << node->data << "(" << node->height << ") ";
        inorder(node->right);
    }
}

void printInorder() {
    inorder(root);
    cout << endl;
}
}; 测试代码:
int main() { AVLTree tree; tree.insert(10); tree.insert(20); tree.insert(5); tree.insert(6); tree.insert(15); tree.insert(25);
tree.printInorder(); // 输出应有序且各节点高度合理

tree.remove(6);
tree.printInorder();

return 0;
} 基本上就这些。只要掌握旋转时机和方式,AVL树就能稳定运行。虽然现在STL中的set/map多用红黑树实现,但AVL作为经典平衡树仍是学习数据结构的重要一环。

相关文章