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 kiểm tra xem cây đó có phải là câu AVL nhị phân tìm kiếm hay không. (Xem thêm phần lý thuyết).

• Test mẫu 1:
   

  Input	Output
  7 4 7 2 1 3 2 5	true

  
  Với a = [4, 7, 2, 1, 3, 2, 5] thì kết quả mong muốn là true.
  Cách nhập dữ liệu:
   

  7
  4 7 2 1 3 2 5

  
  Hình ảnh của cây:
  
• Với a = [4, 7, 2, 1, 3, 2, 5, 2] thì kết quả mong muốn là false.
  Hình ảnh của cây:
  

Lý thuyết.

Giới thiệu cât AVL.

Hiệu suất trường hợp xấu nhất của cây tìm kiếm nhị phân (BST) gần với các giải thuật tìm kiếm tuyến tính, tức là Ο(n). Với dữ liệu thời gian thực, chúng ta không thể dự đoán mẫu dữ liệu và các tần số của nó. Vì thế, điều cần thiết phát sinh ở đây là để cân bằng cây tìm kiếm nhị phân đang tồn tại.

Cây AVL (viết tắt của tên các nhà phát minh Adelson, Velski và Landis) là cây tìm kiếm nhị phân có độ cân bằng cao. Cây AVL kiểm tra độ cao (bậc) của các cây con bên trái và cây con bên phải và bảo đảm rằng hiệu số giữa chúng là không lớn hơn 1. Hiệu số này được gọi là Balance Factor (Nhân tố cân bằng).

Hình ảnh ví dụ của cây AVL:

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

Cần kiếm trả độ cao của cây con trái và phải của một node, Nếu không có node nào có sự chệnh lệch độ cao giữa hai cây con vượt quá 1 thì cây đó là cây AVL.

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);
}
int main(){
	int n, temp;
	cin >> n;
	node * t = NULL;
	for (int i = 0; i < n; i++){
		cin >> temp;
		t = insert(t, temp);
	}
	cout << checkAvl(t) << endl;
	
	return 0;
}