99久久精品免费看国产,久久综合九色综合欧美就去吻,亚洲精品无码久久久久sm

AVL樹的簡(jiǎn)單實(shí)現(xiàn)

#include <math.h>
#include <vector>
using namespace std;
#define max(a,b) ((a)>(b)?(a):(b))
template<typename E>
class AVL_TMP
{
template <typename E>
class AVL_NODE
{
public:
  AVL_NODE():ln(0),rn(0),depth(0){}
  AVL_NODE( const E& e):data(e),ln(0),rn(0),depth(0){}
  ~AVL_NODE(){ if (ln) delete ln; if (rn) delete rn; }

  bool operator < (E& e){  return data < e; }
  bool operator > (E& e){  return data > e; }
  bool operator == (E& e){ return data == e; }
  bool operator != (E& e){ return data != e; }

  E getdata(){return data;}

  E data;
  int depth;
  AVL_NODE<E> *ln,*rn;
};

public:
typedef E dataType;
typedef AVL_TMP<E> Myt;
typedef AVL_NODE<E> n;
typedef n* npos;
typedef npos iterator;
enum unbalanceType {LL,RR,LR,RL};
AVL_TMP():root(0),size(0),depth(-1){}
~AVL_TMP(){ if(root) delete root; }

iterator begin(){return root;}
bool insert(const E& e);
npos find(const E& e);
npos findpre(const E& e);
bool del(dataType);
bool balance(AVL_TMP<E>::iterator pos){
  if(pos == NULL) throw 0;
  int lh,rh;
  if(pos->ln == NULL ) lh = -1;
  else lh = pos->ln->depth;
  if(pos->rn == NULL ) rh = -1;
  else rh = pos->rn->depth;
  return abs( lh - rh ) < 2 ;
}
virtual void frontOrder(){};
virtual void midOrder(){ };

protected:
void LLr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos);
void LRr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos);
void RRr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos);
void RLr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos);
void updateDepth(AVL_TMP<E>::iterator pos);
bool delAux(E const& e,AVL_TMP<E>::iterator pos = NULL);
iterator findMax(iterator );
iterator findMin(iterator );
bool upTree(int iDepth,iterator itRoot,unsigned long iSize){depth = iDepth;root = itRoot;size = iSize; return true;}
bool upRoutineDepth(vector<iterator>&);
bool adjust(iterator a,iterator b,iterator c,iterator prePos = NULL);
npos root;
int depth;
unsigned long size;
};
template<typename E>
bool AVL_TMP<E>::adjust(iterator a,iterator b,iterator c,iterator prePos){
bool b1,b2;
b1 = b == a->ln;
b2 = c == b->ln;
unbalanceType ub;
if(b1&&!b2)   ub = LR;
if(!b1&&b2)   ub = RL;
if(b1&&b2)    ub = LL;
if(!b1&&!b2) ub = RR;
switch(ub) {
  case LL :LLr(a,prePos);
   break;
  case LR :LRr(a, prePos);
   break;
  case RR :RRr(a,prePos);
   break;
  case RL :RLr(a,prePos);
   break;
} //end switch
return true;
}
template<typename E>
bool AVL_TMP<E>::upRoutineDepth(vector<iterator>&routine){
//該函數(shù)主要是將路徑節(jié)點(diǎn)的深度更新并且使得那些不平衡的節(jié)點(diǎn)平衡
int size = routine.size();
while (size--) {
  updateDepth(routine[size]);
  if (!balance(routine[size])) {//不平衡得調(diào)整
   iterator cur = routine[size],prePos = NULL;
   if(size-1>=0)
    prePos = routine[size-1];
   //檢查當(dāng)前不平衡節(jié)點(diǎn)的哪顆子樹的高度更高
   bool bl = cur->ln != NULL;
   bool br = cur->rn != NULL;
   if (!bl) {//肯定有右孩子
    if(cur->rn->ln) RLr(cur,prePos);
    else RRr(cur,prePos);
   }
   else{//有左孩子
    if (!br) {//沒右孩子
     if (cur->ln->ln) LLr(cur,prePos);
     else LRr(cur,prePos);
    }
    else{ //有右孩子,此時(shí)需要檢查左右孩子的高度，則右子樹高度至少為1
     //因此左子樹高度至少為3，則左子樹的節(jié)點(diǎn)個(gè)數(shù)肯定大于4
     if (cur->ln->depth > cur->rn->depth) LLr(cur,prePos);
     else RRr(cur,prePos);
    }
   }
  }
}
return true;
}
template<typename E>
AVL_TMP<E>::iterator AVL_TMP<E>::findMax(AVL_TMP<E>::iterator pos){//以pos為根的樹的最大值的節(jié)點(diǎn)
if (!pos) return NULL;
iterator p = pos;
while(p->rn) p = p->rn;
return p;
}
template<typename E>
AVL_TMP<E>::iterator AVL_TMP<E>::findMin(AVL_TMP<E>::iterator pos){
iterator p = pos;
while (p->ln) p = p->ln;
return p;
}
template<typename E>
void AVL_TMP<E>::updateDepth(AVL_TMP<E>::iterator pos){
bool b1 = pos->ln == NULL,b2 = pos->rn ==NULL;
switch(b1) {
case true:
  if(b2) pos->depth = 0;
  else pos->depth = pos->rn->depth+1;
  break;
default: //false
  if(b2) pos->depth = pos->ln->depth+1;
  else pos->depth = max(pos->ln->depth , pos->rn->depth )+1;
}
if(pos == root) depth = pos->depth;
}
template<typename E>
void AVL_TMP<E>::LLr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos){
typename AVL_TMP<E>::iterator t, a = pos, b = t = pos->ln ;
pos->ln = t->rn;
t->rn = pos;
if(root == a) root = b;
if(prePos != NULL)
  if(prePos->ln == a) prePos->ln = b;
  else prePos->rn = b;
updateDepth(a);updateDepth(b);
}
template<typename E>
void AVL_TMP<E>::LRr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos){
AVL_TMP<E>::iterator a = pos,b = pos ->ln, c = b->rn;
b->rn = c->ln ; a->ln = c->rn;
c->ln = b; c->rn =a;
if(a == root ) root = c ;
if(prePos != NULL)
  if(prePos->ln == a) prePos->ln = c;
  else prePos->rn = c;
updateDepth(a);updateDepth(b);updateDepth(c);
}
template<typename E>
void AVL_TMP<E>::RRr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos ){
AVL_TMP<E>::iterator a = pos ,t, b = t = pos->rn ;
pos->rn = t->ln;
t->ln = pos;
if(prePos != NULL)
  if(prePos->ln == a) prePos->ln = b;
  else prePos->rn = b;
if(root == a) root = b;
updateDepth(a);updateDepth(b);
}
template<typename E>
void AVL_TMP<E>::RLr(AVL_TMP<E>::iterator pos,AVL_TMP<E>::iterator prePos){
AVL_TMP<E>::iterator a = pos, b = pos->rn , c = b->ln;
a->rn = c->ln ; b->ln = c->rn;
c->ln = a; c->rn = b;
if(prePos != NULL)
  if(prePos->ln == a) prePos->ln = c;
  else prePos->rn = c;
if( a == root) root = c;
updateDepth(a);updateDepth(b);updateDepth(c);
}
template<typename E>
bool AVL_TMP<E>::insert(const E& e){
if(root == NULL) {root = new AVL_NODE<E>(e); size++; depth = root->depth;return true;}
bool bUpdateDepth = false;
vector<AVL_TMP<E>::iterator> routin;
typename AVL_TMP<E>::iterator p = root,pos,prePos;
for (int i = 0 ; i < size ;i++ ) {
  routin.push_back(p);
  if(p->data > e){
   if ( p->ln == NULL ) {
    p->ln = pos = new AVL_NODE<E>(e);
    bUpdateDepth = p->rn == NULL;
    break;
   }
   else { p = p->ln ; continue;}
  }
  if(p->data < e){
   if (p->rn == NULL) {
    p->rn = pos = new AVL_NODE<E>(e) ;
    bUpdateDepth = p->ln == NULL;
    break;
   }
   else { p = p->rn ; continue;}
  }
  return false;   //already exists
}  //insertion finished
size++;
if(size <= 2 ) {
  updateDepth(root);
  return true;
}
if(!bUpdateDepth) return true;   //balance

bool unAdjusted = true;
// check for balance and adjust depth
for (i = routin.size()-1; i >=0 ; i-- ) {
  if(!balance(routin.at(i)))
   if(unAdjusted) { // unbalance! get unbalance type
    if(i-1 >= 0) prePos = routin.at(i-1);
    else prePos = NULL;
    AVL_TMP<E>::iterator a = routin.at(i) , b = routin.at(i+1) , c;
    if(i+2 >= routin.size() ) c = pos;
    else c = routin.at(i+2);
    bool b1,b2;
    b1 = b == a->ln;
    b2 = c == b->ln;
    unbalanceType ub;
    if(b1&&!b2)   ub = LR;
    if(!b1&&b2)   ub = RL;
    if(b1&&b2)    ub = LL;
    if(!b1&&!b2) ub = RR;

    switch(ub) {
     case LL :LLr(routin.at(i),prePos);
      break;
     case LR :LRr(routin.at(i),prePos);
      break;
     case RR :RRr(routin.at(i),prePos);
      break;
     case RL :RLr(routin.at(i),prePos);
      break;
    } //end switch
    unAdjusted = false;
   } //end if
updateDepth(routin.at(i));  //update the depth of the node in the routin
depth = root->depth;
}//end for
return true;
};
template<typename E>
AVL_TMP<E>::npos AVL_TMP<E>::find(const E& e){//search for position
   npos p=root;
   while (p&&p->data!=e)
    if(e>p->data) p=p->rn;
    else p= p->ln;
   return p;
}
template<typename E>
AVL_TMP<E>::npos AVL_TMP<E>::findpre(const E& e){//search for parent node position
   npos p,pre;
   p=pre=root;
   while (p&&p->data!=e) {
    pre = p;
    if (e>p->data) p=p->rn;
    else p = p->ln;
   }
   if(p) if(p->data==e) return NULL;//already existed
   return pre;
}
template<typename E>
bool AVL_TMP<E>::delAux(E const& e,AVL_TMP<E>::iterator pos){
// 1.遞歸刪除節(jié)點(diǎn)，直到刪除的是葉子節(jié)點(diǎn)
// 2. 刪除葉子節(jié)點(diǎn),更新樹的數(shù)據(jù)成員
// 3. 更新路徑上的節(jié)點(diǎn)深度并且檢查平衡因子
static vector<iterator> routine;
iterator p = pos;
bool bUpdate = false;
if(!pos){//第一次調(diào)用
  p = root;
  while (p&&e!=p->data) {//找到節(jié)點(diǎn)，并且將尋找路徑存入表中
   routine.push_back(p);
   if(p->data > e) p = p->ln;
   else p = p->rn;
  }
  if(p == NULL){ //沒找到
   routine.clear();
   return false;
  }
  else pos = p;
}
if (pos->ln||pos->rn) {//不是葉子節(jié)點(diǎn)，則該節(jié)點(diǎn)有孩子節(jié)點(diǎn)，可能是一個(gè)或者兩個(gè)
  routine.push_back(pos);//還得往下刪除
  if (pos->ln&&!pos->rn){ //情況一: 只有有左孩子
   //找到左子樹中的最大值的位置
   iterator max = pos->ln;
   while (max->rn) { routine.push_back(max); max = max->rn;}
   bUpdate = false;
   //偽刪除
   pos->data = max->data;
   delAux(max->data,max);
  }
  else if (!pos->ln&&pos->rn) { //情況二：只有右孩子
   //找到右子樹中的最小值
   iterator min = pos->rn;
   while (min->ln) { routine.push_back(min); min = min->ln;}
   bUpdate = false;
   //偽刪除
   pos->data = min->data;
   delAux(min->data,min);
  }
  else //情況三：有倆個(gè)孩子
  {
   //找到左子樹中的最大值
   iterator max = pos->ln;
   while (max->rn) { routine.push_back(max); max = max->rn;}
   bUpdate = false;
   //偽刪除
   pos->data = max->data;
   delAux(max->data,max);
  }
}
else
{//是葉子節(jié)點(diǎn)
  //有三種情況，是其父節(jié)點(diǎn)的左子樹且沒有兄弟，是其父節(jié)點(diǎn)的右子樹且沒有兄弟，有兄弟
  //取得其父節(jié)點(diǎn)
  iterator parent = NULL;
  if (routine.size()) //有父節(jié)點(diǎn)
   parent = routine[routine.size()-1];
  else{//即該節(jié)點(diǎn)是根節(jié)點(diǎn),無根節(jié)點(diǎn)
   delete root;
   routine.clear();
   upTree(-1,NULL,0);
   return true;
  } //完成根節(jié)點(diǎn)的刪除
  //有父節(jié)點(diǎn)
  if (pos == parent->ln&&!parent->rn) {//情況一：是父節(jié)點(diǎn)的左孩子且沒兄弟
   //刪除節(jié)點(diǎn)
   parent->ln = NULL;
   delete pos;
   //需要更新路徑上的節(jié)點(diǎn)的深度
   bUpdate = true;
   upRoutineDepth(routine);
   upTree(root->depth,root,size-1);
   routine.clear();
   //改寫父節(jié)點(diǎn)的孩子指針
  }//完成情況一葉子節(jié)點(diǎn)的刪除
  else{
   if (pos == parent->rn && !parent->ln ) { //情況二：是父節(jié)點(diǎn)的右孩子且沒兄弟
    parent->rn = NULL;
    delete pos;
    bUpdate = true;
    upRoutineDepth(routine);
    upTree(root->depth,root,size-1);
    routine.clear();
   }//完成情況二葉子節(jié)點(diǎn)的刪除
   else{//情況三：有兄弟
    //只需要將節(jié)點(diǎn)刪除，并清理路徑表就可以了
    if (pos == parent->ln) parent->ln = NULL;
    else parent->rn = NULL;
    delete pos;
    routine.clear();
   }//完成情況三的葉子節(jié)點(diǎn)刪除
  }
}
return true;
}

