在这4中情况当中，1和3是对称的，2和4也是对称的。所以我们只需要着重分析其中两种就可以了，另外两种可以通过对称性得到。
由于我们使用递归来维护树的平衡性的时候，是从底往上的。因此我们可以假设ABCDLR这六棵子树都是平衡的，这样可以简化我们的分析。我们假设我们现在有了一个函数叫做maintain，它可以将一棵不平衡的子树旋转到平衡状态。我们先假设已经有了这个函数，再去看看它里面需要实现哪些逻辑。
接下来我们来看看上面四种情况如果不满足的话，我们应该怎么处理。
情况1
情况1当中A.size > R.size，也就是A当中的节点比较多，为了能够趋近于平衡。我们将原子树右旋，得到：
我们右旋之后，A的层级向上提升了一层。我们观察一下旋转之后的结果，会发现R子树的平衡性得到了保持，没有被破坏，A子树本身就是平衡的。所以旋转之后，还有还有两个节点的平衡性没有保证。一个是T节点，一个是L节点。那么，我们递归调用maintain(T)和maintain(L)即可。
我们写成伪代码就是：
right_rotate(T)
maintain(T)
maintain(L)
情况2
下面我们来看情况2，也就是B.size > R.size的情况。和上面一种情况类似，由于B的节点比较多，我们希望能够把B往上提。但是B节点在内部，我们无论对L左旋还是右旋都
既然对T旋转不行，那么我们可以对L进行旋转啊，这样不就可以影响到B节点了吗？为了展示地更加清楚，我们把B子树的孩子节点也画出来。
接着我们对L进行左旋，这样可以把B往上提升一层，得到：
虽然我们把B往上提了一层，但是对于T子树而言，左重右轻的局面仍然没有改变。要想改变T的不平衡，我们还需要对T进行右旋，得到：
对于这个结果而言，除了L、T和B这三棵树而言，其他所有的子树都满足平衡了。所以我们按顺序维护L、T和B即可。
我们写成代码就是：
left_rotate(L)
right_rotate(T)
maintain(L)
maintain(T)
maintain(B)
情况3和情况1刚好相反，我们把左旋和右旋互换即可，情况4和情况2也一样。
所以我们可以写出所有的情况来了：
def maintain(t):
if t.left.left.size > t.right.size:
right_rotate(t)
maintain(t.right)
maintain(t)
elif t.left.right.size > t.right.size:
left_rotate(t.left)
right_rotate(t)
maintain(t.left)
maintain(t.right)
maintain(t)
elif t.right.right.size > t.left.size:
left_rotate(t)
maintain(t.left)
maintain(t)
else:
right_rotate(t.right)
left_rotate(t)
maintain(t.left)
maintain(t.right)
maintain(t)
这里的四种情况罗列出来当然就可以，但是有很多代码重复了，我们可以设置一个flag标记，表示我们判断的是左子树还是右子树。这样我们可以把一些情况归并在一起，让代码显得更加简洁：
def maintain(t, flag):
if flag:
if t.left.left.size > s.right.size:
right_rotate(t)
elif s.left.right.size > t.right.size:
left_rotate(t.left)
right_rotate(t)
else:
return
else:
if t.right.right.size > t.left.size:
left_rotate(t)
elif t.right.left.size > t.left.size:
right_rotate(t.right)
left_rotate(t)
else:
return
maintain(t.left, False)
maintain(t.right, True)
maintain(t, False)
maintain(t, True)
这里其实我们省略了maintain(t.left, True)和maintain(t.right, False)这两种情况，这两种情况我们稍微分析一下会发现其实已经被包含了。
我们搞清楚了这些之后，还有一个疑问没有解开，就是为什么旋转操作可以让二叉树趋向于平衡呢，而不是无穷无尽地旋转下去呢？
尽管我们已经知道了不会，但是还是想要来证明一下。我们以情况一举例，我们右旋之后的结果是：
我们对比一下旋转之前的结果，会发现T、R、C、D的高度增加1，而L和A的高度减小了1。由于A.size > R.size，A的size最小等于R.size + 1，也就刚好是T加上R子树的size。这两个部分一增一减互相抵消之后，至少还有L这个节点的深度减小了1。也就是说旋转之后的所有元素的深度和是在减小的，不仅是情况1如此，其他的情况也是一样。
既然深度和是在减小的，那么maintain这个操作就一定不是无限的。并且它也的确可以让树趋向于稳定，因为完美平衡的情况下所有元素的深度和才是最小的。
实现细节
到这里我们就已经把SBT的原理都讲解完了，但是还存在一些细节上的问题。由于我们是使用Python是引用语言，所以当我们在旋转的时候进行赋值只是指针之间改变了引用的目标， 并没有实际对原本的结构进行改变。
我们来看下刚才上面的伪代码：
def right_rotate(u):
ul = u.left
u.left = ul.right
ul.right = u
u = ul
由于我们把u的左孩子右旋，代替了u本来的位置。当我们执行u = ul的时候，只是u这个指针改变了指向的位置。至于原本的数据结构当中的内容，并没有发生变化。因为u、ul这些变量都是临时变量，都是拷贝出来的，我们随便更改，也不会影响类当中的值。
在C++当中我们可以传入引用，这样我们修改引用就是修改原值了。但是Python当中不行，想要解决这个问题，只有一种方法，就是对于每个节点我们都记录它父节点的位置。当我们旋转完了之后，我们需要去更新它父节点中储存的孩子节点的地址，这样的话，我们就不只是局部变量之间互相修改了，就真正落实到了数据结构上了。
我们以右旋为例：
def reset_child(self, node, child, left_or_right='left'):
"""
Since Python pass instance by reference, in order to rotate the node in tree, we need to reset the child of father node
Otherwise the modify won't be effective
"""
if node is None:
self.root = child
self.root.father = None
return
if left_or_right == 'left':
node.lchild = child
else:
node.rchild = child
if child is not None:
child.father = node
def rotate_right(self, node, left_or_right='left'):
"""
Right rotate operation of Treap.
Example:
D
/ \
A B
/ \
E C
After rotate:
A
/ \
E D
/ \
C B
"""
father = node.father
lchild = node.lchild
node.lchild = lchild.rchild
if lchild.rchild is not None:
lchild.rchild.father = node
lchild.rchild = node
node.father = lchild
# 要重新reset父节点的孩子节点，这样整个改动才是真的生效了。
self.reset_child(father, lchild, left_or_right)
# 更新节点买的size
node.size = node_size(node.lchild) + node_size(node.rchild) + 1
lchild.size = node_size(lchild.lchild) + node_size(lchild.rchild) + 1
return lchild
由于每个节点的孩子节点有两个，所以我们还需要一个变量来记录我们当前要改变的节点究竟是它父亲节点的左孩子还是右孩子，这样我们才能在reset的时候正确地修改。不仅是旋转如此，删除和添加也是一样的，我们都需要修改父节点当中的信息，否则我们修改来修改去，改的都只是局部变量而已。
另外一点是我们旋转之后还需要更新每个节点的size，这个逻辑如果忘记了，那么后面的maintain就无从谈起了。
最后我们思考一个问题，我们在什么情况下需要maintain操作呢，也就是什么情况下会破坏树的平衡性呢？其实很简单，就是当树中的元素数量发生改变的时候。无论是增多或者是减少都有可能破坏树的平衡。所以我们在完成了插入和删除之后都需要maintain一次树的平衡。
论文当中对于maintain这个操作还有详细的分析，可以证明maintain的均摊复杂度是，也就是常数级的操作，这也是为什么SBT运行效率高的原因。
论文的最后还附上了SBT和其他常用平衡树数据结构的比较，我们可以看出SBT无论是运行效率还是质量都是其中佼佼者。
最后，我们聊一聊SBT的实现。关于SBT这类复杂数据结构的实现还是C++要更方便一些，主要原因就是因为C++当中带有引用和指针的传递操作。我们可以在函数内部修改全局的值，而Python当中则不行。参数传递默认传递的是拷贝，我们在函数内部赋值并不会影响结果。所以如果使用Python实现会更加复杂一些，并且需要一些修改父节点的额外操作。
因此网上关于SBT的Python实现非常非常少，我有自信说我的代码目前是我能找到的实现得比较好的一个。相关代码很长，足足有五百多行，不适合放在文章当中。如果大家感兴趣，可以在公众号内回复SBT关键字进行获取。
今天的文章就到这里，衷心祝愿大家每天都有所收获。如果还喜欢今天的内容的话，请来一个三连支持吧~（点赞、关注、转发）