https://twinkle0331.github.io/bst.html

1 查找

1.1 循关键码访问

查找或搜索（search）：指从一组数据对象中找出符合特定条件者，这是构建算法的一种基本而重要的操作。

其中的数据对象，统一地表示和实现为词条(entry)的形式；不同词条之间，依照各自的关键码（key）彼此区分。

如：根据身份证号查找特定公民，根据车牌号查找特定车辆，根据国际统一书号查找特定图书，均属于根据关键码查找特定词条的实例。

请注意，与此前的“循秩访问”和“循位置访问”等完全不同，这一新的访问方式，**与数据对象的物理位置或逻辑次序均无关。实际上，查找的过程与结果，仅仅取决于目标对象的关键码，
故这种方式亦称作**循关键码访问（call-by-key）。

1.2 词条

一般的，对于词条，主要有：“关键码”、“数值”组成。（好比于键值对）

#ifndef DSACPP_BST_ENTRY_H_
#define DSACPP_BST_ENTRY_H_
/*词条*/
template<class K, class V>
class Entry
{
public:
    K key_; V value_; //关键码、数值
    Entry(K k = k(),V v = v()) //k()：表示默认值为0，就相当于k = k() ==》k=0（https://stackoverflow.com/questions/46330646/what-does-const-k-k-k-mean-in-this-constructor-function）
        :key_(k), value_(v)
    {}
    Entry(const Entry<K, V>& e) //拷贝构造函数
        : key_(e.key_), value_(e.value_)
    {}
    // 比较器、判断器
    bool operator< (const Entry<K, V>& e){return key_ < e.key_;}
    bool operator> (const Entry<K, V>& e) {return key_ > e.key_;}
    bool operator== (const Entry<K, V>& e) {return key_ == e.key_;}
    bool operator!= (const Entry<K, V>& e) {return key_ != e.key_;}
};
#endif

2 二叉搜索树

顺序性：
若二叉树中各节点所对应的词条之间支持大小比较，则在不致歧义的情况下，我们可以不必严格区分树中的节点、节点对应的词条以及词条内部所存的关键码。

