二叉树，红黑树初学-开发者社区

二叉树、AVL 树和红黑树都是基于二叉搜索树（BST）的数据结构，但在平衡性、实现复杂度和操作性能上有显著区别。以下是它们的核心差异与时间复杂度对比：

一、基本定义

类型	定义	是否自平衡
普通二叉搜索树（BST）	满足左子 < 根 < 右子的二叉树	❌ 否
AVL 树	自平衡 BST，任意节点左右子树高度差 ≤ 1	✅ 是
红黑树（Red-Black Tree）	自平衡 BST，通过颜色标记和5条性质维持近似平衡	✅ 是

二、核心区别

特性	普通 BST	AVL 树	红黑树
平衡机制	无，可能退化为链表	严格平衡（高度差 ≤ 1）	宽松平衡（黑高一致，最长路径 ≤ 2×最短）
查找效率	平均 O(log n)，最坏 O(n)	最优：始终 O(log n)，树更矮	稍逊于 AVL：O(log n)，但常数因子略大
插入/删除开销	O(1) 调整（无平衡）	高：可能需多次旋转（最多 O(log n) 次）	较低：最多 2 次旋转 + 重染色
空间开销	仅存储值和指针	额外存储高度或平衡因子	额外 1 bit 存储颜色
实现复杂度	简单	中等（需维护平衡因子和4种旋转）	较复杂（颜色规则 + 旋转）
适用场景	小规模、随机数据	查找密集型（如数据库索引）	频繁插入/删除（如 STL map/set、Java TreeMap）

三、时间复杂度汇总

操作	普通 BST	AVL 树	红黑树
查找	平均 O(log n)，最坏 O(n)	O(log n)	O(log n)
插入	平均 O(log n)，最坏 O(n)	O(log n)（含旋转）	O(log n)（含旋转+染色）
删除	平均 O(log n)，最坏 O(n)	O(log n)	O(log n)

✅ 所有操作在 AVL 和红黑树中最坏情况均为 O(log n)，而普通 BST 在有序输入下会退化为 O(n)。

四、为什么红黑树“最长路径 ≤ 2×最短路径”？

最短路径：全为黑色节点，长度 = 黑高（bh）
最长路径：黑红交替（因不能连续红），长度 ≤ 2 × bh
⇒ 树高h ≤ 2 log₂(n+1)，保证 O(log n) 性能

五、实际应用举例

AVL 树：适用于读多写少场景，如数据库索引、静态字典。
红黑树：广泛用于标准库：
- C++ STL：std::map,std::set
- Java：TreeMap,TreeSet
- Linux 内核：进程调度、虚拟内存管理

总结

若查找为主→ 选AVL 树
若插入/删除频繁→ 选红黑树
若数据量小或随机性强 →普通 BST足够且简单

两者都是 O(log n) 的高效结构，红黑树牺牲少量平衡性换取更低的维护成本，因此在工程实践中更常用。

我来为你实现一个完整的红黑树，包括插入、删除、查询等功能。这是C++中比较经典且复杂的算法之一。