template<typename E>
bool AVL_TMP<E>::del(dataType e){
return delAux(e);
}

posted on 2007-10-05 15:47 zlf 閱讀(2584) 評(píng)論(2) 編輯收藏引用

評(píng)論

# re: AVL樹的簡(jiǎn)單實(shí)現(xiàn) 2007-10-05 16:15 Minidx全文檢索

其實(shí)這樣的寫法不能算簡(jiǎn)單拉
看看這個(gè) http://bbs.chinaunix.net/viewthread.php?tid=692071 回復(fù) 更多評(píng)論

# re: AVL樹的簡(jiǎn)單實(shí)現(xiàn) 2007-10-06 23:05 zlf

為什么呢?
刪除操作比插入操作的代碼多
你是否會(huì)覺得更刪除更復(fù)雜呢?
其實(shí)刪除的想法是很簡(jiǎn)單的,因?yàn)槭沁f歸的刪除直到遞歸到葉子節(jié)點(diǎn)
所以要?jiǎng)h除的只是葉子節(jié)點(diǎn).
不管是插入還是刪除節(jié)點(diǎn)深度的變化都只是在插入或刪除路徑節(jié)點(diǎn)上
這樣更新應(yīng)該很方便吧
至于旋轉(zhuǎn)操作之類的其實(shí)每必要去探討數(shù)學(xué)原理什么的
用數(shù)學(xué)來證明這東西應(yīng)該很難吧(我是這么想的),要不然怎么會(huì)是兩個(gè)數(shù)學(xué)家提出來的呢?
只要知道各種不平衡類型施行的操作就行的
而操作只需要畫畫圖就很容易看出來的
也許很亂
不過這樣想來要"實(shí)現(xiàn)"(只是實(shí)現(xiàn))AVL樹的話應(yīng)該就很簡(jiǎn)單了回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

# re: AVL樹的簡(jiǎn)單實(shí)現(xiàn) 2007-10-05 16:15 Minidx全文檢索

# re: AVL樹的簡(jiǎn)單實(shí)現(xiàn) 2007-10-06 23:05 zlf

zhulf753

AVL樹的簡(jiǎn)單實(shí)現(xiàn)

評(píng)論

導(dǎo)航

統(tǒng)計(jì)

常用鏈接

留言簿(1)

隨筆檔案

文章檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