平衡树学习

童年如作业 · 2020-07-25 16:13:18 · 个人记录

Treap

左旋、右旋

左旋要求把子树根节点的右儿子提上来，代替根节点的位置，同时根节点成为原右儿子的左儿子。

因此要处理右儿子以及右儿子原来的左儿子。根据二叉查找树的定义可知：右儿子原来的左儿子绝对比原根节点大，但比原根节点右儿子小。以左儿子为根的子树同理。可表示为 \text{根节点} < \text{以根节点的右儿子的左儿子为根节点的子树的树中的任意一个节点} < \text{根节点的右儿子} 。

因此 右儿子原来的左儿子（子树）可变为左旋后根节点的右儿子 。

void Treap_Left_Rotate(Treap_Node *&a)
{
    Treap_Node *b=a->right;//b指向a（根节点）的右儿子（子树）
    a->right=b->left;//将a子树转化为b的左子树
    b->left=a;//给b的左子树赋值
    a=b;//传参
}

同理，

右旋要求把子树根节点的左儿子提上来，代替根节点的位置，同时根节点成为原左儿子的右儿子。

因此要处理左儿子以及左儿子原来的右儿子。根据二叉查找树的定义可知：左儿子原来的右儿子绝对比原根节点小，但比原根节点左儿子大。以右儿子为根的子树同理。可表示为 \text{根节点的左儿子} < \text{以根节点的左儿子的右儿子为根节点的子树的树中的任意一个节点} < \text{根节点} 。

因此 左儿子原来的右儿子（子树）可变为根节点右旋后的左儿子 。

void Treap_Right_Rotate(Treap_Node *&a)
{
    Treap_Node *b=a->left;//b指向a（根节点）的左儿子（子树）
    a->left=b->right;//将a子树转化为b的右子树
    b->right=a;//给b的右子树赋值
    a=b;//传参
}

平衡树学习

Treap

左旋、右旋

代码（P3369）

FHQ-Treap

代码（P3369, P6136）

AVL

代码（P3369, P6136）