红黑树与AVL树的区别

1. 红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。     红黑树能够以O(log2 n) 的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构，能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高。     当然，红黑树并不适应所有应用树的领域。如果数据基本上是静态的，那么让他们待在他们能够插入，并且不影响平衡的地方会具有更好的性能。如果数据完全是静态的，做一个哈希表，性能可能会更好一些。  2 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。  引入二叉树的目的是为了提高二叉树的搜索的效率,减少树的平均搜索长度.为此,就必须每向二叉树插入一个结点时调整树的结构,使得二叉树搜索保持平衡,从而可能降低树的高度,减少的平均树的搜索长度.     2.AVL树的定义:  一棵AVL树满足以下的条件:  1>它的左子树和右子树都是AVL树  2>左子树和右子树的高度差不能超过1  性质:  1>一棵n个结点的AVL树的其高度保持在0(log2(n)),不会超过3/2log2(n+1)  2>一棵n个结点的AVL树的平均搜索长度保持在0(log2(n)).  3>一棵n个结点的AVL树删除一个结点做平衡化旋转所需要的时间为0(log2(n)). 

3.这点来看红黑树是牺牲了严格的高度平衡的优越条件为代价红黑树能够以O(log2 n)的时间复杂度进行搜索、插入、删除操作。此外，由于它的设计，任何不平衡都会在三次旋转之内解决。当然，还有一些更好的，但实现起来更复杂的数据结构能够做到一步旋转之内达到平衡，但红黑树能够给我们一个比较“便宜”的解决方案。红黑树的算法时间复杂度和AVL相同，但统计性能比AVL树更高.

AVL树的插入实现 ：AVLTree.h

#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 // 定义平衡二叉树的结点结构 typedef struct BiTNode { int data; int bf; // 平衡因子 BiTNode *lchild, *rchild; }BiTNode, *BiTree; typedef int Status; // 右旋处理，即LL调整 void R_Rotate( BiTree *p ) { BiTree L; L = (*p)->lchild; (*p)->lchild = L->rchild; L->rchild = *p; *p = L; } // 左旋处理，即RR调整 void L_Rotate( BiTree *p ) { BiTree R; R = (*p)->rchild; (*p)->rchild = R->lchild; R->lchild = *p; *p = R; } // 左平衡旋转处理，包括 LL 和 LR 调整 void LeftBalance( BiTree *T ) { BiTree L, Lr; L = (*T)->lchild; switch( L->bf ) { case 1: // 新结点插入在T的左孩子的左子树上，为LL型，作右旋处理即LL调整 (*T)->bf = L->bf = 0; R_Rotate( T ); break; case -1: // 新结点插入在T的左孩子的右子树上，为LR型，作双旋处理 Lr = L->rchild; switch( Lr->bf ) { case 1: (*T)->bf = -1; L->bf = 0; break; case 0: (*T)->bf = L->bf = 0; break; case -1: (*T)->bf = 0; L->bf = 1; break; } Lr->bf = 0; L_Rotate( &(*T)->lchild ); // 先对T的左子树进行左旋处理即RR调整 R_Rotate( T ); // 再对T进行右旋处理即LL调整 } } // 右平衡旋转处理，包括 RR 和 RL 调整 void RightBalance( BiTree *T ) { BiTree R, Rl; R = (*T)->rchild; switch( R->bf ) { case -1: // 新结点插入在T的右孩子的右子树上，为RR型，作左旋处理即RR调整 (*T)->bf = R->bf = 0; L_Rotate( T ); break; case 1: // 新结点插入在T的右孩子的左子树上，为RL型，作双旋处理 Rl = R->lchild; switch( Rl->bf ) { case 1: (*T)->bf = 0; R->bf = -1; break; case 0: (*T)->bf = R->bf = 0; break; case -1: (*T)->bf = 1; R->bf = 0; break; } Rl->bf = 0; R_Rotate( &(*T)->rchild ); // 先对T的左子树进行左旋即RR调整 L_Rotate( T ); // 再对T进行右旋即LL调整 } } // 若在平衡二叉树T中不存在和 e 具有相同数据的结点，则插入数据元素为 e 的新结点， // 若因插入使二叉排序树失去平衡，则要作平衡调整， // 布尔变量taller表示 T 的深度是否增加，TRUE表示增加，FALSE表示没有增加 Status InsertAVL( BiTree *T, int e, Status *taller ) { if( !*T ) { *T = (BiTree)malloc(sizeof(BiTNode)); (*T)->data = e; (*T)->lchild = (*T)->rchild = NULL; (*T)->bf = 0; *taller = TRUE; } else { // 树中已有和e具有相同数据的结点，则不再插入 if( e == (*T)->data ) { *taller = FALSE; return FALSE; } if( e < (*T)->data ) // 继续在T的左子树进行搜索 { if( !InsertAVL( &(*T)->lchild, e, taller ) ) // InsertAVL( &(*T)->lchild, e, taller )得到的是T的左孩子结点(*T)->lchild的 data,bf 等相关信息 { return FALSE; } // 如果e已插入到T的左子树中，且左子树深度增加 if( *taller ) { switch( (*T)->bf ) // 检查T的平衡因子 { case 1: // 原本左子树比右子树高，再加上此结点，导致不平衡，需要作LL或LR调整 LeftBalance( T ); *taller = FALSE; break; case 0: // 原本左右子树等高，再加上此结点，左子树增高 (*T)->bf = 1; *taller = TRUE; break; case -1: // 原本右子树比左子树高，再加上此结点，左右子树变为等高 (*T)->bf = 0; *taller = FALSE; break; } } } else // 在T的右子树进行搜索 { if( !InsertAVL( &(*T)->rchild, e, taller ) ) { return FALSE; } if( *taller ) { switch( (*T)->bf ) { case 1: // 原先左子树比右子树高，现在左右子树等高 (*T)->bf = 0; *taller = FALSE; break; case 0: // 原先左右子树等高，现在右子树增高 (*T)->bf = -1; *taller = TRUE; break; case -1: // 原先右子树比左子树高，现在再加上此结点，导致不平衡，需要作 RR 或 RL 调整 RightBalance( T ); *taller = FALSE; break; } } } } return TRUE; }

