普通二叉搜索树，Treap，TODO

二叉搜索树 && 平衡二叉树

二叉搜索树用于动态维护一个有序序列。

普通二叉搜索树

下面介绍一些二叉搜索树的基本操作。

创建

思来想去，还是有必要先讲一下二叉搜索树的创建。

最最朴素的创建就是置根节点为空，而有过一定思考之后的做法可能是最开始建立最小结点和最大结点这两个哨兵结点，这样做插入操作就不用特别处理整棵树为空的情况了（不过，哨兵结点要保证其确实会是最大和最小的，不然会影响正确性）。

遍历

对于二叉搜索树来说，我们关心它的前序遍历，中序遍历，后序遍历以及层次遍历。对于前三种遍历，我们可以使用递归或者非递归的方式进行实现。这部分内容蛮基础和重要的，笔试面试的时候经常出现，但竞赛中似乎没见过太多次，这导致我对这些基础内容的掌握一般。

TODO

插入

二叉搜索树的插入需要保证其本身应该遵守的序关系，假设当前结点为p，要插入的值为x：

• 如果p是空，则创建一个新的结点，其值为x，并维护好新结点与父亲节点的关系。
• 如果p不为空
  • 如果x == p.value ，那么直接增加该结点的重复次数即可。
  • 如果x < p.value，则要递归地插入到左子树中，即ins(p.left, x)
  • 如果x > p.value，则要递归地插入到右子树中，即ins(p.right, x)

插入结束之后，可能需要自下而上更新信息，比如子树大小等信息。

在实现上，对于p为空的情况，一个优雅的处理方式是传递结点参数时传递结点的引用或者指针，这样在p为空的时候，创建新结点时直接用p来指向新的结点，那么新的结点和父亲之间的关系就自然建立了。另外多说一句，传递引用的话在旋转调整树的形态的时候也会很方便。

代码模板（使用内存池的方式进行实现）：

void ins(int &p, int x) {
    if (!p) {
        p = newNode(x);
    } else if (x == node[p].value) {
        node[p].cnt++;
    } else if (x < node[p].value) {
        ins(node[p].l, x); 
        // 如果是平衡树，此处可能会有一些树形态的调整操作
    } else {
        ins(node[p].r, x);
    }
    // 自下而上更新信息,根据题意去实现相应的pushup函数即可
    pushup(p);
}

删除

个人认为删除操作是所有操作中最复杂的一个操作，需要考虑的情况比较多，并且删除的实现方式很多。

二叉搜索树上的删除的总体思路是这样的：首先需要找到要删除的结点，然后我们要分情况讨论该怎么删除该结点。

其中一个思路是这样的：

• 利用二叉搜索树的性质，递归查找要删除的结点，直到找到或者最终没找到
• 如果上一步找到了，那么要考虑下面几种情况：
  • 如果当前结点重复次数大于1，则减小该结点的重复次数即可
  • 否则，需要讨论当前结点的左右子树的情况
    • 如果左右子树都为空，则直接将当前结点变成空即可
    • 如果只有左子树为空，则直接让当前结点变成它的右儿子
    • 如果只有右子树为空，则直接让当前结点变成它的左儿子
    • 如果都不为空，则可以根据自己的爱好，将当前结点左旋或者右旋，然后递归删除左儿子或者右儿子
• 自下而上更新树的信息。

当然，对于删除非叶子结点，其实可以通过循环找左子树中的最大的结点或者右子树中最小的结点（必然是一个叶子结点），然后交换当前结点以及刚找到的那个结点，最后递归下去删除它就好了。算法本身和上面提供的思路一样，只是实现上一个是递归一个是循环，一个旋转多次另一个只交换一次罢了。

代码模板：