#include<iostream>#include<queue>#include<iomanip>usingnamespacestd;enumColor{RED,BLACK};template<typenameT>structNode{T data;Color color;Node<T>*left;Node<T>*right;Node<T>*parent;Node(T val):data(val),color(RED),left(nullptr),right(nullptr),parent(nullptr){}};template<typenameT>classRedBlackTree{private:Node<T>*root;Node<T>*nil;// 哨兵节点，表示空节点// 初始化哨兵节点voidinitializeNil(){nil=newNode<T>(T());nil->color=BLACK;nil->left=nil->right=nil->parent=nil;}// 左旋voidleftRotate(Node<T>*x){Node<T>*y=x->right;x->right=y->left;if(y->left!=nil){y->left->parent=x;}y->parent=x->parent;if(x->parent==nil){root=y;}elseif(x==x->parent->left){x->parent->left=y;}else{x->parent->right=y;}y->left=x;x->parent=y;}// 右旋voidrightRotate(Node<T>*y){Node<T>*x=y->left;y->left=x->right;if(x->right!=nil){x->right->parent=y;}x->parent=y->parent;if(y->parent==nil){root=x;}elseif(y==y->parent->left){y->parent->left=x;}else{y->parent->right=x;}x->right=y;y->parent=x;}// 插入后修复红黑树性质voidinsertFixup(Node<T>*z){while(z->parent->color==RED){if(z->parent==z->parent->parent->left){Node<T>*y=z->parent->parent->right;if(y->color==RED){// 情况1：叔叔节点是红色z->parent->color=BLACK;y->color=BLACK;z->parent->parent->color=RED;z=z->parent->parent;}else{if(z==z->parent->right){// 情况2：z是右孩子z=z->parent;leftRotate(z);}// 情况3：z是左孩子z->parent->color=BLACK;z->parent->parent->color=RED;rightRotate(z->parent->parent);}}else{// 对称的情况Node<T>*y=z->parent->parent->left;if(y->color==RED){// 情况1：叔叔节点是红色z->parent->color=BLACK;y->color=BLACK;z->parent->parent->color=RED;z=z->parent->parent;}else{if(z==z->parent->left){// 情况2：z是左孩子z=z->parent;rightRotate(z);}// 情况3：z是右孩子z->parent->color=BLACK;z->parent->parent->color=RED;leftRotate(z->parent->parent);}}}root->color=BLACK;}// 查找最小节点Node<T>*minimum(Node<T>*node)const{while(node->left!=nil){node=node->left;}returnnode;}// 查找最大节点Node<T>*maximum(Node<T>*node)const{while(node->right!=nil){node=node->right;}returnnode;}// 替换节点voidtransplant(Node<T>*u,Node<T>*v){if(u->parent==nil){root=v;}elseif(u==u->parent->left){u->parent->left=v;}else{u->parent->right=v;}v->parent=u->parent;}// 删除后修复红黑树性质voiddeleteFixup(Node<T>*x){while(x!=root&&x->color==BLACK){if(x==x->parent->left){Node<T>*w=x->parent->right;if(w->color==RED){// 情况1：兄弟节点是红色w->color=BLACK;x->parent->color=RED;leftRotate(x->parent);w=x->parent->right;}if(w->left->color==BLACK&&w->right->color==BLACK){// 情况2：兄弟节点的两个子节点都是黑色w->color=RED;x=x->parent;}else{if(w->right->color==BLACK){// 情况3：兄弟节点的右子节点是黑色w->left->color=BLACK;w->color=RED;rightRotate(w);w=x->parent->right;}// 情况4：兄弟节点的右子节点是红色w->color=x->parent->color;x->parent->color=BLACK;w->right->color=BLACK;leftRotate(x->parent);x=root;}}else{// 对称的情况Node<T>*w=x->parent->left;if(w->color==RED){w->color=BLACK;x->parent->color=RED;rightRotate(x->parent);w=x->parent->left;}if(w->right->color==BLACK&&w->left->color==BLACK){w->color=RED;x=x->parent;}else{if(w->left->color==BLACK){w->right->color=BLACK;w->color=RED;leftRotate(w);w=x->parent->left;}w->color=x->parent->color;x->parent->color=BLACK;w->left->color=BLACK;rightRotate(x->parent);x=root;}}}x->color=BLACK;}// 删除节点voiddeleteNode(Node<T>*z){Node<T>*y=z;Node<T>*x;Color y_original_color=y->color;if(z->left==nil){x=z->right;transplant(z,z->right);}elseif(z->right==nil){x=z->left;transplant(z,z->left);}else{y=minimum(z->right);y_original_color=y->color;x=y->right;if(y->parent==z){x->parent=y;}else{transplant(y,y->right);y->right=z->right;y->right->parent=y;}transplant(z,y);y->left=z->left;y->left->parent=y;y->color=z->color;}if(y_original_color==BLACK){deleteFixup(x);}deletez;}// 递归删除所有节点voidclear(Node<T>*node){if(node!=nil){clear(node->left);clear(node->right);deletenode;}}// 中序遍历voidinorderHelper(Node<T>*node,vector<T>&result)const{if(node!=nil){inorderHelper(node->left,result);result.push_back(node->data);inorderHelper(node->right,result);}}// 获取节点高度intgetHeight(Node<T>*node)const{if(node==nil)return0;returnmax(getHeight(node->left),getHeight(node->right))+1;}public:RedBlackTree(){initializeNil();root=nil;}~RedBlackTree(){clear(root);deletenil;}// 插入元素voidinsert(T value){Node<T>*z=newNode<T>(value);Node<T>*y=nil;Node<T>*x=root;while(x!=nil){y=x;if(z->data<x->data){x=x->left;}else{x=x->right;}}z->parent=y;if(y==nil){root=z;}elseif(z->data<y->data){y->left=z;}else{y->right=z;}z->left=nil;z->right=nil;z->color=RED;insertFixup(z);}// 删除元素boolremove(T value){Node<T>*z=searchNode(value);if(z==nil){returnfalse;}deleteNode(z);returntrue;}// 查找节点Node<T>*searchNode(T value)const{Node<T>*current=root;while(current!=nil){if(value==current->data){returncurrent;}elseif(value<current->data){current=current->left;}else{current=current->right;}}returnnil;}// 查询元素是否存在boolcontains(T value)const{returnsearchNode(value)!=nil;}// 获取最小值Tminimum()const{if(root==nil)throwruntime_error("Tree is empty");returnminimum(root)->data;}// 获取最大值Tmaximum()const{if(root==nil)throwruntime_error("Tree is empty");returnmaximum(root)->data;}// 获取中序遍历结果vector<T>inorder()const{vector<T>result;inorderHelper(root,result);returnresult;}// 获取树的高度intheight()const{returngetHeight(root);}// 判断树是否为空boolempty()const{returnroot==nil;}// 层次遍历打印树结构（调试用）voidprintTree()const{if(root==nil){cout<<"Tree is empty"<<endl;return;}queue<Node<T>*>q;q.push(root);intlevel=0;while(!q.empty()){intlevelSize=q.size();cout<<"Level "<<level<<": ";for(inti=0;i<levelSize;i++){Node<T>*node=q.front();q.pop();if(node!=nil){cout<<node->data<<(node->color==RED?"(R)":"(B)");if(node->left!=nil)q.push(node->left);if(node->right!=nil)q.push(node->right);cout<<" ";}}cout<<endl;level++;}}// 图形化打印树结构（旋转90度）voidprintTreeGraphical()const{cout<<"\n红黑树结构（旋转90度）:\n";printTreeHelper(root,0);}private:voidprintTreeHelper(Node<T>*node,intspace)const{if(node==nil)return;constintSPACING=5;space+=SPACING;printTreeHelper(node->right,space);cout<<endl;for(inti=SPACING;i<space;i++){cout<<" ";}if(node->color==RED){cout<<"\033[31m"<<node->data<<"\033[0m";// 红色}else{cout<<"\033[34m"<<node->data<<"\033[0m";// 蓝色（代表黑色）}cout<<endl;printTreeHelper(node->left,space);}};// 测试函数intmain(){RedBlackTree<int>rbt;cout<<"========== 红黑树测试 ==========\n";// 测试插入vector<int>values={10,20,30,15,25,5,35,40,50,55,60};cout<<"插入元素: ";for(intval:values){cout<<val<<" ";rbt.insert(val);}cout<<endl;// 打印树结构rbt.printTree();rbt.printTreeGraphical();// 测试中序遍历vector<int>inorder=rbt.inorder();cout<<"\n中序遍历结果: ";for(intval:inorder){cout<<val<<" ";}cout<<endl;// 测试查询cout<<"\n查询测试:\n";cout<<"树是否包含15? "<<(rbt.contains(15)?"是":"否")<<endl;cout<<"树是否包含100? "<<(rbt.contains(100)?"是":"否")<<endl;cout<<"最小值: "<<rbt.minimum()<<endl;cout<<"最大值: "<<rbt.maximum()<<endl;cout<<"树高度: "<<rbt.height()<<endl;// 测试删除cout<<"\n删除测试:\n";cout<<"删除20: "<<(rbt.remove(20)?"成功":"失败")<<endl;cout<<"删除100: "<<(rbt.remove(100)?"成功":"失败")<<endl;cout<<"删除5: "<<(rbt.remove(5)?"成功":"失败")<<endl;// 删除后再次打印cout<<"\n删除后的树结构:\n";rbt.printTree();inorder=rbt.inorder();cout<<"删除后的中序遍历: ";for(intval:inorder){cout<<val<<" ";}cout<<endl;// 测试空树RedBlackTree<int>emptyTree;cout<<"\n空树测试:\n";cout<<"树是否为空? "<<(emptyTree.empty()?"是":"否")<<endl;return0;}

