Mình đang làm bài tập c++ về cây AVL,làm xong bài 1 sang bài 2 thì có cụm từ " thêm con trỏ trỏ tới nút cha" , trước giờ thấy mỗi con trỏ rẽ nhánh trái phải chứ chưa thấy con trỏ trỏ tới nút cha
ACE ai biết chỉ mình vụ này với
Nếu được thì mình xin 1 đoạn code minh họa không thì thuật toán hoặc đơn giản là keyword thì cũng ok lắm rồi
Cảm ơn mọi người
Bạn này thích trồng cây nhỉ…
public class Node {
private Node parentNode;
private Node leftNode;
private Node rightNode;
...
}
Node root = new Node(null, left, right);
Hì hì bài tập mà,cơ mà chưa hiểu làm sao mỗi lần chạy ( ví dụ nhập dữ liệu từ file ) nút cha được cật nhật bạn nhỉ
Thì khi nào tạo hoặc di chuyển child-node thì đồng thời cập nhật parent-node cho nó thôi.
Thực ra là với cậy AVL thì không thấy việc lưu lại parent-node có ý nghĩa lắm trừ việc phải cân bằng lại cây. Vì khi cân bằng lại cây thì các node bị thay đổi vị trí dẫn đến việc đệ quy không đạt được hiệu quả nên cần biết parent-node để biết cách truy vấn ngược lên trên thôi.
Anh có thể cho em 1 đoạn code ngắn được không,em vẫn mập mờ quá
Dùng mã giả code cho dễ hiểu nhé. Ví dụ cho bài toán tìm số lớn nhất nhỏ hơn node cho trước:
// Nếu bên trái mà tồn tại null thì đi tìm số lớn nhất bên trái.
if this.left != null
return findMax(this.left)
else
// Nếu không có node bên trái thì phải tìm xem cha của nó có không vì node bên phải chắc chắn lớn hơn nó.
parent = this.parent, T = this
// Nếu nó không phải là root và nó là node bên trái của cha nó nghĩa là cha nó lớn hơn nó thì phải duyệt tiếp đến ông nó.
while(parent != null && T == parent.left)
T = parent, parent = T.parent
// Nếu tìm đến root rồi mà không có thằng nào thỏa mãn nghĩa là trong cây đó không có thằng nào bé hơn nó hết.
if parent is null
return -1
else
// Nếu không phải là root nghĩa là cái thằng này là thằng xem ảnh đi.
return parent
Thằng node start là thằng d thằng e nằm bên trái sẽ lớn hơn d. Tương tự thằng b và c cũng lớn hơn d. Tìm ra thằng a nhỏ hơn d.
Nếu duyệt tiếp thằng right thì thằng right lớn hơn thằng b do nếu b lớn hơn right thì nó đã nằm bên phải thằng right rồi. Điều đó kéo theo là right lớn hơn d.
Nếu duyệt tiếp thằng left thì thằng này sẽ nhỏ hơn thằng a rồi nên a chính là thằng cần tìm.
Đấy ví dụ bài toán này không duyệt từ root thì không có parent- node thì không làm được. Còn nếu duyệt từ root thì đơn giản thôi. Chạy tìm mút mùa ra được thằng d xong tìm ngược lại. Chưa kể input là d thì cũng không tìm được chỗ root ở đâu cả.
Lâu lâu làm mấy bài này đau não quá.
Cảm ơn anh rất nhiều 
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?
