Định nghĩa của một cây cân bằng

Question

Tôi chỉ tự hỏi nếu ai đó có thể làm rõ định nghĩa của một cây cân bằng cho tôi. Tôi có rằng "một cây được cân bằng của mỗi cây con được cân bằng và chiều cao của hai cây con khác nhau nhiều nhất một.

Tôi xin lỗi nếu đây là một câu hỏi ngớ ngẩn, nhưng định nghĩa này áp dụng cho mọi nút tất cả các con đường xuống lá của một cây hoặc chỉ để các cây con trái và phải ngay lập tức ra khỏi gốc? Tôi đoán một cách khác để yêu cầu này sẽ được hỏi nếu nó có thể cho các nút bên trong của một cây được không cân bằng và toàn bộ cây vẫn cân?

Answer 1

không có sự khác biệt giữa hai điều này. Hãy suy nghĩ về nó.

Chúng ta hãy định nghĩa đơn giản hơn, "một số dương là ngay cả khi nó là số không hoặc số trừ hai thậm chí còn . " Điều này nói 8 là ngay cả khi 6 là thậm chí? Hoặc điều này nói 8 là ngay cả khi 6, 4, 2, và 0 thậm chí là?

Không có sự khác biệt. Nếu nó nói 8 là ngay cả khi 6 là ngay cả, nó cũng nói 6 là ngay cả khi 4 là ngay cả. Và do đó nó cũng nói 4 là ngay cả khi 2 là ngay cả. Và do đó nó nói 2 là ngay cả khi 0 là ngay cả. Vì vậy, nếu nó nói 8 là ngay cả khi 6 là ngay cả, nó (gián tiếp) nói 8 là ngay cả khi 6, 4, 2, và 0 là ngay cả.

Điều tương tự ở đây. Bất kỳ cây con gián tiếp nào cũng có thể được tìm thấy bởi một chuỗi các cây con trực tiếp. Vì vậy, ngay cả khi nó chỉ áp dụng trực tiếp cho cây con trực tiếp, nó vẫn áp dụng gián tiếp cho tất cả các cây con (và do đó tất cả các nút).

Answer 2

Ràng buộc thường được áp dụng đệ quy cho mọi cây con. Đó là, cây chỉ là cân bằng nếu:

1. cao Các subtrees trái và phải khác nhau bởi ít nhất một, VÀ
2. Các cây con bên trái là cân bằng, VÀ
3. Các cây con bên phải là cân bằng

Theo đó, cây tiếp theo là cân bằng:

 A 
/ \ 
    B  C 
/ /\ 
D  E F 
    / 
    G 

tiếp theo là một không cân bằng vì subtrees C khác nhau bởi 2 trong chiều cao của họ:

 A 
/ \ 
    B  C <-- difference = 2 
/ /
D  E 
    / 
    G 

Điều đó nói rằng, các hạn chế cụ thể của điểm đầu tiên phụ thuộc vào loại cây. Thông tin được liệt kê ở trên là điển hình cho AVL trees. Ví dụ:

Red-black trees áp đặt ràng buộc mềm hơn.

Answer 3

Có một số cách để xác định "Cân bằng". Mục tiêu chính là giữ độ sâu của tất cả các nút là O(log(n)).

Dường như với tôi rằng điều kiện cân bằng mà bạn đang nói đến là dành cho cây AVL.
Dưới đây là định nghĩa chính thức về tình trạng cân bằng AVL cây của:

Đối với bất kỳ nút trong AVL, chiều cao của cây con trái của nó sẽ khác biệt bởi tại hầu hết các 1 từ chiều cao của cây con phải của nó.

Câu hỏi tiếp theo, "chiều cao" là gì?

Chiều cao "" của nút trong cây nhị phân là độ dài của đường dài nhất từ ​​nút đó đến lá.

Có một trường hợp kỳ lạ nhưng điểm chung:

dân xác định chiều cao của một cây trống để được (-1).

Ví dụ, con trái gốc là null:

   A (Height = 2) 
     / \ 
(height =-1)  B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1 
        \ 
        C (Height = 0) 

Hai nhiều ví dụ để xác định:

Vâng, Một Balanced Tree Ví dụ:

 A (h=3) 
    / \ 
B(h=1)  C (h=2)   
/  / \ 
D (h=0) E(h=0) F (h=1) 
      /
       G (h=0) 

Không, Không phải cây cân bằng Ví dụ:

 A (h=3) 
    / \ 
B(h=0)  C (h=2)  <-- Unbalanced: 2-0 =2 > 1 
     / \ 
     E(h=1) F (h=0) 
     / \ 
     H (h=0) G (h=0)  

Answer 4

Cây cân bằng là cây có thứ tự log (số phần tử trong cây).

height = O(log(n)) 
O, as in asymptotic notation i.e. height should have same or lower asymptotic 
growth rate than log(n) 
n: number of elements in the tree 

Định nghĩa cho "cây được cân bằng của mỗi cây con được cân bằng và chiều cao của hai cây con khác nhau nhiều nhất" theo sau là cây AVL.

Vì cây AVL cân bằng nhưng không phải tất cả các cây cân bằng đều là cây AVL, cây cân bằng không giữ định nghĩa này và các nút bên trong có thể không cân bằng trong chúng. Tuy nhiên, cây AVL yêu cầu tất cả các nút bên trong phải được cân bằng.

Answer 5

mục đích của cây cân bằng là để đạt được lá trong một tối thiểu của traversal (min chiều cao). Độ của cây là số cành trừ 1. Cây cân bằng có thể không bị nhị phân.