CTDL và giải thuật – Đếm số lượng phần tử có giá trị bằng x trong cây

Posted on by mtoplistChuyên mục:Top List

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. Nhập vào một số nguyên x, hãy đếm số lượng phần tử có giá trị bằng x trong cây đó.

Ví dụ:

  • Test mẫu 1:
     

    Input
    Output

    6
    2 1 2 3 7 2
    2

    2

    Với a = [2, 1, 2, 3, 7, 2] và x = 2 thì kết quả mong muốn là 2.
     

  • Test mẫu 2:
     

    Input
    Output

    5
    1 2 3 4 5
    10

    0

    Với a = [1, 2, 3, 4, 5] và x = 10 thì kết quả mong muốn là 0.

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

Bài này có thể tìm kiếm bằng nhiều cách, nên đưa về cây AVL để tìm kiếm một cách nhanh chóng nhất.

Hàm tìm kiếm trong cây AVL:

int count(node *t, int x){
	if (t == NULL) return 0;
	if (t->data == x) return 1 + count(t->left, x) + count(t->right, x);
	else if (t->data < x) return count(t->right, x);
	return count(t->left, x);
}

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 count(node *t, int x){
	if (t == NULL) return 0;
	if (t->data == x) return 1 + count(t->left, x) + count(t->right, x);
	else if (t->data < x) return count(t->right, x);
	return count(t->left, x);
}
int main(){
	int n, x, 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);		
	}
	cin >> x;
	cout << count(t, x);
	return 0;
}

mtoplist