别，WX大牛会发飙的。

回复 80楼 UserYuH

我想看看  rofor  写的Trie
拿来当作模板背背也不错的

大家都这么期待了,我看rofor不拿出一段code就真的说不过去了.
 
无论怎么样WX,Bule,Star总是给出了代码的.

我是来浇油的..

稍微看了你的code , 你这也是树阿。。。。在处理size的时候也有问题，Maintain的时候也有问题。用数组简化了很多操作，浪费了很多空间。

LS显然不懂竞赛之道。

回复 85楼 StarWing83

你能告诉我下面这句为什么那么写么？我实在是看不懂，请指教。(void)(0)? (void)(1)?
(void)(scanf("%d", &n) == 1);

回复 84楼 wxjeacen
多谢提醒，天杀的NOCOW上面的代码居然写了一句。。。if flag == False then...，我没仔细看就写代码了，结果弄反了状态标记。下面的代码是按照rofer的提示，合并了对称的过程写下的代码。
另：竞赛编程不是实际的商业代码编写。它对程序的速度和正确性要求高，而对其余的（健壮性，可扩展性）没有要求，因此怎么写着方便怎么写着快就怎么写，很多ACMer都是直接拿数组当静态树用的。

#include <stdio.h>
#include <string.h>
#define N 10001
char str[N][201], count[N];
int left[N] = {0}, right[N] = {0}, size[N] = {0};
int root = 0, last = 0;
void sbt_rotate(int *t, int *left, int *right)
{
    int k = right[*t];
    right[*t] = left[k];
    left[k] = *t;
    size[k] = size[*t];
    size[*t] = size[left[*t]] + size[right[*t]];
    *t = k;
}
void sbt_maintain(int *t, int *left, int *right)
{
    if (size[left[left[*t]]] > size[right[*t]])
        sbt_rotate(t, right, left);
    else if (size[right[left[*t]]] > size[right[*t]])
    {
        sbt_rotate(&left[*t], left, right);
        sbt_rotate(t, right, left);
    }
    else return;
    sbt_maintain(&left[*t], left, right);
    sbt_maintain(&right[*t], right, left);
    sbt_maintain(t, left, right);
    sbt_maintain(t, right, left);
}
int sbt_search(int t, char *s)
{
    int res;
    if (t == 0)
        return 0;
    if ((res = strcmp(s, str[t])) == 0)
        return t;
    return sbt_search(res < 0 ? left[t] : right[t], s);
}
int sbt_insert(int *t, char *s)
{
    int ret, res;
    if (*t == 0)
    {
        strcpy(str[++last], s);
        *t = last;
        count[*t] = 1;
        return *t;
    }
    ++size[*t];
    ret = sbt_insert((res = strcmp(s, str[*t]) < 0) ?
            &left[*t] : &right[*t], s);
    res ? sbt_maintain(t, left, right) : sbt_maintain(t, right, left);
    return ret;
}
int sbt_remove(int *t, char *s)
{
    int cnt = 0, res;
    if (*t != 0)
    {
        if ((res = strcmp(s, str[*t])) == 0)
        {
            *t = size[left[*t]] > size[right[*t]] ?
                left[*t] : right[*t];
            ++cnt;
        }
        cnt += sbt_remove(&left[*t], s);
        cnt += sbt_remove(&right[*t], s);
    }
    return cnt;
}
int main(void)
{
    int n, ret;
    ret = scanf("%d", &n);
    while (n--)
    {
        ret = scanf("%s", *str);
        if ((ret = sbt_search(root, *str)) != 0)
            ++count[ret];
        else
            sbt_insert(&root, *str);
    }
    for (n = 1; n <= last; ++n)
        printf("%s %d\n", str[n], count[n]);
    return 0;
}

帮忙看看现在还有没有问题。

慢着……SBT的delete太难写了……我找找资料去，上面代码的sbt_remove函数是错的= =

