一、AVL 树
AVL 树是一种平衡二叉树，得名于其发明者的名字（Adelson-Velskii 和 Landis）。
特点：
- 平衡二叉搜索树
- 每个结点存 balance factor = {-1, 0, 1}，即左右子树的高度差
- 四种旋转操作
缺点：
- 结点需要存储额外的信息，而且调整的次数频繁（因为左右子树高度差不能超过1）。
二、红黑树
红黑树（Red-Black Tree）是一种 近似平衡 的二叉搜索树，它能确保任何一个结点的左右子树的 高度差小于两倍。
特点：
- 每个节点要么是红色，要么是黑色；
- 根节点是黑色；
- 每个叶子节点（ NULL 结点，空节点）是黑色；
- 不能有相邻的两个红色节点；
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色节点。
红黑树的对子树高度差的要求比 AVL 树低，但是依然维持了不错平衡，所以红黑树的维护频率比 AVL 树低，但是效率差不多的高。
三、AVL 树 C++ 实现
C++ 实现
#pragma once
template <typename T>
struct TreeNode {
T *left_ = nullptr, *right_ = nullptr;
/* left left case: left rotate
* A (B)
* / \ / \
* (B) C D A
* / \ => / \
* D E E C
**/
static T* r_rotate(T* node)
{
T* root = node->left_;
node->left_ = root->right_;
root->right_ = node;
return root;
}
/* right right case: left rotate
* A (C)
* / \ / \
* B (C) A E
* / \ => / \
* D E B D
**/
static T* l_rotate(T* node)
{
T* root = node->right_;
node->right_ = root->left_;
root->left_ = node;
return root;
}
/* left right case: left rotate, right rotate
* A A
* / \ / \ (E)
* B C (E) C / \
* / \ => / \ => B A
* D (E) B G / \ / \
* / \ / \ D F G C
* F G D F
**/
static T* lr_rotate(T* node)
{
node->left_ = l_rotate(node->left_);
return r_rotate(node);
}
/* right left case: right rotate, left rotate
* A A
* / \ / \ (D)
* B C B (D) / \
* / \ => / \ => A C
* (D) E F C / \ / \
* / \ / \ B F G E
* F G G E
**/
static T* rl_rotate(T* node)
{
node->right_ = r_rotate(node->right_);
return l_rotate(node);
}
};
template <typename T>
struct HeightNode : TreeNode<T> {
int height_ = 0;
static int height(T* node) { return node ? node->height_ : 0; }
static void update_height(T* node)
{
const auto left = height(node->left_), right = height(node->right_);
node->height_ = 1 + (left > right ? left : right);
}
static T* r_rotate(T* node)
{
node = TreeNode<T>::r_rotate(node);
update_height(node->right_);
update_height(node);
return node;
}
static T* l_rotate(T* node)
{
node = TreeNode<T>::l_rotate(node);
update_height(node->left_);
update_height(node);
return node;
}
static T* lr_rotate(T* node)
{
node->left_ = l_rotate(node->left_);
return r_rotate(node);
}
static T* rl_rotate(T* node)
{
node->right_ = r_rotate(node->right_);
return l_rotate(node);
}
};
template <typename T>
class AVLTree {
public:
struct Node : HeightNode<Node> {
T data_;
Node(T data) : data_(data) {}
};
public:
template <typename V>
void accept(V& visitor)
{
visitor.begin();
visitor.visit(root_);
visitor.end();
}
void insert(T data) { if (!exist(data)) { root_ = insert_(root_, data); } }
void remove(T data) { root_ = remove_(root_, data); }
bool exist(T data) const { return find_(root_, data); }
private:
Node* balance_(Node* node)
{
const int left = Node::height(node->left_), right = Node::height(node->right_);
if (left == right + 2) {
if (Node::height(node->left_->left_) < Node::height(node->left_->right_)) {
node = Node::lr_rotate(node); // left right case
} else {
node = Node::r_rotate(node); // left left case
}
} else if (right == left + 2) {
if (Node::height(node->right_->left_) < Node::height(node->right_->right_)) {
node = Node::l_rotate(node); // right left case
} else {
node = Node::rl_rotate(node); // right left case
}
}
return node;
}
Node* insert_(Node* node, T data)
{
if (!node) {
return new Node(data);
} else if (data < node->data_) {
node->left_ = insert_(node->left_, data);
} else {
node->right_ = insert_(node->right_, data);
}
node = balance_(node);
Node::update_height(node);
return node;
}
Node* remove_(Node* node, T data)
{
if (!node) {
return node;
}
if (data == node->data_) {
if (node->left_ && node->right_) {
if (Node::height(node->left_) < Node::height(node->right_)) {
Node* minimum = node->right_;
while (minimum->left_) {
minimum = minimum->left_;
}
node->data_ = minimum->data_;
node->right_ = remove_(node->right_, minimum->data_);
} else {
Node* maximum = node->left_;
while (maximum->right_) {
maximum = maximum->right_;
}
node->data_ = maximum->data_;
node->left_ = remove_(node->left_, maximum->data_);
}
} else {
Node* tmp = node;
node = node->left_ ? node->left_ : node->right_;
delete tmp;
}
} else if (data < node->data_) {
node->left_ = remove_(node->left_, data);
node = balance_(node);
} else {
node->right_ = remove_(node->right_, data);
node = balance_(node);
}
return node;
}
Node* find_(Node* node, T data) const
{
while (node && data != node->data_) {
node = data < node->data_ ? node->left_ : node->right_;
}
return node;
}
private:
Node* root_ = nullptr;
};测试代码
#include "avl.h"
#include <iostream>
using namespace std;
template <typename T>
struct InOrderVisitor {
void begin() { cout << "in-order: "; }
void end() { cout << endl; }
void visit(int data) { cout << data << " "; }
void visit(typename T::Node* node)
{
if (node) {
visit(node->left_);
visit(node->data_);
visit(node->right_);
}
}
};
template <typename T>
void test_tree()
{
T tree;
InOrderVisitor<T> visitor;
constexpr int arr[] = { 3, 1, 4, 6, 2, 5, 9, 8, 7, 0 };
for (auto v : arr) {
tree.insert(v);
cout << v << ": " << tree.exist(v) << endl;
tree.accept(visitor);
}
for (auto v : arr) {
tree.remove(v);
cout << v << ": " << tree.exist(v) << endl;
tree.accept(visitor);
}
}
int main()
{
test_tree<AVLTree<int>>();
return 0;
}
