[TOC]

寫在前面

本篇文章整理《數(shù)據(jù)結(jié)構(gòu)（C++語言版）》關(guān)于二叉樹這種線性結(jié)構(gòu)知識點。
整個數(shù)據(jù)結(jié)構(gòu)部分章節(jié)列表如下:
1 向量
2 列表
3 棧
4 隊列
5 二叉樹
6 圖
7 二叉搜索樹

7 二叉搜索樹

設(shè)計初衷：高效的動態(tài)修改（如insert, remove）與高高效的靜態(tài)查找（search）能否兼顧？

循關(guān)鍵碼訪問

類似于python中的dict類型骑科，詞條對象擁有關(guān)鍵碼key與值value并通過key來尋找對應(yīng)節(jié)點罢屈。

template<typename K, typename V> struct Entry {  //詞條模板類
  K key; V value;
  Entry( K k = K(), V v = V() ) : key(k), value(v) {};  //默認構(gòu)造函數(shù)
  Entry( Entry<K, V> const & e) : key(e.key), value(e.value) {};
// 比較器滑绒、判斷器，可用詞條直接代替關(guān)鍵碼
  bool operator< ( Entry<K, V> const & e ) { return key < e.key; }
  bool operator> ( Entry<K, V> const & e ) { return key > e.key; }
  bool operator== ( Entry<K, V> const & e ) { return key == e.key; }
  bool operator!= ( Entry<K, V> const & e ) { return key != e.key; }
}

7.1 基礎(chǔ)操作

任意一顆二叉樹是二叉搜索樹當(dāng)且僅當(dāng)其中序遍歷序列單調(diào)非降。

BST與中序遍歷

template<typename T> class BST : public BinTree {  //由二叉樹（BT）派生
public:  //以virtual修飾聚谁，強制要求派生類根據(jù)各自規(guī)則重寫接口
  virtual BinNodePosi(T) & search( cosnt T & );
  virtual BinNodePosi(T) insert( const T & );
  virtual bool remove ( const T & );
protected:
  BinNodePosi(T) _hot;  //命中節(jié)點的父親
  BinNodePosi(T) connect34(  //3+4重構(gòu)
      BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), 
      BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), BinNodePosi(T) );  
  BinNodePosi(T) rotateAt( BinNodePosi(T) );  //旋轉(zhuǎn)調(diào)整
}

關(guān)于虛函數(shù)virtual
當(dāng)基類Base指針ptr指向派生類Derived的成員函數(shù)時母剥，調(diào)用派生類對應(yīng)的成員函數(shù)而不是基類成員函數(shù)（一般情況下，ptr是Base指針形导，其指向應(yīng)為Base成員函數(shù)）
>>>
class Base {
public:
void echo1() { std::cout << "called from Base" << endl; }
virtual void echo2() { std::cout << "called from Base" << endl; }
}
class Derived : public Base {
public:
void echo1() { std::cout << "called from Derived" << endl; }
void echo2() { std::cout << "called from Derived" << endl; }
}
int main() {
Base * ptr1 = new Derived;
ptr->echo1; //調(diào)用Base成員函數(shù)环疼，打印--called from Base
ptr->echo2; //調(diào)用Derived成員函數(shù)，打印--called from Derived
}

7.1.1 search接口

與二分查找類似朵耕，BST節(jié)點的中序遍歷即為單調(diào)有序向量形式炫隶。
如下圖，待查找節(jié)點e與當(dāng)前節(jié)點比較阎曹，若e較大伪阶，則深入該節(jié)點右子樹...依次遞歸。

查找算法

接口語義

template<typename T> BinNodePosi(T) & BST<T>::search(const T& e) {
  return searchIn(_root, e, _hot = NULL);
}
template<typename T>
static BinNodePosi(T) & searchIn(BinNodePosi(T) & v, const T& e, BInNodePosi(T) & hot){
  if( !v || ( e == v->data ) ) return v;  //待search值e已找到或遞歸節(jié)點v為空
  hot = v;  //hot指向“命中節(jié)點”的父親
  return searchIn( ( ( e < v->data ) ? v->lc : v->rc ), e, hot);
}

7.1.2 插入操作

根據(jù)search接口，命中節(jié)點v即為待查找節(jié)點e應(yīng)當(dāng)存在的位置注暗，因此只需將待插入節(jié)點作為命中節(jié)點v父親_hot的孩子插入即可坛缕。