void del(int &p, int x) {
    if (!p) return;
    else if (node[p].key == x) {
        if (node[p].cnt > 1) {
            node[p].cnt--;
        } else if (node[p].l && node[p].r) {
            // 左旋还是右旋可以自行决定
            // 平衡树中根据调整策略的不同而选择不同的旋转方法
            zig(p); // 右旋
            del(node[p].r, x);
            // zag(p); // 左旋
            // del(node[p].l, x);
        } else if (node[p].l) {
            p = node[p].l;
        } else if (node[p].r) {
            p = node[p].r;
        } else {
            p = 0;
        }
    } else if (x < node[p].key) {
        del(node[p].l, x);
    } else {
        del(node[p].r, x);
    }
    // 自下而上更新信息
    pushup(p);
}

查找前驱和后继

这个就是比较简单的递归地去做了，注意考虑等于的情况到底归到哪边，实在不行就单独写等于的情况。

查找前驱：

• 如果x <= p.value，则查左子树
• 如果x > p.value，则查右子树，返回右子树递归查找结果和当前结点中较大的那个

查找后继：

• 如果x < p.value，则查左子树，返回当前结点和左子树递归查找结果中较小的那个
• 如果x >= p.value，则查右子树

插入，删除，找前驱和后继，找最大最小值，查排名，查排名为rank的结点

代码模板：

int getPrev(int &p, int x) {
    if (!p) return -INF;
    if (x <= node[p].key) {
        return getPrev(node[p].l, x);
    } else {
        return max(node[p].key, getPrev(node[p].r, x));
    }
}

int getNext(int &p, int x) {
    if (!p) return INF;
    if (x < node[p].key) {
        return min(node[p].key, getNext(node[p].l, x));
    } else {
        return getNext(node[p].r, x);
    }
}

旋转

旋转操作可以在不会破坏二叉搜索树的序的性质的情况下改变树的形态，这意味着我们可以在任何时候对树中某个结点做旋转操作。当然，无目标的旋转一般是没有意义的，但有目的地在“合适的时候”做树的旋转，可以减小树的深度，使之变得更平衡。

旋转操作口诀：左旋拎右左挂右，右旋拎左右挂左（鸣谢不分解的AgOH）

意思是：如果要将一个结点右旋，那么你需要把这个节点的左子树“拎起来”，交换该结点和左儿子的父子关系，然后把原来的这个左子树的右子树作为该结点的左子树（因为拎起来的时候该结点的左儿子变成了父亲，该结点没有左儿子了）。

代码模板：

void zig(int &p) { // 右旋
    int q = node[p].l;
    node[p].l = node[q].r;
    node[q].r = p;
    p = q;
    // 一般旋转完了之后需要更新一下信息
    pushup(node[p].r);
    pushup(p);
}

void zag(int &p) { // 左旋
    int q = node[p].r;
    node[p].r = node[q].l;
    node[q].l = p;
    p = q;
    pushup(node[p].l);
    pushup(p);
}

查找排名为k的结点

对于二叉搜索树来说，由于其拥有良好的顺序的关系，所以可以借助这个性质来快速查询第k大的结点。

基本思路是这样的：

假设当前结点为p：

• 如果p的左子树的大小 >= k，说明待查的结点在左子树中，所以递归查左子树中的第k大
• 在不满足上一条时，如果p的左子树大小 + p的重复次数 >= k，说明待查的结点就是当前结点
• 在不满足上一条时，说明待查的结点在右边，所以需要查询右子树中的第k - p.l.size - p.cnt大的结点。

代码模板：

int get_node_by_rank(int &p, int k) {
    if (node[node[p].l].size >= k) {
        return get_node_by_rank(node[p].l, k);
    } else if (node[node[p].l].size + node[p].cnt >= k) {
        return node[p].value;
    } else {
        return get_node_by_rank(node[p].r, k - node[node[p].l].size - node[p].cnt);
    }
}

在调用这个函数的时候，要注意自己最开始是否设置了哨兵结点。如果设置了，那么查询的时候应该是查询第k + 1大的结点。

查找某个值x在树中的排名

