本来这篇文章想聊聊BBST，和BBST的一种具体实现-AVl，但文章写完后，篇幅太长了，达到了万字长文，所以我将文章拆分成了两篇，今天我们先聊聊BBST到底是什么？明天我会把AVL的相关内容发出来。
平衡与等价
根据上篇文章对BST的观察不难发现：节点数目固定时，兄弟子树高度越接近（平衡），全树叶将倾向于更低。我们把由n个节点组成的二叉树，高度不低于log(n) - 恰为log(n)时，称作理想平衡。
但达到这种理想状态很难，例如完全二叉树和满二叉树，即使能构造出完全二叉树，其中的维护成本又太高。例如：使用数组实现完全二叉树是一种常见的形式，但这相当于把BST退化成了List，所有的插入和删除操作，都会涉及到部分或者大面积的元素移动。
那么我们是不是可以适当放宽理想平衡的条件，来达到一个适度平衡的状态呢？
如上图所示，如果n个节点所能组成的所有BST为一个大的集合，那CBT（完全二叉树）只是其中的一少部分。我们通过找到适度平衡的边界来构建BBST。那么什么是适度平衡呢？
- 高度渐进地不超过o（logn），即可称作适度平衡。
- 适度平衡的BST，也称作平衡二叉树（BBST）
可以证明，AVL或者红黑树等的高度，都可以在渐进意义上不超过log(n)。后面我们会慢慢分析。
我们的数据不是永恒不变的，树也一样，我们会有插入和删除操作，来改变其结构。如何在插入或者删除节点时，使BBST不离开这种适度平衡的状态呢？在聊这个问题前，我们先来聊两个知识点：
- 歧义性与等价转换
- 基本等价转换操作
歧义性与等价转换
中序序列的歧义性，是指两个树的结构不同，但有可能中序序列是一样的。中序序列的歧义性会导致在做树的重建时可能需要一些额外标识数据，才能构建出两棵相同的树，这在其他算法中可能会是一个头疼的问题。如下图所示，由一个中序序列（1，2，3）构建的两个树。
虽然在其他算法中可能会带来不少麻烦，但在BST或者BBST中，中序序列的歧义性为我们带来了遍历性。例如上篇文章我们通过交换两个节点的位置，将节点从双分支转换为单分支，进而降低删除对树结构所造成的影响。
我们可以根据歧义性去更改树的结构，而不影响整体的顺序性，对树做等价转换。我们可以通过歧义性，推断出等价转换的两个特点：
- 上下可变：垂直方向的自由度，联结关系不尽相同，承袭关系可能颠倒
- 左右不能乱：中序遍历序列完全相同，全局单调
其实所有的等价变换，都可以通过一系列的基本变换操作来维持。我们来看两个最常用的基本操作：Zig/Zag。
基本变换操作—Zig/Zag
在很多算法的资料中都会用到两种基本操作：Zig/Zag，也有的称之为左旋/右旋，但基本思想是一样的。
- Zig将节点按顺指针方向旋转
- Zag将节点按逆时针方向旋转
Zig/右旋
如上图所示，对v节点做Zig操作，即Zig(v)后的结果。中序遍历序列是没有任何改变的。
Zag/左旋
如上图所示，对v节点做Zag操作，即Zag(v)后的结果。中序遍历序列是没有任何改变的。
重平衡
如上图所示，在经历插入/删除操作后，BBST可能会转化为非BBST。但我们能通过一系列的操作将其转换为BBST，这个过程我们称之为重平衡。
虽然至今我们还没有涉及到重平衡的算法，但通过中序遍历的歧义性和等价变换，为这种设想带来了希望。但我们对重平衡还是有一些要求的，例如：
- 局部性：最好是能局部变动，而不影响整棵树
- 累计需要执行的操作数不要过多，如果操作数过多，可能树又退化成了List
通过这两个要求，我们可以控制总体的时间和操作数。
总结
所以所有BBST的实现，无非是在基于以下准则：
- 如何界定适度平衡的标准
- 一套满足重平衡的技巧和算法
AVL和红黑树都是增加了一些规则，来让树保持适度平衡，而且有一套满足自己规则的重平衡算法。那么他们之间又有什么区别呢？
若有收获，就点个赞吧
0 人点赞
