数据结构复习：二叉搜索树

template
 <class T, class Comp = std::less <T> >
class qtree {
public
:
    struct node {
        node(const T &t, node *p)
            : data(t), parent(p), lchild(0), rchild(0), left_size(0)
        {
        }

        T data;
        node *parent;
        node *lchild, *rchild;
        int
 left_size;
    };

    qtree()
        : __head(T(), 0), __size(0)
    {
    }

    node * add(const T &data)
    {
        node *p = &__head;
        while
 (1) {
            if
 (__less_than(data, p)) {
                p->left_size += 1;
                if
 (p->lchild) {
                    p = p->lchild;
                } else {
                    p->lchild = new
 node(data, p);
                    p = p->lchild;
                    break
;
                }
            } else {
                if
 (p->rchild) {
                    p = p->rchild;
                } else {
                    p->rchild = new
 node(data, p);
                    p = p->rchild;
                    break
;
                }
            }
        }
        ++__size;
        return
 p;
    }

    void
 remove(node *p)
    {
        if
 (p->lchild && p->rchild) {
            __swap_node(p, __min_node(p->rchild));
        }
        __increase_leaf(p, -1);
        node *q = __only_child(p);
        *__child_entry(p, p->parent) = q;
        if
 (q) {
            q->parent = p->parent;
        }
        --__size;
        delete
 p;
    }

    node * find(const T &data)
    {
        node *p = &__head;
        while
 (p) {
            if
 (__less_than(data, p)) {
                p = p->lchild;
            } else if
 (__less_than(p, data)) {
                p = p->rchild;
            } else {
                break
;
            }
        }
        return
 p;
    }

    node * at(int
 index)
    {
        node *p = __head.rchild;

        while
 (p) {
            if
 (index < p->left_size) {
                p = p->lchild;
            } else if
 (p->left_size < index) {
                index -= (p->left_size + 1);
                p = p->rchild;
            } else {
                break
;
            }
        }

        return
 p;
    }

    int
 size()
    {
        return
 __size;
    }
private
:
    bool
 __less_than(const T &data, const node *node)
    {
        if
 (node == &__head) return
 false;
        return
 Comp()(data, node->data);
    }

    bool
 __less_than(const node *node, const T &data)
    {
        if
 (node == &__head) return
 true
;
        return
 Comp()(node->data, data);
    }

    node ** __child_entry(node *p, node *q)
    {
        return
 q->lchild == p ? &q->lchild : &q->rchild;
    }

    void
 __swap_node(node *a, node *b)
    {
        *__child_entry(a, a->parent) = b;
        *__child_entry(b, b->parent) = a;
        std::swap(a->parent, b->parent);
        std::swap(a->lchild, b->lchild);
        std::swap(a->rchild, b->rchild);
        std::swap(a->left_size, b->left_size);
        if
 (a->lchild) {
            a->lchild->parent = a;
        }
        if
 (a->rchild) {
            a->rchild->parent = a;
        }
        if
 (b->lchild) {
            b->lchild->parent = b;
        }
        if
 (b->rchild) {
            b->rchild->parent = b;
        }
    }

    node * __min_node(node *p)
    {
        while
 (p->lchild) {
            p = p->lchild;
        }
        return
 p;
    }

    node * __max_node(node *p)
    {
        while
 (p->rchild) {
            p = p->rchild;
        }
        return
 p;
    }

    void
 __increase_leaf(node *p, int
 increment)
    {
        while
 (p->parent) {
            node *q = p->parent;
            if
 (p == q->lchild) {
                q->left_size += increment;
            }
            p = q;
        }
    }

    node * __only_child(node *p)
    {
        return
 p->lchild ? p->lchild : p->rchild;
    }

    node __head;
    int
 __size;
};