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