测试代码

#include<iostream> #include "AVLTree.h" using namespace std; int main() { int i;       int a[10] = {2,1,0,3,4,5,6,9,8,7};       BiTree T = NULL;       Status taller;          for( i=0; i<10; i++ )       {           InsertAVL( &T, a[i], &taller );       }   }

红黑树的插入实现：

#include<iostream> #include<malloc.h> #include<string.h> #include<stdlib.h> using namespace std; template<class _Ty> class R_BTree { protected: enum _Redbl{_Red=0,_Black=1}; struct _Node; typedef struct _Node * _Nodeptr; struct _Node { _Nodeptr _Left,_Parent,_Right; _Ty _Value; _Redbl _Color; }; typedef struct _Node *& _Nodepref; typedef _Redbl & _Rbref; typedef _Ty & _Vref; static _Rbref _Color(_Nodeptr _P) { return _P->_Color; } static _Vref _Value(_Nodeptr _P) { return _P->_Value; } static _Nodepref _Left(_Nodeptr _P) { return _P->_Left; } static _Nodepref _Right(_Nodeptr _P) { return _P->_Right; } static _Nodepref _Parent(_Nodeptr _P) { return _P->_Parent; } public: R_BTree():_Head(NULL),_Nil(NULL) { _Init(); } void insert(const _Ty &_V) { _Nodeptr _X = _Root(); _Nodeptr _Y = _Head; while(_X != _Nil && _Value(_X) != _V) { _Y = _X; _X = _V < _Value(_X) ? _Left(_X):_Right(_X); } if(_X != _Nil) return ; insert(_X,_Y,_V); } private: void insert(_Nodeptr _X,_Nodeptr _Y,const _Ty &_V) { _Nodeptr _Z = _Buynode(_Y,_Red); if(_Y == _Head) { _Parent(_Head) = _Z; }else { if(_V < _Value(_Y)) _Left(_Y) = _Z; else _Right(_Y) = _Z; } _Left(_Z) = _Right(_Z) = _Nil; new(&_Value(_Z)) _Ty(_V); // _X = _Z; for(;_X != _Root() && _Color(_Parent(_X)) == _Red;) { if(_Parent(_X) == _Left(_Parent(_Parent(_X)))) // left { _Y = _Right(_Parent(_Parent(_X))); if(_Color(_Y) == _Red) { _Color(_Parent(_X)) = _Black; _Color(_Y) = _Black; _Color(_Parent(_Parent(_X))) = _Red; _X = _Parent(_Parent(_X)); }else { if(_X == _Right(_Parent(_X))) { _Y = _Parent(_X); _Lrotate(_Y); } _Color(_Parent(_X)) = _Black; _Color(_Parent(_Parent(_X))) = _Red; _Rrotate(_Parent(_Parent(_X))); } } else // right { _Y = _Left(_Parent(_Parent(_X))); if(_Color(_Y) == _Red) { _Color(_Parent(_X)) = _Black; _Color(_Y) = _Black; _Color(_Parent(_Parent(_X))) = _Red; _X = _Parent(_Parent(_X)); }else { if(_X == _Left(_Parent(_X))) { _Y = _Parent(_X); _Rrotate(_Y); } _Color(_Parent(_X)) = _Black; _Color(_Parent(_Parent(_X))) = _Red; _Lrotate(_Parent(_Parent(_X))); } } } _Color(_Root()) = _Black; } void _Rrotate(_Nodeptr _X) { _Nodeptr _Y = _Left(_X); _Left(_X) = _Right(_Y); if(_Right(_Y) != _Nil) { _Parent(_Right(_Y)) = _X; } _Parent(_Y) = _Parent(_X); if(_X == _Root()) { _Root() = _Y; }else if(_X == _Right(_Parent(_X))) { _Right(_Parent(_X)) = _Y; }else { _Left(_Parent(_X)) = _Y; } _Right(_Y) = _X; _Parent(_X) = _Y; } void _Lrotate(_Nodeptr _X) { _Nodeptr _Y = _Right(_X); _Right(_X) = _Left(_Y); if(_Left(_Y) != _Nil) { _Parent(_Left(_Y)) = _X; } _Parent(_Y) = _Parent(_X); if(_X == _Root()) { _Root() = _Y; }else if(_X == _Left(_Parent(_X))) { _Left(_Parent(_X)) = _Y; }else { _Right(_Parent(_X)) = _Y; } _Left(_Y) = _X; _Parent(_X) = _Y; } _Nodeptr _Root() const { return _Parent(_Head);} _Nodepref _Root() { return _Parent(_Head);} void _Init() { _Nil = _Buynode(NULL,_Black); _Head = _Buynode(_Nil,_Red); } static _Nodeptr _Buynode(_Nodeptr _Parg,_Redbl _Carg) { _Nodeptr _S = (_Nodeptr)malloc(sizeof(_Node)); if(NULL == _S) exit(1); memset(_S,0,sizeof(_Node)); _Parent(_S) = _Parg; _Color(_S) = _Carg; return _S; } _Nodeptr _Head; _Nodeptr _Nil; }; int main() { int ar[]={12,23,34,45,56,67,78,89,90,100,110,120}; int n = sizeof(ar)/sizeof(ar[0]); R_BTree<int> mytree; int x; while(cin>>x, x!= -1) { mytree.insert(x); } return 0; }