template<typename T> BinNodePosi(T) BST<T>::insert( const T& e) {
  if( search(e) ) return search(e);  //若待插入節(jié)點存在，則停止插入
  BinNodePosi(T) & x = new BinNode<T> (e, _hot);  //創(chuàng)建新節(jié)點x捆昏，以e為關(guān)鍵碼赚楚，_hot為父
  _size++;
  updateHeightAbove(x);
  return x;
}  

7.1.3 刪除操作

與插入操作類似，首先通過search接口查找需要刪除節(jié)點位置屡立。
以下是刪除操作的代碼框架

template<typename T> bool BST<T>::remove( cosnt T& e ) {
  BinNodePosi(T) & x = search(e);
  if(!x) return false;  //待刪除元素不存在直晨，返回
  removeAt(x, _hot);  //刪除操作，需考慮兩種情況膨俐。
  size--;
  updateHeightAbove(_hot);
  return true;
}

分為兩種情況考慮勇皇，待刪除節(jié)點只有一個分支或有兩個分支。
出現(xiàn)這種分歧的原因是BST是按照中序遍歷序列排列的焚刺，插入或刪除操作都需要維持原始BST的有序性敛摘。
對于單分支，待刪除節(jié)點下只有比它大（腥橛洹）的節(jié)點兄淫，將其孩子直接代替刪除位置屯远，不影響B(tài)ST有序性。
對于多分支捕虽，待刪除節(jié)點的左（右）孩子替換刪除位置后慨丐，可能會導(dǎo)致新節(jié)點的左（右）子樹中存在比當(dāng)前節(jié)點大（小）的元素泄私。
如下圖房揭，若直接將58代替36會導(dǎo)致40、46晌端、53等比58小的節(jié)點存在右子樹中捅暴。

例

static BinNodePosi(T) removeAt( BinNodePosi(T) & x, BinNodePosi & hot ) {
  BinNodePosi(T) w = x;
  BinNodePosi(T) succ = NULL;
  if( ! HasLChild(*x) ) succ = x = x->rc;  //直接將rc覆蓋x即可刪除x節(jié)點
  else if( ! HasRChild(*x) ) succ = x =x->lc;
  else {
    w = w->succ();  //通過中序遍歷獲得x的直接后繼钧椰，即大于x的最小節(jié)點
    swap( x->data, w->data );  //只將兩節(jié)點data交換粹断，節(jié)點對應(yīng)的左右孩子指向未變
    BinNodePosi(T) u = w->parent;
    ( ( u == x) ? u->rc : u->lc ) = succ = w->rc;
  }
  hot = w->parent;
  if(succ) succ->parent = hot;
  release( w->data ); release(w);
  return succ;
} 

7.2 AVL樹

平衡二叉樹----在節(jié)點數(shù)目固定的前提下，盡可能降低樹的高度嫡霞，即盡可能使兄弟子樹的高度彼此接近瓶埋。漸進意義下樹高不超過O(log n)。
平衡因子----節(jié)點v的左右子樹高度差诊沪。

balFac(v) = height(lc(v)) - height(rc(v))

AVL樹----各節(jié)點平衡因子的絕對值不超過1.
接口定義----由BST派生得來养筒。

/**********************************
#define  stature(p) ((p) ? (p)->height : -1) //節(jié)點高度（與“空樹高度為-1”的約定相統(tǒng)一）
**********************************/
#define Balanced(x) ( stature( (x).lc ) == stature( (x).rc ) )  //理想平衡條件
#define BalFac(x) ( stature( (x).lc ) - stature( (x).rc ) )  //平衡因子
#define AvlBalanced(x) ( ( -2 < BalFac(x) ) && ( BalFac(x) < 2) )  //AVL平衡條件
template<typename T> class AVL : public BST<T> {
public:
  BinNodePosi(T) insert( const T& e);
  bool remove( const T& e);
}

7.2.1 平衡性

設(shè)高度為h的子樹至少含有S(h)個節(jié)點，則根據(jù)AVL平衡條件有如下等式成立端姚。
S(h) = S(h-1) + S(h-2) + 1

平衡性

節(jié)點刪除

節(jié)點插入

7.2.2 重平衡

插入重平衡
只需維護插入節(jié)點x導(dǎo)致第一個失衡祖先即可昏鹃，其余失衡祖先可隨之一并重平衡尚氛。
設(shè)g是首次失衡祖先，通過如下代碼即可完成由g找到x的祖先p或v洞渤。

