Cho một dãy gồm n số nguyên, hãy cài đặt dãy đó vào cây nhị phân tìm kiếm bằng cách sau, phần tử đầu tiên được chọn làm gốc, các phần tử tiếp theo được chèn và cây nhị phần theo cách: node con bên trái luôn nhỏ hơn node cha, node con bên phải luôn lớn hơn học bằng node cha.

Hãy biến đổi cây đó thành cây AVL. Hãy đưa ra bậc của cây đó.

Ví dụ:

• Test mẫu 1:
   

  Input	Output
  7 1 2 3 4 5 6 7	2

  
  Với a = [1, 2, 3, 4, 5, 6, 7] thì kết quả là 2.
  Cây nhị phân tìm kiếm ban đầu có bậc 6:
  
  
  Cây nhị phân sau khi biến đổi thành cây AVL có bậc là 2:
  
  

Lý thuyết.

Với những cây nhị phân tìm kiếm, nhiều cây sẽ rơi vào trường hợp rất xấu, trường hợp xấu nhất là tất cả các node cha chỉ có một node con, việc tìm kiếm trên cây này có ĐPT là O(n), lúc đó cây này không khác biệt mấy so với một danh sách liên kết.

Để tránh trường hợp trên chúng ta phải biết những cách xoay cây ở trong cây nhị phân tìm kiếm.

Phần này cần khả năng ghi nhớ cũng như trí tưởng tượng của các bạn.

Kỹ thuật xoay phải.

Kỹ thuật này thường áp dụng cho những cây nhị phần tìm kiếm bị lệch về bên trái (độ cao của cây con trái lớn hơn độ của của cây con phải).

Với cách xoay này ta cần quan tâm tới node gốc (A) cây con bên trái (B) và cây con bên phải của cây con bên trái (D).

Cách xoay:

• Biến đổi node B thành node gốc, node gốc (A) thành cây con bên phải của B.

• Nếu như trên hình thi node B có tới 3 cây con, sai quy tắc của cây nhị phân, nên ta cần chuyển node D thành node con trái của A.
  (lưu ý là 2 hoạt động trên diễn ra cùng lúc nên cần phải thêm một số node tạm).
• 

Ví dụ cụ thể:

Xoay cách xoay phải node trên:

Gán code node tạm A, B, D vào các vị trí sau:

Đầu tiên gán cây con bên trái của A thành D.

Gán cây con bên phải của B thành A:

Cây sau khi xoay là:

Code mẫu C++:

node *turnRight(node *a){
	node *b = a->left;
	node *d = b->right;
	a->left = d;
	b->right = a;
	return b;
}

Kỹ thuật xoay trái.

Kỹ thuật này thường áp dụng cho những cây nhị phần tìm kiếm bị lệch về bên phải(độ cao của cây con phải lớn hơn độ của của cây con trái).

Với cách xoay này ta hoàn toàn làm ngược lại cách xoay trái.

Với cách xoay này ta cần quan tâm tới node gốc (A) cây con bên trái (B) và cây con bên phải của cây con bên trái (C).

Cách xoay:

• Gán node trái của B bằng A:

• Gán node con bên phải của A bằng C:

Code mẫu C++:

node *turnLeft(node *a){
	node *b = a->right;
	node *c = b->left;
	a->right = c;
	b->left = a;
	return b;
}

Cách trường hợp xử lý cần bằng để thành cây AVL:

Có 4 trường hợp lệch trong cây nhị phân tìm kiếm:

• Lệch trái - trái:
• Lệch trái - phải:
• Lệch phải - phải:
• Lệch phải  - trái:

Mình sẽ hướng dẫn các bạn về xử lý 2 cách lệch là trái - trái và trái phải, hai cách còn lại tương tự.

Xử lý lệch trái - trái:

Lệch trái - trái có nghĩa là node cha có độ cao của cây con bên trái lớn hơn cây con bên phải, và đối với cây con bên trái thì độ cao của cây con trái cũng lớn hơn cây con phải.

Ví dụ cụ thể dưới đây:

Với những trường hợp lệch trái - trái, ta xử lý rất đơn giản, chỉ cần xoay phải cây là được.