- -好像如果要删除，就必须要一个parent数组，否则就必须重复遍历整颗树。不写删除了，反正用不上。删除的方法是，如果被删掉的子女有前驱或者后继，那么可以保证他们最多只有一个子女，因此用这个前驱后者后继代替当前节点，就可以使用普通的删除方法了。
wx的方法还是很巧妙的。如果发现有两个子女，则继续通过在右分支查找这个key来找后继，因为这时其实是已经找到了key的，因此可以确定它的子女全部大于等于这个key，而又在找不到的时候，返回最接近的一个，因此返回的就是它的后继，这样就用不着parent数组以及重新遍历整棵树来寻找后继了。唯一的问题是，如果树中没有这个key，那么可能会删错一个叶子……这个恐怕只能使用标记参数的方法解决了。

恩，其实单纯在删除的时候，是可以直接找到后继的， 不需要parent数组来寻找后继（也许在单纯查找后继的时候就需要了），下面的代码是更新过的。效率应该不如wx的（毕竟可能会反复遍历一个区域），不过应该可以满足“删除所有key匹配的节点”的要求，如果只要求删一个，可以只改改wx的。

#include <stdio.h>
#include <string.h>
#define N 10001
char str[N][201], count[N];
int left[N] = {0}, right[N] = {0}, size[N] = {0};
int root = 0, last = 0;
void sbt_rotate(int *t, int *left, int *right)
{
    int k = right[*t];
    right[*t] = left[k];
    left[k] = *t;
    size[k] = size[*t];
    size[*t] = size[left[*t]] + size[right[*t]];
    *t = k;
}
void sbt_maintain(int *t, int *left, int *right)
{
    int is_left;
    if ((is_left = size[left[left[*t]]] > size[right[*t]])
            || size[right[left[*t]]] > size[right[*t]])
    {
        if (!is_left)
            sbt_rotate(&left[*t], left, right);
        sbt_rotate(t, right, left);
        sbt_maintain(&left[*t], left, right);
        sbt_maintain(&right[*t], right, left);
        sbt_maintain(t, left, right);
        sbt_maintain(t, right, left);
    }
}
int sbt_search(int t, char *s)
{
    int res;
    if (t == 0)
        return 0;
    if ((res = strcmp(s, str[t])) == 0)
        return t;
    return sbt_search(res < 0 ? left[t] : right[t], s);
}
int sbt_insert(int *t, char *s)
{
    int ret, res;
    if (*t == 0)
    {
        strcpy(str[++last], s);
        *t = last;
        count[*t] = 1;
        return *t;
    }
    ++size[*t];
    ret = sbt_insert((res = strcmp(s, str[*t]) < 0) ?
            &left[*t] : &right[*t], s);
    res ? sbt_maintain(t, left, right) : sbt_maintain(t, right, left);
    return ret;
}
int sbt_remove(int *t, char *s)
{
    int cnt = 0, res = 1;
    if (*t != 0)
    {
        cnt += sbt_remove(&left[*t], s);
        cnt += sbt_remove(&right[*t], s);
        if ((res = strcmp(s, str[*t])) == 0)
        {
            if (left[*t] == 0 || right[*t] == 0)
                *t = left[*t] == 0 ? right[*t] : left[*t];
            else
            {
                int *succ = &right[*t];
                while (left[*succ] != 0)
                    succ = &left[*succ];
                strcpy(str[*t], str[*succ]);
                *succ = right[*succ];
            }
        }
        size[*t] -= cnt;
    }
    return cnt + (res == 0);
}
int main(void)
{
    int n, ret;
    ret = scanf("%d", &n);
    while (n--)
    {
        ret = scanf("%s", *str);
        if ((ret = sbt_search(root, *str)) != 0)
            ++count[ret];
        else
            sbt_insert(&root, *str);
    }
    for (n = 1; n <= last; ++n)
        printf("%s %d\n", str[n], count[n]);
    return 0;
}