/**************************************
#define IsLChild(x) ( ! IsRoot(x) && ( & (x) == (x).parent->lc ) )
該部分在BinNode中定義
**************************************/
#define tallerChild(x) ( \
    stature( (x)->lc ) > stature( (x)->rc ) ? (x)->lc : ( /*左子樹高*/ \
    stature( (x)->lc ) < stature( (x)->rc ) ? (x)->rc : ( /*右子樹高*/ \
    IsLChild( * (x) ) ? (x)->lc : (x)->rc /*等高阅嘶，與父親同側(cè)者優(yōu)先*/ \
    ) \
    ) \
)

單旋----g, p, v同側(cè)
BST中的等價變換為上下可變，左右不變。

單旋操作

雙旋

template<typename T> BInNodePosi(T) AVL<T>::insert( const T& e ) {
  BinNodePosi(T) & x = search(e); if(x) return x;  //判斷待插入節(jié)點是否存在
  BinNodePosi(T) xx = x = new BinNode<T> (e, _hot); _size++; //創(chuàng)建新節(jié)點
//重平衡
  for(BInNodePosi(T) g = _hot; g; g = g->parent) {  //查找首次遇到失衡祖先節(jié)點g
    if( !AvBalanced(*g) ) { // 一旦發(fā)現(xiàn)g失衡讯柔，采用“3+4”算法重平衡
      FromParentTo(*g) = rotateAt( tallerChild ( tallerChild(g) ) );
      break;
    } else //若未失衡抡蛙，只需更新樹高
      updateHeight(g);
  }
  return xx;
}

刪除重平衡
如下圖操作，重平衡后子樹的高度可能繼續(xù)降低魂迄，從而導(dǎo)致失衡向上傳播粗截。
單旋

單旋

雙旋

template<typename T> bool AVL<T>::remove( const T& e ) {
  BinNodePosi(T) x = search(e); if(!x) return false; //待刪除節(jié)點不存在，返回
  removeAt( x, _hot); _size--;
  for(BinNodePosi(T) g = _hot; g; g = g->parent) {
    if( !AvlBalanced(*g) )
      g = FromParentTo(*g) = rotateAt( tallerChild( tallerChild(g) ) );
    updateHeight(g);
  }
  return true;
}

7.2.3 3+4算法

將操作節(jié)點x與其先失衡祖先g以及g更高一側(cè)的子樹的孩子節(jié)點p, v設(shè)置為獨立的模塊捣炬。
整理得到如下兩類模塊：
3節(jié)點模塊：g, p, v
4子樹模塊:g不含p的子樹T1, p不含v的子樹T2, v的兩個子樹T3, T4
最終只需按著滿足中序遍歷方法將上述模塊重組為符合BST結(jié)構(gòu)即可慈格。

3+4算法

template<typename T> BinNodePosi(T) BST<T>::connect34 (
  BinNodePosi(T) a, BinNodePosi(T) b, BinNodePosi(T) c,
  BinNodePosi(T) T0, BinNodePosi(T) T1, BinNodePosi(T) T2, BinNodePosi(T) T3
) {
  a->lc = T0; if(T0) T0->parent = a;
  a->rc = T1; if(T1) T1->parent = a;
  c->lc = T2; if(T2) T2->parent = c;
  c->rc = T3; if(T3) T3->parent = c;
  b->lc = a; a->parent = b;
  b->rc = c; c->parent = b;
  updateHeight(b);
}

繼而可以將單旋、雙旋等操作直接整合如下遥金。

template<typename T> BinNodePosi(T) BST<T>::rotateAt(BinNodePosi(T) v) {
  BinNodePosi(T) p = v->parent;
  BinNodePosi(T) g = p->parent;
//視p, v, g相對位置分為四種情況
  if( IsLChild(*p) ) /*zig*/
    if( IsLChild(*v) ) {/*zig-zig*/
      p->parent = g->parent;
      return connect34(v, p, g, v->lc, v->rc, p->rc, g->rc);
    } else { /*zig-zag*/
       v->parent = g->parent;
      return connect34(p, v, g, p->lc, v->lc, v->rc, g->rc);
  } 
  else /* zag*/
    if( IsRChild(*v) ) { /*zag-zag*/
      p->parent = g->parent;
      return connect34(g, p, v, g->lc, p->lc, v->lc, v->rc);
    } else { /*zag-zig*/
      v->parent = g->parent;
      return connect34(g, v, p, g->lc, v->lc, v->rc, p->rc);
    }  
}