SPOJ.COM - Thuật toán bài SDITSAVL - AVL Tree

Posted on June 7th, 2017

Đề bài:

Bài toán này là bài toán mở rộng (với một chút thay đổi) từ bài toán: SDITSBST. Trong bài toán này, bạn được đưa cho 2 loại query:

  • 1. Chèn một số nguyên x vào list
  • 2. Cho số x.

Hãy tìm số k biểu diễn chỉ số của số x trong list nếu như list được sắp xếp theo thứ tự tăng dần. Chú ý rằng: bài toán này chỉ số bắt đầu tính từ 1.

Như tên bài toán đã gợi ý, chúng ta sẽ sử dụng cây nhị phân cân bằng, một trong những ví dụ của cây nhị phân cân bằng là cây AVL

Đầu vào

Dòng đầu tiên là số nguyên Q: biểu diễn số query. Q dòng tiếp theo sẽ biểu diễn 1 trong 2 loại query với định dạng như sau:

1 x: chèn số nguyên x vào list

2 x: tìm chỉ số k của số nguyên x nếu như list được sắp xếp theo thứ tự tăng dần

Đầu ra

Với mỗi query loại 2, in ra kết quả số nguyên k nếu như số nguyên x tồn tại trong list. Ngược lại in ra dòng "Data tidak ada".

Ví dụ

Input:

10 
1 100 
1 74 
2 100 
2 70 
1 152 
1 21 
1 33 
2 100 
2 21 
2 1

Output:

2 
Data tidak ada 
4 
1 
Data tidak ada

Giải thích

Cho đến query thứ 3, list bao gồm {74, 100}. Vì vậy, bạn phải in ra 2 - chỉ số của số 100 trong list. Đến query thứ 4, list vẫn không thay đổi, vì 70 không có trong list nên kết quả sẽ là "Data tidak ada".

Đến 3 query cuối cùng, list bao gồm {21, 33, 74, 100, 152}. Vì vậy, kết quả cho query thứ 8, 9, 10 lần lượt là 4, 1, "Data tidak ada".

Ràng buộc

1 ≤ Q ≤ 200000

1 ≤ x ≤ 106

Đảm bảo rằng tất cả số nguyên chèn vào list là phân biệt.

Chú ý

Không đảm bảo rằng input sẽ là cây cân bằng. Bạn phải tự cân bằng cây.

Bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/SDITSAVL/

Phân tích

Bài này không có gì phải băn khoăn về cách giải, vì chúng ta sẽ dùng cây AVL. Vấn đề ở đây là cách cấu trúc mỗi node trong cây. Sau đây là cấu trúc mà mình đã làm:

struct Node {
  int x, height, numLeft, numRight;
  Node *left, *right;
};

Trong đó:

  • x: giá trị của số nguyên chèn vào
  • height: độ cao của node. Node lá sẽ có độ cao là 1. Độ cao của node cha là giá trị lớn nhất của độ cao hai node con.
  • numLeft: số node con, cháu,.. bên trái một node
  • numRight: số node con, cháu... bên phải một node

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

#include <iostream>
using namespace std;

int Q;
void insert(int x);
int  find(int x);
void init();

struct Node
{
	int x, height, numLeft, numRight;
	Node *left, *right;
};

Node *root;

int  height(Node *p);
void fixHeight(Node *p);
void fixNumLeft(Node *p);
void fixNumRight(Node *p);
int  balanceFactor(Node *p);

Node* initNode(int x);
Node* insert(Node *p, int x);
Node* findMin(Node *p);
Node* removeMin(Node *p);
Node* rotateLeft(Node *p);
Node* rotateRight(Node *p);
Node* balance(Node *p);
int   findOrder(Node *p, int x, int offset);

int main()
{
//	freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(false);

	init();
	cin >> Q;
	for(int q = 0; q < Q; q++)
	{
		int type, x, k;
		cin >> type >> x;
		switch (type)
		{
		case 1:
			insert(x);
			break;
		case 2:
			k = find(x);
			if(k < 0) cout << "Data tidak ada" << endl;
			else cout << k << endl;
			break;
		default:
			cout << "There is something wrong" << endl;
			break;
		}
	}
}

void init()
{
	root = 0;
}

void insert(int x)
{
	root = insert(root, x);
}

int  find(int x)
{
	return findOrder(root, x, 0);
}

int height(Node *p)
{
	return p ? p->height : 0;
}

void fixHeight(Node *p)
{
	int hr = height(p->right);
	int hl = height(p->left);
	p->height = (hr > hl ? hr : hl) + 1;
}

void fixNumLeft(Node *p)
{
	if(p->left) p->numLeft = p->left->numLeft + p->left->numRight + 1;
	else p->numLeft = 0;
}

void fixNumRight(Node *p)
{
	if(p->right) p->numRight = p->right->numLeft + p->right->numRight + 1;
	else p->numRight = 0;
}

int balanceFactor(Node *p)
{
	return height(p->right) - height(p->left);
}

Node* initNode(int x)
{
	Node* newNode = new Node;
	newNode->x = x;
	newNode->height = 1;
	newNode->numLeft = 0;
	newNode->numRight = 0;
	newNode->left = 0;
	newNode->right = 0;
	return newNode;
}

Node* insert(Node *p, int x)
{
	if(!p)
		return initNode(x);

	if(x < p->x)
	{
		p->left = insert(p->left, x);
		fixNumLeft(p);
	}
	else if(x > p->x)
	{
		p->right = insert(p->right, x);
		fixNumRight(p);
	}
	return balance(p);
}

Node* findMin(Node *p)
{
	if(!p) return 0;
	if(p->left == 0) return p;
	return findMin(p->left);
}

Node* removeMin(Node *p)
{
	if(!p) return 0;
	if(p->left == 0) return p->right;
	p->left = removeMin(p->left);
	return balance(p);
}

Node* rotateLeft(Node *p)
{
	Node *q = p->right;
	p->right = q->left;
	q->left = p;
	fixHeight(p);
	fixHeight(q);
	fixNumRight(p);
	fixNumLeft(q);
	return balance(q);
}

Node* rotateRight(Node *p)
{
	Node *q = p->left;
	p->left = q->right;
	q->right = p;
	fixHeight(p);
	fixHeight(q);
	fixNumLeft(p);
	fixNumRight(q);
	return balance(q);
}

Node* balance(Node *p)
{
	fixHeight(p);
	fixNumLeft(p);
	fixNumRight(p);

	if(balanceFactor(p) == 2)
	{
		if(balanceFactor(p->right) < 0)
			p->right = rotateRight(p->right);
		return rotateLeft(p);
	}

	if(balanceFactor(p) == -2)
	{
		if(balanceFactor(p->left) > 0)
			p->left = rotateLeft(p->left);
		return rotateRight(p);
	}

	return p;
}

int findOrder(Node *p, int x, int offset)
{
	if(!p) return -1;
	if(p->x == x) return offset + p->numLeft + 1;

	if(p->x > x)
		return findOrder(p->left, x, offset);

	if(p->x < x)
		return findOrder(p->right, x, offset + p->numLeft + 1);
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Spoj
Graph and Tree