从C语言到C++_27(AVL树)概念+插入接口实现(四种旋转)

**从 C语言到 C++: AVL 树的概念与插入接口实现**

在计算机科学中，AVL 树是一种自平衡二叉查找树（Balanced Binary Search Tree），它保证了每个节点的高度相差不超过1。这种数据结构是由 Adelson-Velskii 和 Landis 在1962 年提出的。AVL 树的主要特点是其高度始终保持在一个较小的范围内，这使得它成为查找、插入和删除操作的高效选择。

**概念**

AVL 树是一棵二叉树，每个节点最多有两个子节点（左孩子和右孩子）。每个节点都包含一个关键字（key），以及指向其左孩子和右孩子的指针。AVL 树的高度是从根到叶子的最大路径长度。

**插入接口实现**

在 C++ 中，我们可以使用类来实现 AVL 树的插入接口。下面是一个基本的例子：

cppclass Node {
public:
 int key;
 Node* left;
 Node* right;

 Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

class AVLTree {
private:
 Node* root;

public:
 AVLTree() : root(nullptr) {}

 void insert(int key);

 // ...
};

**插入函数**

下面是 `insert` 函数的实现：

cppvoid AVLTree::insert(int key) {
 if (root == nullptr) {
 root = new Node(key);
 } else {
 Node* current = root;
 while (true) {
 if (key < current->key) {
 if (current->left == nullptr) {
 current->left = new Node(key);
 balance(current);
 return;
 }
 current = current->left;
 } else if (key > current->key) {
 if (current->right == nullptr) {
 current->right = new Node(key);
 balance(current);
 return;
 }
 current = current->right;
 } else {
 // key already exists return;
 }
 }
 }
}

void AVLTree::balance(Node* node) {
 int balanceFactor = getHeight(node->left) - getHeight(node->right);

 if (balanceFactor >1) {
 if (getHeight(node->left->left) >= getHeight(node->left->right)) {
 // LL rotation rotateLL(node);
 } else {
 // LR rotation rotateLR(node);
 }
 } else if (balanceFactor < -1) {
 if (getHeight(node->right->right) >= getHeight(node->right->left)) {
 // RR rotation rotateRR(node);
 } else {
 // RL rotation rotateRL(node);
 }
 }

 return;
}

void AVLTree::rotateLL(Node* node) {
 Node* newRoot = node->left;
 node->left = newRoot->right;
 newRoot->right = node;

 updateHeight(node);
 updateHeight(newRoot);

 return;
}

void AVLTree::rotateLR(Node* node) {
 Node* newRoot = node->left;
 node->left = newRoot->right;
 newRoot->right = node->right;
 node->right = newRoot;

 updateHeight(node);
 updateHeight(newRoot);

 return;
}

void AVLTree::rotateRR(Node* node) {
 Node* newRoot = node->right;
 node->right = newRoot->left;
 newRoot->left = node;

 updateHeight(node);
 updateHeight(newRoot);

 return;
}

void AVLTree::rotateRL(Node* node) {
 Node* newRoot = node->right;
 node->right = newRoot->left;
 newRoot->left = node->left;
 node->left = newRoot;

 updateHeight(node);
 updateHeight(newRoot);

 return;
}

在上面的例子中，我们定义了一个 `Node` 类来表示 AVL 树中的每个节点。我们还定义了一个 `AVLTree` 类来管理整个树。

`insert` 函数负责将新键插入到 AVL 树中。当新键小于当前节点的键时，函数会向左子树移动；当新键大于当前节点的键时，函数会向右子树移动。我们使用 `balance` 函数来维护 AVL 树的平衡性。

在 `balance` 函数中，我们计算当前节点的平衡因子。如果平衡因子大于1，则意味着左子树过深；如果平衡因子小于 -1，则意味着右子树过深。我们使用四种旋转（LL、LR、RR 和 RL）来调整 AVL 树的结构，使其保持平衡。

在 `rotateLL`、`rotateLR`、`rotateRR` 和 `rotateRL` 函数中，我们实现了四种旋转的具体逻辑。当左子树过深时，我们使用 LL 或 LR 旋转；当右子树过深时，我们使用 RR 或 RL 旋转。

最后，我们在 `updateHeight` 函数中更新每个节点的高度，以便 AVL 树始终保持平衡。