利用二叉搜索树的性质进行查找：

• 如果当前结点的值等于x，那么返回左子树大小 + 1
• 如果当前结点的值大于x，那么递归在左子树中查找排名
• 如果当前结点的值小于x，那么递归在右子树中查找x的排名，并最终返回左子树大小 + 当前结点重复数 + 右子树中的排名

代码模板：

int getRankByKey(int &p, int x) {
    if (x == node[p].key) {
        return node[node[p].l].size + 1;
    } else if (x < node[p].key) {
        return getRankByKey(node[p].l, x); 
    } else {
        return node[node[p].l].size + node[p].cnt + getRankByKey(node[p].r, x);
    }
}

在调用这个函数的时候，要注意自己最开始是否设置了哨兵结点，如果设置了 ，那么最后查到的排名应该减去1。

平衡二叉树

对于各种不同的平衡树来说，其不同点不在于二叉树通用的操作（增删改查与旋转），而在于维持树的平衡性的算法。

单旋Treap

Treap是最简单的且效率较高的一种平衡二叉树。由于其调整树形态的方式是单旋，所以在代码上和普通二叉树的代码实现相差无几，且非常好理解，属于入门级平衡树之一（虽然我的入门平衡树是AVL树）。

保持平衡性的方法

Treap维持平衡的想法是：结点中不仅存储我们关心的key值，还在结点中开一个域，存储一个叫做value的随机数。在结构上，我们要保证Treap是一个二叉搜索树，在此基础上还要让其关于value值是一个大根或者小根堆。同时满足二者是不矛盾的，因为树的旋转是不破坏二叉搜索树性质的，所以我们可以先插入或者删除结点使之成为二叉搜索树，然后进行树旋转来使得其又是关于value的一个堆。在同时满足这两个条件的情况下，会出现什么样的事情呐？由于value是随机数，所以即便输入的key有序，最终的效果也和随机打乱一样，所以Treap是期望平衡的。

具体来说，Treap是这样保持平衡的：在插入时，从ins函数回溯上来之后，判断当前结点p和刚刚操作过的那棵子树的value做比较，如果不满足堆的性质，就做相应的旋转；或者在删除操作之前，如果两个子树都存在，则把大的儿子旋转上去，然后递归删除。所以，Treap相比普通的二叉搜索树，代码上总共也就多10行左右，仅仅是在ins和del函数中增加简单的旋转操作即可。

代码模板

int newNode(int x) { // 使用内存池实现时创建一个新的结点的方法
    node[++idx].key = x;
    node[idx].value = rand();
    node[idx].l = node[idx].r = 0;
    node[idx].size = node[idx].cnt = 1;
    return idx;
}

void ins(int &p, int x) {
    if (!p) {
        p = newNode(x);
    } else if (x == node[p].key) {
        node[p].cnt++;
        node[p].size++;
        return;
    } else if (x < node[p].key) {
        ins(node[p].l, x);
        if (node[node[p].l].value > node[p].value) { // 比普通BST多的代码
            zig(p);
        } 
    } else {
        ins(node[p].r, x);
        if (node[node[p].r].value > node[p].value) { // 比普通BST多的代码
            zag(p);
        }
    }
    pushup(p);
} 

void del(int &p, int x) {
    if (!p) return;
    else if (node[p].key == x) {
        if (node[p].cnt > 1) {
            node[p].cnt--;
        } else if (node[p].l && node[p].r) {
            if (node[node[p].l].value > node[node[p].r].value) { // 比普通BST多的代码
                zig(p);
                del(node[p].r, x);
            } else {
                zag(p);
                del(node[p].l, x);
            }
        } else if (node[p].l) {
            p = node[p].l;
        } else if (node[p].r) {
            p = node[p].r;
        } else {
            p = 0;
        }
    } else if (x < node[p].key) {
        del(node[p].l, x);
    } else {
        del(node[p].r, x);
    }

    pushup(p);
}