avl.cpp

Bài viết đang được chỉnh sửa.

Bài toán

Xây dựng cấu trúc cây cân bằng

Độ phức tạp

chèn : logn

xóa : logn

#include <stdio.h>

#define then

int cnt = 0;

int abs(int a) { return a > 0 ? a : -a; }

int max(int a, int b) { return a > b ? a : b; }

class node_t {

   public:

    int value, id;

    node_t *ll, *rr, *pp;

    node_t(int _value) {

        value = _value;

        id = ++cnt;

        ll = rr = pp = 0;

    }

    node_t() { value = 9999999; }

    bool operator<(const node_t rhs) const { return value < rhs.value; }

    int llHeight();

    int rrHeight();

    int height();

    bool rightMore() { return rrHeight() > llHeight(); }

    bool leftMore() { return llHeight() > rrHeight(); }

    bool nonAvl() { return abs(rrHeight() - llHeight()) >= 2; }

    void add(node_t* U);

    void rem(node_t* U);

    void rotate();

    void push(node_t* U);

    void show();

};

int node_t::llHeight() {

    if (ll)

        return ll->height();

    else

        return 0;

}

int node_t::rrHeight() {

    if (rr)

        return rr->height();

    else

        return 0;

}

int node_t::height() { return max(llHeight(), rrHeight()) + 1; }

void node_t::add(node_t* U) {

    if (U == NULL) return;

    if ((*U) < (*this)) {

        if (ll) ll->pp = 0;

        ll = U;

    } else {

        if (rr) rr->pp = 0;

        rr = U;

    }

    if (U->pp) U->pp->rem(U);

    U->pp = this;

}

void node_t::rem(node_t* U) {

    if (U == NULL) return;

    if (ll == U)

        ll = 0;

    else

        rr = 0;

    U->pp = 0;

}

void node_t::rotate() {

    node_t *ch = 0, *gc = 0;  // child and grandchild

    if (rightMore()) {

        if (rr) gc = rr->ll;

        ch = rr;

    } else {

        if (ll) gc = ll->rr;

        ch = ll;

    }

    pp->add(ch);

    this->add(gc);

    ch->add(this);

}

void node_t::push(node_t* U) {

    if ((*U) < (*this))

        then if (ll == NULL) {

            ll = U;

            U->pp = this;

        }

    else

        ll->push(U);

    else if (rr == NULL) {

        rr = U;

        U->pp = this;

    }

    else rr->push(U);

    if (id == 0) return;

    if (nonAvl()) {

        printf("nonAvl at %d\n", id);

        if (leftMore())

            then {

                if (ll->rightMore()) ll->rotate();

            }

        else {

            if (rr->leftMore()) rr->rotate();

        }

        rotate();

    }

}

void node_t::show() {

    printf("(");

    if (ll) ll->show();

    printf("%d", value);

    if (rr) rr->show();

    printf(")");

}

/// Containers

node_t tr;

int main() {

    int p, q;

    for (;;) {

        scanf("%d", &q);

        tr.push(new node_t(q));

        tr.show();

        printf("\n");

    }

}

Nhận xét