在所谓的二叉搜索树(binary search tree，BST）中，处处都满足顺序性：
任一节点r的左（右）子树中，所有节点（若存在）均不大于（不小于）r；

单调性：
在微观上满足顺序性，在宏观上满足单调性，单调性：
BST的中序遍历序列，必然单调非降

考查二叉树中的任一节点r，按照中序遍历的约定，r左(右)子树中的节点(若存在)均应先于(后于)r接受访问。
按照二叉搜索树的定义，r左(右)子树中的节点(若存在)均不大于(不小于)r，故中序遍历序列必然在r处单调非降，反之亦然。
鉴于以上所取r的任意性，在二叉搜索树中处处成立。
即，有：
任何一颗二叉树是二叉搜索树时，当且仅当其中序遍历序列单调非降**

2.1 查找

假设查找data_ = e的节点。首先从根节点v开始，如果：

e = v.data_，则查找成功；
e < v.data_，继续在左子树中查找；
e > v.data_，继续在右子树中查找；

对照中序遍历来看，整个过程可视为仿效有序向量的二分查找。

查找22所在节点的过程

注意：此处使用了“哨兵”，当查找失败时，假象的哨兵等效于叶节点。

//查找
template<class T>
BinNodePosi<T>& BST<T>::search(const T& e)  //在BST中查找关键码e
{
    return searchIn(root_, e, hot_ = nullptr); //返回目标节点位置的引用，以便后续插入、删除操作
}
template<class T>
static BinNodePosi<T>& searchIn(BinNodePosi<T>& v, const T& e, BinNodePosi<T>& hot)
{
    if ((e == v->data_) || !v) // 递归基
    {// 当（e == v->data_）时，查找成功；
     // 当v节点为空时，查找失败,也返回一个值（此时该值为null）【这里使用了哨兵策略】
        return v->data_;
    }
    hot = v; //一般情况：记录当前节点，然后继续深入一层递归
    return searchIn((e > v.data_) ? v->rc_ : v->lc_, e, hot);
} //返回时，返回值指向命中节点（或假想的通配哨兵），hot指向其父亲（退化时为初始值NULL）

hot_：指向“命中节点”的父亲节点；
查找成功时，返回的值如（7.6a）中所示，指向一个关键码为e且真实存在的节点；
查找失败时，返回值的数值为null，但是它作为引用将如（7.6b）所示，指向最后一次试图转向的空节点。假象此空节点为值为e的一个 哨兵节点。

因此无论成功与否，查找的返回值总是等效的指向“命中节点”。

无论树的具体形态如何，查找必然有n种成功情况和n+1种失败情况。

效率：
在二叉搜索树的每一层，查找算法至多访问一个节点，且访问时只需常数时间，因此总体的时间正比于查找路径长度。

最好的情况，目标关键码刚好出现在树根节点处(或附近)，此时只需O(1时间。
最坏的情况，规模为nn的二叉搜索树深度可能达到Ω(n)，比如该树退化为一条单链时，此时的查找等效于顺序查找。
- 因此，若要控制单次查找在最坏的情况下运行的时间，必须控制二叉搜索树的高度。【如后面的平衡二叉树】

2.2 插入

为了在二叉搜索树中插入一个顶点，首先需要利用查找算法search() 确定插入的位置和方式，然后才能将新节点作为叶子插入。

实际上，再使用search() 确定插入的位置时，插入位置实际上都在叶子节点的孩子位置。

无论是插入40、55，都可以看出插入位置是在叶子节点的左孩子或右孩子位置。

//插入
template<class T>
BinNodePosi<T> BST<T>::insert(const T& e)
{
    BinNodePosi<T>& x = search(e); //查找，找出要插入的位置
    if (x) return x; //确认目标不存在（留意对hot_的设置）[即，如果要插入的值e，在原二叉搜索树中本来就存在，则直接返回]
    x = new BinNode<T>(e, hot_); //创建新节点，以e为关键码，以hot_为父亲
    //开始更新祖先的高度，以及二叉树的规模
    ++size_;
    updateHeightAbove(x); //更新祖先的高度
    return x; //新插入的节点，必为叶节点
} //无论e是否存在于原树中，返回时总有x->data == e

这里需要注意，在创建新节点x的时候，只是指定了父亲为hot，并没有指定hot的左孩子还是右孩子为x，为什么？

答：在前一步的search过程中，返回了命中节点的引用，通过对x的赋值来连接父子节点，同时也将x接入树中。所以，不用显示指定x到底是hot的左孩子 or 右孩子。

效率：

插入操作必定在叶节点处，同样取决于节点的深度，在最坏情况下不超过全树的高度，即最深的叶子的深度。

在二叉树树中插入节点v之后，除v的历代祖先外，其余节点的高度无需更新：

节点的高度仅取决于其后代，更确切地，是该节点与其最深后代之间的距离。因此在插入节点vv之后，节点aa的高度可能发生变化，当且仅当vv是aa的后代，或反过来等价地，a是v的祖先。

2.3 删除

首先，也是利用search函数，找到要删除的节点（假设为节点v）。
然后，分情况删除：
- 单分支情况：（包含：只有左孩子、只有右孩子、左右孩子均无（叶节点））
  - 只有左或右孩子：直接将该节点（将要删除的节点）替换为其左或右孩子节点即可。
  - 左右孩子均无：直接删除该节点即可。【代码实现时，与只有左或右孩子一样，只是此时替换的孩子节点为空】
- 双分支情况（左右孩子均存在）：
  - 首先，找出v的直接后继节点succ（是在中序遍历中的直接后继）。【该后继节点必无左孩子】
  - 然后，将v、与其后继节点succ的值进行交换。（使用swap函数）
  - 此时，删除交换后的后继节点succ（此时节点succ的值已经交换过了）。【此时删除succ节点的办法，就是单分支情况】

最后，注意不要忘记更新整个树的规模size_和后继节点succ的祖先节点的高度。

// 删除
template<class T>
bool BST<T>::remove(const T& e)
{
    BinNodePosi<T>& x = search(e); if (!x) return false; //确认要删除的目标存在（留意hot_的设置）
    removeAt(x, hot_);
    //更新二叉搜索树
    --size_;
    updateHeightAbove(hot_); //因为x节点被删除，所以从其父节点开始的祖先进行高度更新
    return true;
} //删除成功与否，由返回值指示
template<class T>
static BinNodePosi<T> removeAt(BinNodePosi<T>& x, BinNodePosi<T> hot)
{
    BinNodePosi<T> w = x; //实际被删除的节点，初值同x
    BinNodePosi<T> succ = nullptr; //实际被删除的节点的后继节点（是中序遍历中的后继节点）
    //分情况讨论：1.被删除的节点只有 右孩子、左孩子、无孩子；2.左右孩子均存在
    if (!HasLChild(*x)) //1.1不存在左子树
        succ = x->rc_;  //则，直接*x替换为右子树（x可能是叶子节点，此时其直接后继为空）
    else if (!HasRChild(*x)) //1.2 不存在右子树
        succ = x->lc_;       // 则，直接将*x替换为左子树（x可能是叶子节点，此时其直接后继为空）
    else // 2.左右子树均存在
    {
        w = w->succ(); //找到*x的直接后继*w
        swap(x->data_, w->data_);
        BinNodePosi<T> u = w->parent_;
        ((u == x) ? u->rc_ : u->lc_) = succ = w->rc_;
    }
    hot = w->parent_; //记录被删除节点的父亲
    if (succ) //如果被删除节点的直接后继存在，则
    {//将被删除节点w的父节点与w的直接后继相连
        succ->parent_ = hot; //父节点确定
        succ = ((hot->lc_ == w) ? hot->lc_ : hot->rc_); //确定是左孩子还是右孩子
    }
    release(w); release(w->data_); //释放被摘除的节点
    return succ; //返回接替者
}

效率：

算法操作所需的时间主要消耗于对search()，succ()，updateHeightAbove()的调用。在树的任意高度，它们至多消耗O(1)O(1)时间，故总体的渐进时间复杂度亦不超过全树的高度。

3 平衡二叉搜索树（BBST）

树高与性能：
二叉搜索树的性能主要取决于树高，故在节点数目固定时应尽可能地降低高度。

节点数目固定时，兄弟子树的高度越接近(平衡)，全树也倾向于更低。

**理想平衡与适度平衡：

理想平衡：包含N个节点的二叉树，高度不小于。若树高恰好为时，该树为理想平衡树。大致相当于完全树、满二叉树：叶节点只能出现在最底部的两层。
- 遗憾的是：完全二叉树的限制过于苛刻相对二叉树所有可能的形态，此类二叉树所占比例极低，而随着二叉树规模的增大，这一规模还将继续锐减。所以对标准适度放松，依照某种相对宽松的标准，重新定义二叉搜索树的平衡性。
  
  证明：若高度为的二叉树共含个节点，则必有：
  
  注意，这里规定：1. 只含一个节点的数的高度为0；2. 空树的高度为-1。
  
  这里的等号成立，当且仅当是满树。于是有：

适度平衡：在渐进意义下适当放松标准之后的平衡性（如：高度在渐进意义上不超过），称作适度平衡。
- 适度平衡的BST，称作平衡二叉搜索树（balanced binary search tree，BBST）之列。

3.1 等价变换

若两棵二叉树的中序遍历序列相同，则称它们彼此等价。

由上图，虽然等价二叉搜索树中各节点的垂直高度可能有所不同，但水平次序完全一致。这一特点可概括为“上下可变，左右不乱”，它也是以下等价变换的基本特性。

上下可变：联接关系不同，承袭关系可能颠倒；
左右不乱：中序遍历序列完全一致，全局单调非降。

局部性：
各种平衡二叉搜索树(BBST)可视为BST的某一子集，相应地满足限制条件。除了适度平衡性，还具有如下局部性：

刚刚失去平衡的二叉搜索树，必然可以迅速转换为一棵等价的平衡二叉搜索树。等价二叉搜索树之间的上述转换过程，也称作等价变换。

3.2 旋转调整

修复局部失衡的最基本手段，就是通过围绕特定节点的旋转，实现等价前提下的拓扑调整。

之后的平衡二叉搜索树的旋转调整策略，都将依据此。

Zig（右旋）[顺时针]、 Zag（左旋）[逆时针]

设c和Z是v左孩子、右子树，X和Y是c的左、右子树。以v为轴的zig旋转，如图所示，重新调整这两个节点和三棵子树之间的关系，将X和v作为c的左子树、右孩子，Y和Z分别作为v的左、右子树。
对称地，设X和c是v左子树、右孩子，Y和Z是c的左、右子树。以v为轴的zag旋转，如图所示，重新调整这两个节点和三棵子树之间的关系，将X和Y作为v的左子树、右子树，v和Z分别作为c的左孩子、右子树。

zig和zag均属于局部操作，旋转以后中序遍历序列依然不变，故均为等价变换。旋转操作仅涉及常数顶点及其之间的联接关系，故均可在常数时间内完成。

4 AVL树

AVL树是平衡二叉搜索树，不过它有一些限制：
AVL树中的各节点的左、右子树的高度差的绝对值 ≤ 1【左子树高度 - 右子树高度】
**
通过合理设定适度平衡的标准，并借助以上等价变换，AVL树可实现近似理想的平衡。在渐进意义上，AVL树可始终将其高度控制在 chapter7 搜索树 - 图19 以内，从而保证每次查找、插入或删除操作均可在 chapter7 搜索树 - 图20 时间内完成。

任一节点的平衡因子定义为其左、右子树的高度差，即
chapter7 搜索树 - 图21

注意：本书的空树高度为-1，单叶子子树（叶节点）的高度为0

AVL树，即平衡因子受限的二叉搜索树，其中各节点平衡因子的绝对值均不超过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平衡条件

4.1 平衡性：

完全二叉树中各节点的平衡因子非0即1，故完全二叉树必是AVL树；反之，AVL树不一定是完全二叉树。AVL的平衡性如何呢？先来看看高h的AVL树至少有多少个节点：

高度为h的AVL树至少包含 chapter7 搜索树 - 图22 个节点。

| 证明：（数学归纳）
- 当h=0时，T中至少包含fib(3)-1 = 2-1=1个节点，命题成立；
- 当h = 1时，T中至少包含fib(4）- 1 = 3- 1 =2个节点，命题也成立。
- 假设对于高度低于h的任何AVL树，以上命题均成立。现考查高度为h的所有AVL树，并取S为其中节点最少的任何一棵（请注意，这样的S可能不止一棵）。如图7.13，设S的根节点为r，r的左、右子树分别为S和S，将其高度记作h和h，其规模记作|S````|和|S````|。于是就有：|S| = 1+ |S``L``|+|S``R``|。

| | —- |

4.2 失衡与重平衡：

4.2.1 失衡

按照BST规则动态操作之后，AVL的平衡性可能破坏：

插入：从祖父开始，每个祖先都有可能失衡，且可能同时失衡；
删除：从父亲开始，每个祖先都有可能失衡，但至多一个；

4.2.2 重平衡：

通过旋转等价变换恢复平衡，累计操作不过 chapter7 搜索树 - 图27 。

具体操作分为：单旋、双旋【旋转具体操作位于3.2 旋转调整】

zig-zig、zag-zag：属于单旋情况；
zig-zag、zag-zig：属于双旋情况；第一次旋转目的：转为单旋情况；第二次旋转：按照单旋情况旋转。
- zig-zig：表示P、V均是右孩子；
- zag-zag：表示P、V均是左孩子；
- zig-zag：表示P是左孩子、V是右孩子；
- zag-zig：表示P是右孩子、V是左孩子；

4.2.2.1 单旋

（zag-zag）
（zig-zig）
单旋情况下，只用对位于最深的失衡节点（上图中是g节点）进行相应的单旋操作。【旋转具体操作位于3.2 旋转调整】

4.2.2.2 双旋

（zag-zig）
（zig-zag）
双旋情况下，两次单旋的顺序是： 从下而上的顺序开始；

首先：v为右孩子，则进行zag(p)单旋操作；v为左孩子，则进行zig(p)操作；【得到图b】
然后：在图b中，按照单旋的情况进行zig(g)或者zag(g)操作。

4.3 节点插入

插入节点x之后，可能有多个失衡节点。插入操作必定位于叶节点处，叶节点的父亲必不失衡，故失衡节点中最低者g不低于x祖父。

在x和g(x)的通路上，设p为g(x)的孩子，v为p的孩子。g(x)是由于x的引入而失衡，则p和v的高度均不会低于各自的兄弟。因此可通过以下宏定义由g(x)找到p和v。【我将宏定义改为函数了】

注意：有可能v和新插入点x是同一个节点。如上图x（M）是新插入节点，引起失衡的最深节点为g(x)（N），则p（K），从而v就是M，即v和新插入点x是同一个节点。

// 通过g(x)节点，找到p、v节点（调用该函数一次，只能找到p，再次调用才能得到v）,如：
// tallerChild(tallerChild(g))得到的才是v
/***************************************************************************
* g(x)：新引入节点后，引起失衡的最深者的节点；
* p：为g(x) 的孩子；
* v：为p的孩子；【v有可能与x是同一个节点】
****/
template<typename T>
BinNodePosi<T> tallerChild(BinNodePosi<T> g)
{
    if (stature(x->lc_) > stature(x->rc_)) //左高
        return x->lc_;
    else if (stature(x->lc_) < stature(x->rc_)) //右高
        return x->rc_;
    else if (stature(x->lc_) = stature(x->rc_)) //等高：与父亲x 同侧者（zig-zig或者 zag-zag）优先【同侧时，只需要单旋即可恢复平衡】
        return IsLChild(*x) ? x->lc_ : x->rc_;
}

这里通过比较子树的高度直接计算。失衡节点的恢复方案取决于节点g(x)、p、v之间具体的联接方向，即根据它们的位置来确定是需要单旋、还是双旋。

//插入（代码7.11）
template<class T>
BinNodePosi<T> AVL<T>::insert(const T& e) 
{
    BinNodePosi<T>& x = search(e); if (x) return x; //如果寻找到e（即x节点存在），那么就不用插入了（因为已经存在），则直接返回
    BinNodePosi<T> xx = x = new BinNode<T>(e, hot_);  size_++;//创建新节点x

    //此时，x的父亲hot_若增高，则其祖父有可能失衡
    for (BinNodePosi<T> g = hot_; g; g = g->parent_)
        if (!AvlBalanced(*g)) //找到最深的失衡节点g，则采用“3+4”算法，进行复衡，并将子树重新并入原树中
        {
            FromParentTo(*g) = rotateAt(tallerChild(tallerChild(g))); //使用“FromParentTo(g*)”表示：g的父亲节点的孩子指针 来 指向这个复衡的子树的根节点（从而将子树重新并入原树中）
            break; //⭐⭐这里是与删除操作最大的区别的地方，因为在插入操作中，引起的局部失衡，只需要将局部复衡之后，整个树就复衡了。
        }
        else //否则（g依然平衡），则只需简单的
        {
            updateHeight(g); //只更新g的高度（因为在for循环中，所以每次循环只更新它自己，循环结束其他节点高度也更新了）【虽然g未失衡，但是其高度还是有可能增加的】
        }

    return xx; //最后返回新节点的位置
}

注意：
在代码含⭐处，是与删除操作最大区别的地方。插入操作只需要将局部失衡的子树，复衡。则全树边复衡。
而删除操作中，有失衡传播现象。需要对祖先都进行复衡操作。

效率：

4.4 删除操作

与插入操作不同，在删除节点x之后，以及随后的调整过程中，失衡节点集UT(x)始终至多含有一个节点。而若该节点g(x)存在，其高度必然与失衡前相同。

而且，失衡节点首个可能就是x的父亲hot_。

之所以g(x)节点会失衡，是因为删除的节点x，刚好位于g(x)节点的更短的分支那一侧。

重平衡：

使用search()函数，找到失衡节点g(x)，需花费时间。
在失衡节点不包含x（被删除节点）的一侧，必有一个非空孩子p，且P的高度至少为1。于是可以按照以下规则从p的两个孩子（其一可能为空）中选出v节点。
- 规则：若两个孩子不等高，则v取作其中的更高者；否则，优先取v与p同向者(亦即，v与p同为左孩子，或者同为右孩子)。

以下不妨假定失衡后g(x)的平衡因子为+2（为-2的情况完全对称）。根据祖孙三代节点g(x)、p和v的位置关系，通过以g(x)和p为轴的适当旋转，同样可以使得这一局部恢复平衡。

4.4.1 失衡传播

在删除节点后，通过单旋或双旋调整使局部子树恢复平衡，但是恢复平衡后，**子树的高度未必可以复原**，可能再次失衡。

设g(x)复衡之后，局部子树的高度的确降低。此时，若g(x)原本属于某一更高祖先的更短分支，则因为该分支现在又进一步缩短，从而会致使该祖先失衡。在摘除节点之后的调整过程中，这种由于低层失衡节点的重平衡而致使其更高层祖先失衡的现象，称作“失衡传播”。

注意：
失衡传播的方向必然为自底而上，而不至于影响到后代节点。在此过程的任一时刻，至多只有一个失衡的节点；高层的某一节点由平衡转为失衡只可能发生在下层失衡节点恢复平衡之后。因此，可沿parent_指针遍历所有祖先，每找到一个失衡的祖先节点，即可套用以上算法使之恢复平衡。

在AVL树中摘除一个节点后，刚刚通过调整使g(x)g(x)恢复了平衡，此时，若发现g(x)原先的父节点依然平衡，在更高层仍可能有失衡的祖先，仅仅通过平衡性不足以确定可否终止自底而上的重平衡过程，转而核对重平衡后节点的高度可判断是否可以立即终止上溯过程。

//删除
template<class T>
bool AVL<T>::remove(const T& e)
{
    BinNodePosi<T>& x = search(e); if (!x) return false; //如果没找到要删除的节点，则返回false
    removeAt(x, hot_); --size_; //先按照BST规则删除，（此后被删除节点的父亲、祖先均有可能失衡）

    for (BinNodePosi<T> g = hot_; g; g = g->parent_)
    {
        if (!AvlBalanced(*g)) //一旦发现失衡，使用“3+4”算法使之复衡
        {
            g = FromParentTo(*g) = rotateAt(tallerChild(tallerChild(g))); //并将该子树连接至原树中
            //注意，⭐⭐这里不要“break;”。因为局部复衡之后，祖先节点有可能还是失衡的，所以要循环着对每一个祖先判断，如果失衡就将其复衡
            updateHeight(g);
        }
    }
    return true; //删除成功
}

节点的平衡与否取决于其左、右子树之差。因此反过来，只要子树的高度不变，则节点不可能失衡。

效率：

4.5 统一平衡算法：“3+4”

上述的平衡算法，需要根据失衡节点及其孩子节点、孙子节点的相对位置关系，分别做单旋或双旋调整。按照这一恩路直接实现调整算法，代码量大且流程繁杂，必然导致调试困难且容易出错。为此，以下引入一种更为简明的统一处理方法。

使用这种方法，就不需要再分单旋、双旋的情况。只需要将其转换为如下图所示的子树。

无论对于插入或删除操作，新方法也同样需要从刚发生修改的位置x出发逆行而上，直至遇到最低的失衡节点g(x)。于是在g(x)更高一侧的子树内，其孩子节点p和孙子节点v必然存在，而且这一局部必然可以g(x)、p和v为界，分解为四棵子树——按照图7.15至图7.18中的惯例，将它们按中序遍历次序重命名为T0至T3。

若同样按照中序遍历次序，重新排列g(x)、p和v，并将其命名为a、b、c，则这一局部的中序遍历序列应为：
{ T0, a, T1, b, T2, c, T3}
这一局部应等价于下图：

图 7.19 节点插入后的统一重新平衡

观察之前的例子，可以发现四棵子树的高度彼此相差不过一层，所以将这四棵树重新组装起来恰好即是一棵AVL树。

“3+4”重构算法【重构成上图所示的AVL子树】

//“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)
{
    //判断Tx(x = 0、1、2、3)是否存在，是因为子树Tx有可能为空树
    a->lc_ = T0; if (T0) T0->parent_ = a; 
    a->rc_ = T1; if (T1) T1->parent_ = a; updateHeight(a); //更新节点a的高度
    c->lc_ = T2; if (T2) T2->parent_ = c;
    c->rc_ = T3; if (T3) T3->parent_ = c; updateHeight(c); //更新节点c的高度
    b->lc_ = a; a->parent_ = b;
    b->rc_ = b; c->parent_ = b; updateHeight(b); //更新节点b的高度

    return b; //返回该子树的新的根节点
}

利用“3+4”重构算法，视不同情况，完成重构：

传入connect34函数中的参数

template <typename T> BinNodePosi(T) BST<T>::rotateAt ( BinNodePosi(T) v ) { //v为非空孙辈节点
   /*DSA*/if ( !v ) { printf ( "\a\nFail to rotate a null node\n" ); exit ( -1 ); }
   BinNodePosi(T) p = v->parent; BinNodePosi(T) g = p->parent; //视v、p和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 );
      }
}

该算法的复杂度依然是 chapter7 搜索树 - 图38