Xử lý lệch trái - phải:

Lệch trái - phải có nghĩa là node cha có độ cao của cây con bên trái lớn hơn cây con bên phải, và đối với cây con bên trái thì độ cao của cây con phải lớn hơn cây con trái.

Ví dụ dưới đây:

Với trường hợp lệnh trái - phải, ta phải thực hiện 2 phép xoay:

• Xoay trái trái ở cây con bên trái.
• Xoay phải cây.

Hình ảnh sau khi xoay trái cây con bên trái:

Hình ảnh sau khi xoay phải cây:

Hướng dẫn bài tập.

Code mẫu hàm biến đội cây nhị phần tìm kiếm thành cây AVL.

node *updateTreeAvl(node *t){
	if (abs(treeLevel(t->left) - treeLevel(t->right)) > 1){
		if (treeLevel(t->left) > treeLevel(t->right)){
			node *p = t->left;
			if (treeLevel(p->left) >= treeLevel(p->right)){
				t = turnRight(t);
			} else{
				t->left = turnLeft(t->left);
				t = turnRight(t);
			}
		} else {
			node *p = t->right;
			if (treeLevel(p->right) >= treeLevel(p->left)){
				t = turnLeft(t);
			} else{
				t->right = turnRight(t->right);
				t = turnLeft(t);
			
			}
		}	
	}
	if (t->left != NULL) t->left = updateTreeAvl(t->left);
	if (t->right != NULL) t->right = updateTreeAvl(t->right);
	return t;
}

Code mẫu:

Ngôn ngữ C++:

#include<iostream>
#include<math.h>

using namespace std;

struct node{
	int data;
	node *left;
	node *right;
};
node *insert(node *t, int x){
	if (t == NULL){
		node *temp = new node;
		temp->data =x;
		temp->left = NULL;
		temp->right = NULL;
		return temp;
	} else{
		if (x < t->data){
			t->left = insert(t->left, x);
		} else{
			t->right = insert(t->right, x);
		}
	}
	
}
int treeLevel(node *t){
	if (t == NULL) return -1;
	return 1 + max(treeLevel(t->left), treeLevel(t->right));
}
bool checkAvl(node *t){
	if (t == NULL) 	return true;
	if (abs(treeLevel(t->left) - treeLevel(t->right)) > 1) return false;
	return checkAvl(t->left) && checkAvl(t->right);
}
node *turnRight(node *a){
	node *b = a->left;
	node *d = b->right;
	a->left = d;
	b->right = a;
	return b;
}
node *turnLeft(node *a){
	node *b = a->right;
	node *c = b->left;
	a->right = c;
	b->left = a;
	return b;
}
void printTree(node *t){
	if (t != NULL){
		printTree(t->left);
		cout << t->data << " ";
		if (t->left != NULL) cout <<t->left->data << " ";
		if (t->right != NULL) cout << t->right->data << " ";
		cout << endl;
		printTree(t->right);
	}
}
node *updateTreeAvl(node *t){
	if (abs(treeLevel(t->left) - treeLevel(t->right)) > 1){
		if (treeLevel(t->left) > treeLevel(t->right)){
			node *p = t->left;
			if (treeLevel(p->left) >= treeLevel(p->right)){
				t = turnRight(t);
			} else{
				t->left = turnLeft(t->left);
				t = turnRight(t);
			}
		} else {
			node *p = t->right;
			if (treeLevel(p->right) >= treeLevel(p->left)){
				t = turnLeft(t);
			} else{
				t->right = turnRight(t->right);
				t = turnLeft(t);
			
			}
		}	
	}
	if (t->left != NULL) t->left = updateTreeAvl(t->left);
	if (t->right != NULL) t->right = updateTreeAvl(t->right);
	return t;
}
int main(){
	int n, temp;
	cin >> n;
	node * t = NULL;
	for (int i = 0; i < n; i++){
		cin >> temp;
		t = insert(t, temp);
	}
	while(!checkAvl(t)){
		t = updateTreeAvl(t);		
	}
	cout << treeLevel(t);
	return 0;
}