左子节点与右子节点对称的树就是平衡树，否则就是非平衡树。非平衡树会影响树中数据的查询，插入和删除的效率。比如当一个二叉树极不平衡时，即所有的节点都在根的同一侧，此时树没有分支，就变成了一个链表。数据的排列是一维的，而不是二维的。在这种情况下，查找的速度下降到O(N)，而不是平衡二叉树的O(logN)。为了能以较快的时间O(logN)来搜索一棵树，需要保证树总是平衡的（或者至少大部分是平衡的）。这就是说对树中的每个节点在它左边的后代数目和在它右边的后代数目应该大致相等。几种主要的二叉平衡树：红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项，插入程序要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。红黑树有两个特征：(1) 节点都有颜色(2) 在插入和删除过程中，要遵循保持这些颜色的不同排列的规则。红黑规则：1. 每一个节点不是红色的就是黑色的2. 根总是黑色的3. 如果节点是红色的，则它的子节点必须是黑色的（反之不一定成立）4. 从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。（空子节点是指非叶节点可以接子节点的位置。换句话说，就是一个有右子节点的节点可能接左子节点的位置，或是有左子节点的节点可能接右子节点的位置）AVL树，它或者是一颗空二叉树，或者是具有下列性质的二叉树：(1) 其根的左右子树高度之差的绝对值不能超过1；(2) 其根的左右子树都是二叉平衡树。AVL树查找的时间复杂度为O(logN)，因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树，依次向下查找插入点，依次向上平衡树，AVL树不如红黑树效率高，也不如红黑树常用。AVL树插入的C++代码： template <class T>ResultCode AVLTree<T>::Insert(AVLNode<T> * &p,T &x,bool &unBalanced)...{           ResultCode result=Success;           if(p==null)...{//插入新节点                        p=new AVLNode<T>(x);                       unBalanced=true;                       }else if(x<p->element)...{//新节点插入左子树                              result=Insert(p->lChild,x,unBalanced);                             if(unBanlanced)...{                                             switch(p->bF)...{                                                           case -1:                                                                p->bF=0;                                                                unBalanced=false;                                                                break;                                                           case 0:                                                                p->bF=1;                                                                break;                                                           case 1:                                                                LRotation(p,unBalanced);                                                                                                                                }                                             }                             }else if(x==p->element)...{//有重复元素，插入失败                                    unBalanced=false;                                   x=p->element;                                   result=Duplicate;                                   }else...{//新节点插入右子树                                          result=Insert(p->rChild,x,unBalanced);                                         if(unBalanced)...{                                                        switch(p->bF)...{                                                          case 1:                                                                p->bF=0;                                                                unBalanced=false;                                                                break;                                                           case 0:                                                                p->bF=-1;                                                                break;                                                           case -1:                                                                RRotation(p,unBalanced);                                                                                                                                            }                                                        }                                         }                                         return result;           }template <class T> void AVLTree<T>::LRotation(AVLNode<T> * &s,bool &unBalanced)...{     AVLNode<T> *u,*r=s->lChild;     if(r->bF==1)...{//LL旋转                   s->lChild=r->rChild;                  r->rChild=s;                  s->bF=0;                  s=r; //s指示新子树的根                   }else...{ //LR旋转                         u=r->rChild;                        r->rChild=u->lChild;                        u->lChild=r;                        s->lChild=u->rChild;                        u->rChild=s;                        switch(u->bF)...{                                      case 1:                                           s->bF=-1;                                           r->bF=0;                                           break;                                      case 0:                                           s->bF=r->bF=0;                                           break;                                      case -1:                                           s->bF=0;                                           r->bF=1;                                      }                                      s=u; //s指示新子树的根                        }                        s->bF=0;  //s的平衡因子为0                         unBalanced=false;  //结束重新平衡操作  }

评论