AVL树是一种自平衡的二叉搜索树，由Adelson-Velsky和Landis在1962年提出。它的特点是每个节点的左右子树高度差不超过1，因此能够保证在最坏情况下，查找、插入和删除操作的时间复杂度为O(log n)。本文将介绍如何在C++中实现AVL树。
AVL树的节点结构通常包含以下几个部分：
计算
安全
数据库
网络和加速
企业服务
struct AVLNode {
int data;
AVLNode* left;
AVLNode* right;
int height;
AVLNode(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
};
为了计算平衡因子，我们需要一个函数来获取节点的高度。如果节点为空，则高度为0。
int getHeight(AVLNode* node) {
if (node == nullptr) return 0;
return node->height;
}
平衡因子是节点的左子树高度减去右子树高度。如果平衡因子的绝对值大于1，则需要进行旋转操作来恢复平衡。
int getBalanceFactor(AVLNode* node) {
if (node == nullptr) return 0;
return getHeight(node->left) - getHeight(node->right);
}
在插入或删除节点后，需要更新节点的高度。
void updateHeight(AVLNode* node) {
if (node == nullptr) return;
node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
}
AVL树通过旋转操作来恢复平衡。主要有四种旋转方式：左旋、右旋、左右旋和右左旋。
左旋用于处理右子树过高的情况。
AVLNode* leftRotate(AVLNode* y) {
AVLNode* x = y->right;
AVLNode* T2 = x->left;
x->left = y;
y->right = T2;
updateHeight(y);
updateHeight(x);
return x;
}
右旋用于处理左子树过高的情况。
AVLNode* rightRotate(AVLNode* x) {
AVLNode* y = x->left;
AVLNode* T2 = y->right;
y->right = x;
x->left = T2;
updateHeight(x);
updateHeight(y);
return y;
}
左右旋用于处理左子树的右子树过高的情况。
AVLNode* leftRightRotate(AVLNode* z) {
z->left = leftRotate(z->left);
return rightRotate(z);
}
右左旋用于处理右子树的左子树过高的情况。
AVLNode* rightLeftRotate(AVLNode* z) {
z->right = rightRotate(z->right);
return leftRotate(z);
}
插入节点的过程与普通二叉搜索树类似，但在插入后需要检查平衡因子并进行相应的旋转操作。
AVLNode* insert(AVLNode* root, int val) {
if (root == nullptr) return new AVLNode(val);
if (val < root->data) {
root->left = insert(root->left, val);
} else if (val > root->data) {
root->right = insert(root->right, val);
} else {
return root; // 不允许插入重复值
}
updateHeight(root);
int balance = getBalanceFactor(root);
// 左子树过高
if (balance > 1) {
if (val < root->left->data) {
return rightRotate(root);
} else {
return leftRightRotate(root);
}
}
// 右子树过高
if (balance < -1) {
if (val > root->right->data) {
return leftRotate(root);
} else {
return rightLeftRotate(root);
}
}
return root;
}
删除节点的过程也与普通二叉搜索树类似，但在删除后需要检查平衡因子并进行相应的旋转操作。
AVLNode* deleteNode(AVLNode* root, int val) {
if (root == nullptr) return root;
if (val < root->data) {
root->left = deleteNode(root->left, val);
} else if (val > root->data) {
root->right = deleteNode(root->right, val);
} else {
if (root->left == nullptr || root->right == nullptr) {
AVLNode* temp = root->left ? root->left : root->right;
if (temp == nullptr) {
temp = root;
root = nullptr;
} else {
*root = *temp;
}
delete temp;
} else {
AVLNode* temp = findMin(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
if (root == nullptr) return root;
updateHeight(root);
int balance = getBalanceFactor(root);
// 左子树过高
if (balance > 1) {
if (getBalanceFactor(root->left) >= 0) {
return rightRotate(root);
} else {
return leftRightRotate(root);
}
}
// 右子树过高
if (balance < -1) {
if (getBalanceFactor(root->right) <= 0) {
return leftRotate(root);
} else {
return rightLeftRotate(root);
}
}
return root;
}
AVL树通过旋转操作来保持树的平衡，从而保证了查找、插入和删除操作的高效性。本文介绍了如何在C++中实现AVL树的基本操作，包括插入、删除和旋转操作。通过理解和掌握这些基本操作，可以更好地应用AVL树来解决实际问题。
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
