Hỏi về AVL Tree, Binary Search Tree

Virtuesuccess · September 8, 2019, 4:02pm

Chào mọi người,

Mình đang học về cấu trúc giữ liệu và giải thuật, đang xây dựng 1 cây AVL.

AVL Tree là loại đặc biệt hơn của BST - Binary Search Tree.
Lúc xây dựng BST thì mình có thêm cho class Tree này 1 thuộc tính khác lúc delete được dễ dàng hơn.
Bây giờ thì mình đang xây dựng AVL Tree, mình dự định thêm hẳn 1 thuộc tính height và 1 thuộc tính parent cho các Node.

Về BST thì mình nghĩ chỉ thêm 1 thuộc tính cho toàn bộ cây nên cũng sẽ không tăng quá nhiều về bộ nhớ.

Còn về AVL thì thuộc tính height là bắt buộc để cân bằng lại cây, mình phân vân là liệu mình thêm thuộc tính parent cho mỗi Node để cân bằng lại cây thì có làm tăng thêm quá nhiều bộ nhớ không?

rogp10 · September 8, 2019, 11:09pm

Thêm parent thì không nhiều do nó chỉ là tham chiếu.

Virtuesuccess · September 8, 2019, 11:17am

Ví dụ có 1 object là house, house có 2 object là wife và husband, vậy khi mình thêm cho wife thuộc tính spouse có giá trị bằng husband thì có cần gấp đôi bộ nhớ(husband và wife cùng thuộc class people) để lưu biến wife không.

Mình có thể đọc thêm về cái gì để chắc chắn được câu trả lời nhỉ?

Cảm ơn bạn đã phản hồi !

rogp10 · September 8, 2019, 11:54am

Cả hai trường hợp đều là tham chiếu nhưng cây gia phả thì cân bằng ko được đâu.

Virtuesuccess · September 8, 2019, 12:07pm

Cây gia phả là cây gì nhỉ. Mình chỉ biết một số loại cây ở Data Structures. Theo mình biết thì AVL với Red-Black Tree cân bằng được mà. Ngồi cả chiều thì cũng mày mò xong phần insert với kiểm tra unbalance, tí rotate nữa là ổn. Mình viết bằng python và cũng làm khá chi tiết. Làm xong mình sẽ chia sẻ cùng mọi người và góp ý, bổ sung luôn.

rogp10 · September 8, 2019, 12:09pm

Ý bạn là sibling? có parent rồi thì bạn đi qua parent thôi không cần tham chiếu cho sibling vì độ phức tạp sẽ lên O(n).

Virtuesuccess · September 8, 2019, 12:17pm

Không, mình có lưu sibling làm gì đâu, mình lưu parent để lúc delete thì gắn con của parent vào 1 Node khác.
AVL để đưa độ phức tạp về O(log(n)) cho cả trường hợp xấu nhất là cây trở thành Linked List, nếu mình làm cho về O(n) thì code vừa dài, độ phức tạp lại hơn cả LinkedList 1 tí.

Trong quá trình Insert thì độ phức tạp vẫn sẽ là O(log(n)) vì mình phải cập nhật lại height cho các Node thuộc nhánh vừa được Insert cũng như cân bằng lại cây, tương tự thì delete cũng vậy.