[TOC]

写在前面

本篇文章整理《数据结构（C++语言版）》关于二叉树这种线性结构知识点。
整个数据结构部分章节列表如下:
1 向量
2 列表
3 栈
4 队列
5 二叉树
6 图
7 二叉搜索树

7 二叉搜索树

设计初衷：高效的动态修改（如insert, remove）与高高效的静态查找（search）能否兼顾？

循关键码访问

类似于python中的dict类型，词条对象拥有关键码key与值value并通过key来寻找对应节点。

template<typename K, typename V> struct Entry {  //词条模板类
  K key; V value;
  Entry( K k = K(), V v = V() ) : key(k), value(v) {};  //默认构造函数
  Entry( Entry<K, V> const & e) : key(e.key), value(e.value) {};
// 比较器、判断器，可用词条直接代替关键码
  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 基础操作

任意一颗二叉树是二叉搜索树当且仅当其中序遍历序列单调非降。

BST与中序遍历
从上图可以看出，二叉搜索树（BST）中序遍历序列形式上与有序向量相同。
BST模板类
这里假定基本元素类型T或者直接支持比较和判别操作，或者已经重载过对应操作符。

template<typename T> class BST : public BinTree {  //由二叉树（BT）派生
public:  //以virtual修饰，强制要求派生类根据各自规则重写接口
  virtual BinNodePosi(T) & search( cosnt T & );
  virtual BinNodePosi(T) insert( const T & );
  virtual bool remove ( const T & );
protected:
  BinNodePosi(T) _hot;  //命中节点的父亲
  BinNodePosi(T) connect34(  //3+4重构
      BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), 
      BinNodePosi(T), BinNodePosi(T), BinNodePosi(T), BinNodePosi(T) );  
  BinNodePosi(T) rotateAt( BinNodePosi(T) );  //旋转调整
}

关于虚函数virtual
当基类Base指针ptr指向派生类Derived的成员函数时，调用派生类对应的成员函数而不是基类成员函数（一般情况下，ptr是Base指针，其指向应为Base成员函数）
>>>
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; //调用Base成员函数，打印--called from Base
ptr->echo2; //调用Derived成员函数，打印--called from Derived
}

7.1.1 search接口

与二分查找类似，BST节点的中序遍历即为单调有序向量形式。
如下图，待查找节点e与当前节点比较，若e较大，则深入该节点右子树...依次递归。

查找算法
若查找失效，则将此空节点视作哨兵节点。
这样无论是否查找成功，命中节点v都指向e应当存在的位置，_hot指向v的父亲。
接口语义

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已找到或递归节点v为空
  hot = v;  //hot指向“命中节点”的父亲
  return searchIn( ( ( e < v->data ) ? v->lc : v->rc ), e, hot);
}

7.1.2 插入操作

根据search接口，命中节点v即为待查找节点e应当存在的位置，因此只需将待插入节点作为命中节点v父亲_hot的孩子插入即可。

template<typename T> BinNodePosi(T) BST<T>::insert( const T& e) {
  if( search(e) ) return search(e);  //若待插入节点存在，则停止插入
  BinNodePosi(T) & x = new BinNode<T> (e, _hot);  //创建新节点x，以e为关键码，_hot为父
  _size++;
  updateHeightAbove(x);
  return x;
}  

7.1.3 删除操作

与插入操作类似，首先通过search接口查找需要删除节点位置。
以下是删除操作的代码框架

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;
}

分为两种情况考虑，待删除节点只有一个分支或有两个分支。
出现这种分歧的原因是BST是按照中序遍历序列排列的，插入或删除操作都需要维持原始BST的有序性。
对于单分支，待删除节点下只有比它大（小）的节点，将其孩子直接代替删除位置，不影响BST有序性。
对于多分支，待删除节点的左（右）孩子替换删除位置后，可能会导致新节点的左（右）子树中存在比当前节点大（小）的元素。
如下图，若直接将58代替36会导致40、46、53等比58小的节点存在右子树中。

例
1 单分支
这种情况下，直接删除节点，并将其孩子替换掉原在位置。
2 多分支
保持BST有序性的核心在于将距离待删除节点最近的节点代替删除位置，随后重复单分支操作情况。
综上所述，removeAt()实现代码如下。

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节点
  else if( ! HasRChild(*x) ) succ = x =x->lc;
  else {
    w = w->succ();  //通过中序遍历获得x的直接后继，即大于x的最小节点
    swap( x->data, w->data );  //只将两节点data交换，节点对应的左右孩子指向未变
    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树

平衡二叉树----在节点数目固定的前提下，尽可能降低树的高度，即尽可能使兄弟子树的高度彼此接近。渐进意义下树高不超过O(log n)。
平衡因子----节点v的左右子树高度差。

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

AVL树----各节点平衡因子的绝对值不超过1.
接口定义----由BST派生得来。

/**********************************
#define  stature(p) ((p) ? (p)->height : -1) //节点高度（与“空树高度为-1”的约定相统一）
**********************************/
#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 平衡性

设高度为h的子树至少含有S(h)个节点，则根据AVL平衡条件有如下等式成立。
S(h) = S(h-1) + S(h-2) + 1

平衡性
节点删除--失衡
1.节点删除只可能会导致其父节点失衡
2.被删除节点父亲的树高未变（子树高度最大者+1），因而其祖先的平衡因子不会改变。
节点删除
节点插入--失衡
1.节点插入可能会导致其祖先发生一连串的失衡。
2.被删除节点父亲的树高可能发生变化（子树高度最大者+1），因而其祖先的平衡因子可能会打破。
节点插入

7.2.2 重平衡

插入重平衡
只需维护插入节点x导致第一个失衡祖先即可，其余失衡祖先可随之一并重平衡。
设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 /*等高，与父亲同侧者优先*/ \
    ) \
    ) \
)

单旋----g, p, v同侧
BST中的等价变换为上下可变，左右不变。

单旋操作
双旋----g, p, v不在同侧
双旋

template<typename T> BInNodePosi(T) AVL<T>::insert( const T& e ) {
  BinNodePosi(T) & x = search(e); if(x) return x;  //判断待插入节点是否存在
  BinNodePosi(T) xx = x = new BinNode<T> (e, _hot); _size++; //创建新节点
//重平衡
  for(BInNodePosi(T) g = _hot; g; g = g->parent) {  //查找首次遇到失衡祖先节点g
    if( !AvBalanced(*g) ) { // 一旦发现g失衡，采用“3+4”算法重平衡
      FromParentTo(*g) = rotateAt( tallerChild ( tallerChild(g) ) );
      break;
    } else //若未失衡，只需更新树高
      updateHeight(g);
  }
  return xx;
}

删除重平衡
如下图操作，重平衡后子树的高度可能继续降低，从而导致失衡向上传播。
单旋

单旋
双旋
双旋

template<typename T> bool AVL<T>::remove( const T& e ) {
  BinNodePosi(T) x = search(e); if(!x) return false; //待删除节点不存在，返回
  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算法

将操作节点x与其先失衡祖先g以及g更高一侧的子树的孩子节点p, v设置为独立的模块。
整理得到如下两类模块：
3节点模块：g, p, v
4子树模块:g不含p的子树T1, p不含v的子树T2, v的两个子树T3, T4
最终只需按着满足中序遍历方法将上述模块重组为符合BST结构即可。

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);
    }  
}