Ví dụ của Wikipedia về cây AVL không cân bằng thực sự không cân bằng như thế nào?

Question

Hình ảnh trên là từ "Wikipedia's entry on AVL trees" mà Wikipedia cho biết là không cân bằng. Cây này không cân bằng như thế nào? Dưới đây là một trích dẫn từ bài viết:

Yếu tố cân bằng của một nút là chiều cao của cây con phải của nó trừ đi chiều cao của cây con trái của nó và một nút với yếu tố cân bằng 1, 0, hoặc -1 được coi là cân bằng . Một nút với bất kỳ yếu tố cân bằng nào khác được coi là không cân bằng và yêu cầu cân bằng lại cây. Yếu tố cân bằng được lưu trữ trực tiếp tại mỗi nút hoặc được tính từ độ cao của các subtrees.

Cả hai bên trái và phải đều có chiều cao 4. Cây con phải của cây bên trái có chiều cao 3 vẫn chỉ nhỏ hơn 1 4. Ai đó có thể giải thích những gì tôi bị thiếu không?

Answer 1

Để được cân bằng, mỗi nút trong cây phải, một trong hai,

• không có con, (là một "lá" nút)
• Có hai đứa con.

• Hoặc, nếu chỉ có một đứa trẻ, đứa trẻ đó phải là một chiếc lá.

  Trong biểu đồ bạn đã đăng, 9, 54 & 76 vi phạm quy tắc cuối cùng.

đúng cân bằng, cây sẽ trông như thế:

Root: 23 
(23) -> 14 & 67 
(14) -> 12 & 17 
(12) -> 9 
(17) -> 19 
(67) -> 50 & 72 
(50) -> 54 
(72) -> 76 

CẬP NHẬT: (sau gần 9 năm, tôi đã tạo ra một biểu đồ trực tuyến mát mẻ cho đồ thị tại draw.io)

Answer 2

Node 76 là không cân bằng, ví dụ, bởi vì cây con đúng của nó là chiều cao 0 và bên trái là chiều cao 3.

Answer 3

trực giác, đó là bởi vì nó không phải là càng nhỏ càng tốt. ví dụ: 12 phải là cha mẹ của 9 và 14. Do đó, 9 không có cây con bên trái nên nó không cân bằng. Cây là cấu trúc dữ liệu phân cấp nên quy tắc như "cân bằng" thường áp dụng cho mọi nút và không chỉ nút gốc.

Bạn chính xác nút gốc được cân bằng, nhưng không phải tất cả các nút của cây đều là.

Answer 4

Một cách khác để xem xét điều này là chiều cao h của bất kỳ nút nào được cho bởi:

h = 1 + max(left.height, right.height)

và một nút là không cân bằng bất cứ khi nào:

abs(left.height - right.height) > 1

Nhìn vào cây trên:

- Node 12 is a leaf node so its height = 1+max(0,0) = 1 
- Node 14 has one child (12, on the left), so its height is = 1+max(1,0) = 2 
- Node 9 has one child (14, on the right), so its height is = 1+max(0,2) = 3 

Để xác định xem nút 9 là cân bằng hay không chúng ta nhìn vào chiều cao của trẻ em của mình :

- 9's left child is NULL, so 9.left.height = 0 
- 9's right child (14) has height 2, so 9.right.height = 2 

Bây giờ giải quyết để cho thấy nút 9 không cân bằng :

9.unbalanced = abs(9.left.height - 9.right.height) > 1 
9.unbalanced = abs(0 - 2) > 1 
9.unbalanced = abs(-2) > 1 
9.unbalanced = 2 > 1 
9.unbalanced = true 

Tính toán tương tự có thể được thực hiện cho mọi nút khác.