红黑树核心性质：

红黑树的5条性质：

每个节点是红色或黑色
根节点是黑色
每个叶子节点（NIL节点）是黑色
如果一个节点是红色，则它的两个子节点都是黑色
从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点

主要操作复杂度：

· 插入：O(log n)
· 删除：O(log n)
· 查询：O(log n)
· 最大值/最小值：O(log n)

关键操作说明：

左旋和右旋

// 左旋：以x为支点左旋voidleftRotate(Node<T>*x)// 右旋：以y为支点右旋voidrightRotate(Node<T>*y)

插入修复的三种情况
情况1：叔叔节点是红色
· 将父节点和叔叔节点变黑
· 祖父节点变红
· 将祖父节点设为当前节点
情况2：叔叔节点是黑色，当前节点是右孩子
· 以父节点为支点左旋
· 转为情况3
情况3：叔叔节点是黑色，当前节点是左孩子
· 父节点变黑，祖父节点变红
· 以祖父节点为支点右旋
删除修复的四种情况

更复杂，涉及兄弟节点的各种情况组合

使用示例：

// 创建红黑树RedBlackTree<int>rbt;// 插入元素rbt.insert(10);rbt.insert(20);rbt.insert(30);// 查询if(rbt.contains(20)){cout<<"找到20"<<endl;}// 获取最小值cout<<"最小值: "<<rbt.minimum()<<endl;// 删除rbt.remove(20);// 中序遍历vector<int>inorder=rbt.inorder();// 打印树结构rbt.printTree();