Cải thiện thuật toán tính chiều cao của cây (thuật toán cũ bị time limited)

Format lại code bạn nhé. Thêm 3 dấu ` vào đầu và cuối code.

phần tử thứ i có giá trị là value[i] sẽ là con của phần tử thứ value[i]

Thế thì khác gì là cha của nút i là value[i]? Bạn viết thế này hơi khó hiểu.

Tớ đã sửa, cám ơn c đã góp ý

image.png1366x768 40.5 KB

ôi…

t đổi quyền truy cập rồi c ạ. C xem giúp tớ chút nhé

Thay vì viết hàm tính height() đệ quy thì bạn chuyển thành void.
Tạo 1 mảng h[] là chiều sâu của nút so với gốc.
h[root] = 0, chiều cao cả cây = max(h[]) + 1

Nếu tớ k hiểu nhầm ý bạn thì có phải bạn định tính chiều cao của tất cả các node trong cây, rồi đưa nó vào 1 mảng, rồi lấy max của mảng đó +1 không? Tớ thấy như vậy thì tương đương với cách tớ làm, vì mỗi node tớ cũng chỉ đi qua 1 lần thôi. Với lại để tính chiều cao của 1 node mà không sử dụng đệ quy thì làm cách nào? nếu c tính đủ số node trên cây, thì sẽ bị tính đi tính lại chiều cao của 1 vài node nhiều lần :))))

nếu c tính đủ số node trên cây, thì sẽ bị tính đi tính lại chiều cao của 1 vài node nhiều lần :))))

Linh tinh. DFS đâu có tính các node nhiều lần thớt chưa hiểu về DFS rồi.

để tính chiều cao của 1 node mà không sử dụng đệ quy thì làm cách nào?

BFS.

heightChild = (heightChild < height(pos)) ? height(pos) : heightChild;

Cái này chỉ cần thay height(pos) thành 1 biến phụ và tính một lần sẽ giảm được độ phức tạp.

Giả sử cây suy biến thành một linked-list (chỉ có 1 node bên trái) Độ phức tạp của thuật toán tinh height
T(n) = 2*T(n-1) + O(1) => T ~ O(2^n)
nếu thay hieght bằng biến phụ và chỉ tính 1 lần
T(n) = T(n-1) + O(1) =>T ~ O(n)
Nhanh hơn rất nhiều so với không dùng biến phụ

Đã sửa được và chạy ổn, cám ơn 2 bạn. Tớ đã sửa được thêm phần dựng cây để nó chỉ còn là O(n) chứ không còn là O(n^2) như code trên( lại bị quá thời gian ở test 17 đến 20).
Đến test 21, chương trình lại báo lỗi stack overflow. Tại dữ liệu đầu vào lớn quá, 100 000 số dựng thành cây có chiều cao 100 000!

class node {
private:
	int data;
	node* child;
	node *sibling;
	node *posLastChild;
public:
	node() {
		data = 0;
		child = NULL;
		sibling = NULL;
		posLastChild = NULL;
	}
	int getData() {
		return data;
	}
	void setData(int key) {
		data = key;
	}
	node * getChild() {
		return child;
	}
	void setChild(node* _child)
	{
		child = _child;
	}
	node* getSibling() {
		return sibling;
	}
	void setSibling(node *_sibling)
	{
		sibling = _sibling;
	}
	node *getLastChild()
	{
		return posLastChild;
	}
	void setLastChild(node* temp)
	{
		posLastChild = temp;
	}
};
class tree {
	//    root
	//  /
	// child 1st -> child 2nd ->child 3rd ....
	// ...
private:
	node *root;
public:
	tree()
	{
		root = NULL;
	}
	void constructTheTree(int *p, int n) {
		node *temp = new node[n];
		std::cout << "constructing..." << std::endl;
		for (int i = 0; i < n; i++)
		{
			temp[i].setData(p[i]);
			if (p[i] == -1)
			{
				root = &temp[i];
			}
			else {
				if (temp[p[i]].getChild() == NULL)
				{
					temp[p[i]].setChild(&temp[i]);
					temp[p[i]].setLastChild(&temp[i]);
				}
				else {
					node *posLastChild = temp[p[i]].getLastChild();
					posLastChild->setSibling(&temp[i]);
					temp[p[i]].setLastChild(&temp[i]);

					/*node* posSibling = temp[p[i]].getChild();
					while (posSibling->getSibling() != NULL)
					{
						posSibling = posSibling->getSibling();
					}
					posSibling->setSibling(&temp[i]);*/
				}
			}
		}
		std::cout << "constructed!" << std::endl;
	}
	void display(node *n)
	{
		if (n->getChild() == NULL)
		{
			std::cout << n->getData() << " ";
		}
		else {
			node *sibling = n->getChild();
			display(sibling);
			std::cout << n->getData() << " ";
			while (sibling->getSibling() != NULL)
			{
				display(sibling->getSibling());
				sibling = sibling->getSibling();
			}
		}
	}
	node *getRoot() {
		return root;
	}
	int height(node* n)
	{
		if (n->getChild() == NULL)
		{
			return 1;
		}
		
		else
		{
			int heightChild = -1;
			node* pos = n->getChild();
			while (pos!= NULL)
			{
				int heightPos = height(pos);
				heightChild = (heightChild < heightPos) ? heightPos : heightChild;
				pos = pos->getSibling();
			}
			return 1 + heightChild;
		}
		
	}
};

bộ test 21: https://www.fshare.vn/file/4BYN22SJ5PW4 ( open with note pad)
đáp án cho test 21 này là 100 000!

100000 vẫn chưa phải là lớn.

node *temp = new node[n];

Hình như với mỗi node bạn lại xây một mảng node[n]?

Hình như với mỗi node bạn lại xây một mảng node[n]?

Không phải, tớ chỉ xây dựng 1 mảng có n node, xong rồi gán các con trỏ của các node( con trỏ child, sibling, lastChild), gán con trỏ root của tree ,để hình thành cây thôi.
Hàm constructTheTree chỉ cần gọi 1 lần với mỗi bộ số liệu vào. C mở file test sẽ thấy dạng của nó, dòng đầu chứa số phần tử, dòng thứ 2 trở đi chứa các số. Tớ lưu các số đó dưới dạng mảng có số phần tử như dòng 1 đã cho. Đó là lý do mà hàm này có 2 tham số là int*p, và int N.
Test 21, xác định được lỗi ở phần tính chiều cao. Các phần khác đã thử, không bị lỗi