AVL树与红黑树的原理与特性
在计算机科学中，平衡二叉搜索树是一种重要的数据结构，能够有效地存储和检索数据。AVL树和红黑树是两种常见的自平衡二叉搜索树，它们各自有自己的特点和应用场景。本文将深入探讨这两种树的原理、特性以及简单的代码示例。
AVL树
AVL树是一种高度平衡的二叉搜索树，得名于其发明者G.M. Adelson-Velsky和E.M. Landis。AVL树的关键思想是保持树的高度平衡，具体来说，对于树中的任何节点，其左子树和右子树的高度差（平衡因子）不能超过1。
特性：
- 高度平衡：任意节点的左右子树高度差不超过1。
- 二叉搜索树特性：对于每个节点，左子树的值小于节点值，右子树的值大于节点值。
- 旋转操作：当树不再平衡时，通过旋转操作（单旋转或双旋转）来恢复平衡。
代码示例：
以下是实现AVL树的基本结构及插入操作的代码示例：
#include <iostream>
using namespace std;
class AVLNode {
public:
int key;
AVLNode* left;
AVLNode* right;
int height;
AVLNode(int value) : key(value), left(nullptr), right(nullptr), height(1) {}
};
class AVLTree {
public:
AVLNode* root;
AVLTree() : root(nullptr) {}
int height(AVLNode* node) {
return node ? node->height : 0;
}
int getBalance(AVLNode* node) {
return node ? height(node->left) - height(node->right) : 0;
}
AVLNode* rightRotate(AVLNode* y) {
AVLNode* x = y->left;
AVLNode* 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;
}
AVLNode* leftRotate(AVLNode* x) {
AVLNode* y = x->right;
AVLNode* 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;
}
AVLNode* insert(AVLNode* node, int key) {
if (!node) return new AVLNode(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; // 重复节点不插入
node->height = max(height(node->left), height(node->right)) + 1;
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 preOrder(AVLNode* node) {
if (node) {
cout << node->key << " ";
preOrder(node->left);
preOrder(node->right);
}
}
void insert(int key) {
root = insert(root, key);
}
void display() {
preOrder(root);
cout << endl;
}
};
int main() {
AVLTree tree;
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.insert(25);
cout << "AVL树的前序遍历结果是: ";
tree.display();
return 0;
}
红黑树
红黑树是一种平衡的二叉搜索树，每个节点都有一个颜色属性（红色或黑色）。通过对节点颜色的约束，红黑树保证了树的高度大致是对数级别，从而确保了基本操作（插入、删除、查找）的时间复杂度为O(log n)。
特性：
- 每个节点是红色或黑色。
- 根节点是黑色。
- 每个叶子节点（NIL或空节点）是黑色。
- 如果一个节点是红色，则它的两个子节点必须是黑色（即没有两个红色相邻）。
- 从任一节点到其每个叶子节点的路径都包含相同数量的黑色节点（称为黑色高度）。
代码示例：
以下是红黑树的插入操作的简化版代码示例：
#include <iostream>
using namespace std;
enum Color { RED, BLACK };
struct RBNode {
int data;
Color color;
RBNode *left, *right, *parent;
RBNode(int data) {
this->data = data;
left = right = parent = nullptr;
color = RED; // 新节点为红色
}
};
class RBTree {
private:
RBNode *root;
void rotateLeft(RBNode *&node) {
RBNode *node_y = node->right;
node->right = node_y->left;
if (node_y->left != nullptr) {
node_y->left->parent = node;
}
node_y->parent = node->parent;
if (node->parent == nullptr) {
root = node_y;
} else if (node == node->parent->left) {
node->parent->left = node_y;
} else {
node->parent->right = node_y;
}
node_y->left = node;
node->parent = node_y;
}
void rotateRight(RBNode *&node) {
RBNode *node_y = node->left;
node->left = node_y->right;
if (node_y->right != nullptr) {
node_y->right->parent = node;
}
node_y->parent = node->parent;
if (node->parent == nullptr) {
root = node_y;
} else if (node == node->parent->left) {
node->parent->left = node_y;
} else {
node->parent->right = node_y;
}
node_y->right = node;
node->parent = node_y;
}
void fixViolations(RBNode *&node) {
RBNode *parent_node = nullptr;
RBNode *grandparent_node = nullptr;
while ((node != root) && (node->color == RED) && (node->parent->color == RED)) {
parent_node = node->parent;
grandparent_node = parent_node->parent;
if (parent_node == grandparent_node->left) {
RBNode *uncle_node = grandparent_node->right;
if (uncle_node != nullptr && uncle_node->color == RED) {
grandparent_node->color = RED;
parent_node->color = BLACK;
uncle_node->color = BLACK;
node = grandparent_node; // 继续从祖父节点向上检查
} else {
if (node == parent_node->right) {
rotateLeft(parent_node);
node = parent_node;
parent_node = node->parent;
}
rotateRight(grandparent_node);
swap(parent_node->color, grandparent_node->color);
node = parent_node;
}
} else {
RBNode *uncle_node = grandparent_node->left;
if ((uncle_node != nullptr) && (uncle_node->color == RED)) {
grandparent_node->color = RED;
parent_node->color = BLACK;
uncle_node->color = BLACK;
node = grandparent_node; // 继续从祖父节点向上检查
} else {
if (node == parent_node->left) {
rotateRight(parent_node);
node = parent_node;
parent_node = node->parent;
}
rotateLeft(grandparent_node);
swap(parent_node->color, grandparent_node->color);
node = parent_node;
}
}
}
root->color = BLACK; // 根节点始终为黑色
}
public:
RBTree() {
root = nullptr;
}
void insert(const int &data) {
RBNode *node = new RBNode(data);
root = BSTInsert(root, node);
fixViolations(node);
}
RBNode* BSTInsert(RBNode* root, RBNode *node) {
if (root == nullptr) return node;
if (node->data < root->data) {
root->left = BSTInsert(root->left, node);
root->left->parent = root;
} else if (node->data > root->data) {
root->right = BSTInsert(root->right, node);
root->right->parent = root;
}
return root;
}
void InOrder() {
InOrderHelper(root);
}
void InOrderHelper(RBNode* node) {
if (node == nullptr) return;
InOrderHelper(node->left);
cout << node->data << " ";
InOrderHelper(node->right);
}
};
int main() {
RBTree tree;
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(15);
cout << "红黑树的中序遍历结果是: ";
tree.InOrder();
cout << endl;
return 0;
}
总结
AVL树和红黑树都是优秀的自平衡二叉搜索树，适用于不同的场景。AVL树具有更严格的平衡条件，适合查询频繁的应用；而红黑树则具有更好的插入和删除性能，适合修改频繁的情况。理解它们的原理和特性，不仅有助于深入掌握数据结构的基础，也为实际开发中的问题提供了有效的解决方案。
