Nạp chồng toán tử [] - binary search tree

Chào mọi người, cho mình hỏi ai đã từng làm nạp chồng toán tử [] trong cây nhị phân tìm kiếm chưa ạ? Chỉ cho mình với. Ví dụ:

A  5      6 8    2      3      4    (key)
   0.1    4.5    2.3    5.2    1.8  (data)

Bây giờ mình cần:

int x;
nếu x = key thì in ra A[x] = data;
còn x != key thì thông báo lỗi

Phần code của mình như sau:

class Tree {
private:
	struct node {
		int key;
		float data;
		node* left;
		node* right;
	};
	node* root;

BST bạn tạo key làm gì nhỉ, nó làm tốn thêm bộ nhớ mà không có lợi ích gì.

1 Like

ko có key làm sao truy cập theo key được :V :V

khai báo hàm vậy thôi :V

float operator[](int key) const;
2 Likes

Vì BST không có tính truy cập ngẫu nhiên nên overload [] không hợp lí lắm, nếu thêm key vào giống như bạn kia thì em thấy có lẽ hashtable sẽ hợp hơn

1 Like

container nào mà ko truy cập ngẫu nhiên được, có nên hay ko thôi =] Ví dụ linked list muốn truy cập ngẫu nhiên cũng ok nhưng mà nó O(n) =]

cây này ko cân bằng nên có lẽ ko nên, trường hợp tệ nhất nó như liniked list O(n). Nhưng đề yêu cầu thì viết thôi :V

cây có cân bằng thì truy cập ngẫu nhiên chỉ tốn O(logn) thôi, cũng được mà :V

2 Likes

Ý em là vậy đó, không nên thì không làm luôn

2 Likes

đề yêu cầu sao em ko làm được :V Viết cho hiểu cách nó tìm kiếm node trong cây nhị phân thế nào chứ xài thì xài thư viện chuẩn hay thư viện người khác viết cho chắc :V

3 Likes

Có lẽ là vậy cũng nên được chứ nhỉ :v

Ví dụ: bảng tần suất :smiley:

viết chắc cũng dễ mà =]

float operator[](int key) const {
    Node* node = findNodeWithKey(key, root);
    if (node) return node->data;
    throw ...;
}

Node* findNodeWithKey(int key, Node* node) {
    if (!node || node->key == key) return node;
    return findNodeWithKey(key, key < node->key ? node->left : node->right);
}
2 Likes

A post was merged into an existing topic: Topic lưu trữ các post off-topic - version 3

mình cảm ơn, để mình thử code xem sao

bạn xem chương trình này giúp mình với, hàm main giờ viết sao?

#include<iostream>
using namespace std;

class Tree {
private:
	struct node {
		int key;
		float data;
		node* left;
		node* right;
	};
	node* root;

	node* makeEmpty(node* t);
	node* insertprivate(int x, float y, node* t);
	node* findMin(node* t);
	node* removeprivate(int x, float y, node* t);
	void inorderprivate(node* t);
	node* findprivate(node* t, int x);
	int countprivate(node* t);
	node* findNodeWithKey(int index, node* t);

public:
	Tree();
	~Tree();
	void insert(int x, float y);
	void remove(int x, float y);
	void inorder();
	void find(int x);
	int count();
	float& operator[](int index);
	
};

Tree::Tree() {
	root = NULL;
}

Tree::~Tree() {
	root = makeEmpty(root);
}

Tree::node* Tree::makeEmpty(node* t) {
	if (t == NULL)
		return NULL;
	{
		makeEmpty(t->left);
		makeEmpty(t->right);
		delete t;
	}
	return NULL;
}

void Tree::insert(int x, float y) {
	root = insertprivate(x, y, root);
}

Tree::node* Tree::insertprivate(int x, float y, node* t)
{
	if (t == NULL)
	{
		t = new node;
		t->key = x;
		t->data = y;
		t->left = t->right = NULL;
	}
	else if (x < t->key)
		t->left = insertprivate(x, y, t->left);
	else if (x > t->data)
		t->right = insertprivate(x, y, t->right);
	return t;
}

void Tree::remove(int x, float y) {
	root = removeprivate(x, y, root);
}

Tree::node* Tree::removeprivate(int x, float y, node* t) {
	node* temp;
	if (t == NULL)
		return NULL;
	else if (x < t->key)
		t->left = removeprivate(x, y, t->left);
	else if (x > t->key)
		t->right = removeprivate(x, y, t->right);
	else if (t->left && t->right)
	{
		temp = findMin(t->right);
		t->key = temp->key;
		t->right = removeprivate(t->key, t->data, t->right);
	}
	else
	{
		temp = t;
		if (t->left == NULL)
			t = t->right;
		else if (t->right == NULL)
			t = t->left;
		delete temp;
	}

	return t;
}

void Tree::inorder() {
	inorderprivate(root);
	cout << endl;
}

void Tree::inorderprivate(node* t) {
	if (t == NULL)
		return;
	inorderprivate(t->left);
	cout << t->key << "( " << t->data << " )\t";
	inorderprivate(t->right);
}

void Tree::find(int x) {
	root = findprivate(root, x);
}

Tree::node* Tree::findprivate(node* t, int x) {
	if (t == NULL)
		return NULL;
	else if (x < t->data)
		return findprivate(t->left, x);
	else if (x > t->data)
		return findprivate(t->right, x);
	else
		return t;
}

Tree::node* Tree::findMin(node* t)
{
	if (t == NULL)
		return NULL;
	else if (t->left == NULL)
		return t;
	else
		return findMin(t->left);
}

int Tree::countprivate(node* t)
{
	if (t == NULL)
		return 0;
	else
		return (countprivate(t->right) + countprivate(t->left)) + 1;
}

int Tree::count()
{
	cout << "Count = " << countprivate(root);
	cout << endl;
	return 0;
}

float& Tree::operator[](int index)  {
	node* t = findNodeWithKey(index, root);
	if (t) return t->data;
}

Tree::node* Tree::findNodeWithKey(int index, node* t) {
	if (!t || t->key == index) return t;
	return findNodeWithKey(index, index < t->key ? t->left : t->right);
}

int main() {

	Tree* bst = new Tree();
	bst->insert(20, 0.1);
	bst->insert(25, 0.2);
	bst->insert(10, 0.5);
	bst->inorder();
	bst->count();
	bst->remove(20, 0.1);
	bst->inorder();
	bst->count();
	//Tree A;
	//cout << "A[key] = " << ;
	return 0;
}
1 Like

viết hàm main nghĩa là sao :V

2 Likes

thì cái phần chỉ số mảng đó, viết dưới hàm main ra sao vậy bạn

bst[25] gì thôi :V

code của bạn ko có ktra xem key có trong tree hay ko, nếu ko có thì return cái gì? :V Sao ko throw ngoại lệ? Sao ko đọc warning trong toán tử []?

// trong operator[]
if (...) return t->data;
else throw std::runtime_error("Invalid key");

// trong main
int key;
std::cin >> key;
try {
    std::cout << "A[" << key << "] = " << A[key] << "\n";
} catch (const std::exception& e) {
    std::cerr << e.what() << "\n";
}
3 Likes

mình đang học đến phần xử lý ngoại lệ, trong bài làm yêu cầu phải xử lý ít nhất 4 ngoại lệ, mà mình muốn viết cho chương trình chạy được trước đã

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?