【平衡二叉树】数据结构

【平衡二叉树】数据结构—平衡二叉树

平衡二叉树（Balanced Binary Tree）是一种特殊的二叉树，它的左右子树的高度差不超过1，这样可以保证树的高度相对较低，从而使得查找、插入和删除操作的时间复杂度保持在 $O\left ( \log n \right )$ 。

平衡二叉树的基本概念

1. 二叉树：每个节点最多有两个子节点，分别称为左子节点和右子节点。
2. 平衡条件：对于每个节点，左子树和右子树的高度差的绝对值不超过1。
3. 高度：树的高度是从根节点到最深叶子节点的最长路径上的边的数量。

AVL树

AVL树是最早的自平衡二叉查找树，由G.M. Adelson-Velsky和E.M. Landis在1962年提出。AVL树通过在每个节点存储一个平衡因子（左子树高度减去右子树高度）来保持平衡。

AVL树的基本操作

1. 插入：插入新节点后，检查树的平衡情况，必要时进行旋转操作以保持平衡。
2. 删除：删除节点后，同样检查树的平衡情况，并进行旋转操作。
3. 旋转：包括左旋、右旋、左右旋和右左旋四种操作，用于调整树的结构。

AVL树的实现

下面是一个简单的AVL树实现，包括插入和旋转操作的示例代码：

#include <stdio.h>
#include <stdlib.h>// AVL树节点结构
typedef struct Node {int key;int height; // 节点的高度struct Node* left;struct Node* right;
} Node;// 获取节点的高度
int height(Node* N) {if (N == NULL)return 0;return N->height;
}// 获取平衡因子
int getBalance(Node* N) {if (N == NULL)return 0;return height(N->left) - height(N->right);
}// 创建新节点
Node* newNode(int key) {Node* node = (Node*)malloc(sizeof(Node));node->key = key;node->left = NULL;node->right = NULL;node->height = 1; // 新节点的高度为1return node;
}// 右旋转
Node* rightRotate(Node* y) {Node* x = y->left;Node* T2 = x->right;// 进行旋转x->right = y;y->left = T2;// 更新高度y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));return x; // 返回新的根节点
}// 左旋转
Node* leftRotate(Node* x) {Node* y = x->right;Node* T2 = y->left;// 进行旋转y->left = x;x->right = T2;// 更新高度x->height = 1 + (height(x->left) > height(x->right) ? height(x->left) : height(x->right));y->height = 1 + (height(y->left) > height(y->right) ? height(y->left) : height(y->right));return y; // 返回新的根节点
}// 插入节点
Node* insert(Node* node, int key) {// 1. 执行常规的BST插入if (node == NULL)return newNode(key);if (key < node->key)node->left = insert(node->left, key);else if (key > node->key)node->right = insert(node->right, key);else // 不允许重复的键return node;// 2. 更新节点的高度node->height = 1 + (height(node->left) > height(node->right) ? height(node->left) : height(node->right));// 3. 检查平衡性int balance = getBalance(node);// 如果不平衡，有四种情况// 左左情况if (balance > 1 && key < node->left->key)return rightRotate(node);// 右右情况if (balance < -1 && key > node->right->key)return leftRotate(node);// 左右情况if (balance > 1 && key > node->left->key) {node->left = leftRotate(node->left);return rightRotate(node);}// 右左情况if (balance < -1 && key < node->right->key) {node->right = rightRotate(node->right);return leftRotate(node);}// 返回（未改变的）节点指针return node;
}// 中序遍历
void inorder(Node* root) {if (root != NULL) {inorder(root->left);printf("%d ", root->key);inorder(root->right);}
}int main() {Node* 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("中序遍历AVL树：");inorder(root);printf("\n");return 0;
}

代码说明

1. 节点结构：`Node`结构体包含键值、节点高度和左右子节点的指针。
2. 高度和平衡因子的计算：`height`和`getBalance`函数用于计算节点的高度和获取平衡因子。
3. 旋转操作：`rightRotate`和`leftRotate`函数用于进行树的旋转，以保持平衡。
4. 插入操作：`insert`函数用于插入新节点并保持AVL树的平衡。
5. 中序遍历：`inorder`函数用于遍历树并输出节点的键值。