trọng lượng không cân bằng cây AVL

Question

Tin rằng các bài viết wikipedia: http://en.wikipedia.org/wiki/AVL_tree

cây AVL là chiều cao cân bằng, nhưng nói chung không trọng lượng cân bằng cũng không μ cân bằng; [4] có nghĩa là, các nút anh chị em có thể có vô cùng số lượng con cháu khác nhau.

Nhưng, như một cây AVL là:

tự cân bằng nhị phân cây tìm kiếm [...]. Trong một cây AVL, chiều cao của hai subtrees con của bất kỳ nút khác nhau bởi ít nhất một

tôi không thấy làm thế nào một AVL có thể là trọng lượng cân bằng từ -Nếu tôi đã hiểu định nghĩa của một cây AVL well-, mỗi anh chị em sẽ có cùng số lượng con vì chúng có cùng chiều cao +/- 1.

Vì vậy, bạn có thể cho tôi ví dụ về cây AVL không cân bằng? Tôi đã không thành công để tìm thấy một. Do đó, hay tôi hiểu lầm nghĩa của một/cây không trọng số AVL, hoặc các bài viết wikipedia là sai ...

Cảm ơn

Answer 1

Bạn là chính xác trong sự hiểu biết của bạn mà một cây AVL được xác định bởi chiều cao gần đồng nhất của các nút cạnh của nó, nhưng sự nhầm lẫn của bạn dường như là về sự khác biệt giữa vị trí nút và trọng lượng cạnh.

Tức là: Trong cây AVL, độ sâu của các nút cạnh sẽ giống nhau +/- (nhưng không phải cả hai!). Điều này làm cho không có tuyên bố về chi phí liên quan đến một cạnh giữa các nút. Đối với cây AVL có nút gốc và hai con, đường dẫn bên trái có thể đắt gấp đôi để đi qua như đường dẫn bên phải. Điều này sẽ làm cho cây không cân bằng, nhưng vẫn duy trì định nghĩa của cây AVL.

Trang này có thêm thông tin: Weight-balanced tree - wikipedia

Từ Wikipedia:

Một Binary Tree được gọi là μ cân bằng, với , nếu cho mỗi nút N, sự bất bình đẳng:

giữ và μ là tối thiểu với tài sản này. | N | là số lượng các nút dưới gốc cây với N là gốc (bao gồm gốc) và Nl là cây con bên trái của N.

Về cơ bản, điều này có nghĩa là trẻ em trong cây AVL không nhất thiết phải phân phối đồng đều trên mức thấp nhất của cây. Lấy N như chỉ ra nút gốc của cây, người ta có thể xây dựng một cây AVL hợp lệ có nhiều trẻ em ở bên trái của gốc hơn là bên phải của nó. Với một cái cây rất sâu, có thể có nhiều nút ở tầng dưới cùng này.

Định nghĩa của một cây AVL sẽ đòi hỏi rằng tất cả họ đều nằm trong một trong những điểm sâu nhất, nhưng không đảm bảo như những gì nút họ là con cái của đối với một N. nút

Answer 2

anh chị em ruột các nút có thể có số lượng con cháu rất khác nhau.

Tôi chỉ đang gãi đầu về việc này và thực tế là việc triển khai AVL của tôi đã tạo ra những cây không bị lệch hoàn toàn, nhưng có các nhánh nhỏ hơn "lớn hơn" ở bên trong.

tôi phác thảo này ra để trấn an bản thân mình:

Các nút màu đỏ có số dư là 1, những cái màu xanh lá cây -1, và những màu đen 0. Đây là một cây AVL hợp lệ trong đó sự khác biệt về chiều cao giữa hai cặp anh chị em không bao giờ nhiều hơn một, nhưng có (gần như) gấp đôi số nút ở bên phải của cây con bên trái.