Cân bằng cây bằng phép xoay
Cân bằng cây bằng phép xoay
Bài trước để lại một cái hố: cùng 15 khoá, chèn theo thứ tự đã sắp thì cây cao 15 tầng thay vì 4, và không có gì trong cây tìm kiếm thường ngăn chuyện đó. Bài này lấp cái hố ấy, và bắt bạn trả tiền cho việc lấp.
Bài cây tìm kiếm nhị phân kết thúc bằng một lời hẹn. Nó cho bạn thấy rằng cây không nhớ tập khoá, nó nhớ thứ tự khoá đi vào: cùng 15 khoá từ 10 tới 150, chèn theo thứ tự cân bằng thì cây cao 4 tầng, chèn theo thứ tự đã sắp thì cây cao 15 tầng và biến thành một danh sách liên kết. Rồi nó nói rằng cây AVL và cây đỏ đen sinh ra để chặn đúng chuyện đó, và nói thẳng là nó không cài đặt chúng.
Bài này cài đặt cây AVL. Trên đúng bộ khoá cũ, đúng thứ tự đã sắp cũ, và có một công tắc để bạn tắt phép xoay đi rồi bật lại mà so.
Ý tưởng gọn tới mức đáng ngờ. Cây không tự biết nó đang méo, nên ta bắt mỗi nút nhớ thêm chiều cao nhánh của nó. Từ hai chiều cao con, mỗi nút tính ra một con số gọi là hệ số cân bằng: chiều cao con trái trừ chiều cao con phải. Cây AVL là cây mà mọi nút có hệ số ấy nằm trong {−1, 0, +1}. Khi một lần chèn làm con số đó văng ra khỏi khoảng cho phép, ta nối lại vài liên kết để kéo nhánh cao xuống và đẩy nhánh thấp lên. Việc nối lại đó gọi là phép xoay.
Sim dưới đây hiện hệ số cân bằng ngay trên từng nút, cho bạn đi từng bước qua bốn ca xoay, và đếm thật mọi phép mà việc giữ thăng bằng tiêu tốn. Nếu bạn thấy bài đang dẫn bạn tới một kết luận, hãy vặn núm cho tới khi kết luận đó sai.
1 · Dãy khoá và thứ tự chèn ✎ sửa được
↻k trên một khoá nghĩa là lần chèn khoá ấy đã tốn k phép xoay đơn. Cả dãy này tốn 11 phép xoay trong 11 lần cân bằng lại.2 · Cây được vẽ ra, kèm hệ số cân bằng
+1 nghĩa là nhánh trái cao hơn một tầng, và dấu ! phía trước nghĩa là nút ấy phạm luật. Số bên phải một nút là thứ tự bước của đường tìm kiếm đang chạy. Trục ngang là thứ tự duyệt giữa, nên đọc cây từ trái sang phải vẫn là đọc dãy đã sắp.3 · Bốn phép xoay, đi từng bước ✎ sửa được
10, 20, 30. Ca này tốn 1 phép xoay đơn.Cây đang cân bằng: mọi nút có hệ số trong {-1, 0, +1}. Chiều cao 2.
4 · Cùng dãy khoá, cùng thứ tự, khác đúng một cái công tắc
| trên đúng 15 khoá này, chèn theo thứ tự đã sắp | tự cân bằng BẬT | tự cân bằng TẮT |
|---|---|---|
| số nút | 15 | 15 |
| chiều cao | 4 | 15 |
| chiều sâu trung bình | 3,27 | 8,00 |
| phép so sánh để tìm 110 | 4 | 11 |
| phép xoay đã dùng | 11 | 0 |
| tổng chi phí dựng cây | 145 | 105 |
| là cây AVL hợp lệ | ✓ có | ✗ không |
5 · Cái giá, đếm thật từng bước
| lần | khoá | so sánh | cập nhật chiều cao | phép xoay | ca | xoay tại nút |
|---|---|---|---|---|---|---|
| 1 | 10 | 0 | 0 | 0 | — | — |
| 2 | 20 | 1 | 1 | 0 | — | — |
| 3 | 30 | 2 | 4 | 1 | RR | 10 |
| 4 | 40 | 2 | 2 | 0 | — | — |
| 5 | 50 | 3 | 5 | 1 | RR | 30 |
| 6 | 60 | 3 | 5 | 1 | RR | 20 |
| 7 | 70 | 3 | 5 | 1 | RR | 50 |
| 8 | 80 | 3 | 3 | 0 | — | — |
| 9 | 90 | 4 | 6 | 1 | RR | 70 |
| 10 | 100 | 4 | 6 | 1 | RR | 60 |
| 11 | 110 | 4 | 6 | 1 | RR | 90 |
| 12 | 120 | 4 | 6 | 1 | RR | 40 |
| 13 | 130 | 4 | 6 | 1 | RR | 110 |
| 14 | 140 | 4 | 6 | 1 | RR | 100 |
| 15 | 150 | 4 | 6 | 1 | RR | 130 |
| tổng | 45 | 67 | 11 | LL 0 · RR 11 · LR 0 · RL 0 | ||
6 · Điểm hoà vốn ✎ sửa được
Dựng cây AVL đắt hơn 40 bước, nhưng mỗi vòng tìm hết 15 khoá thì nó rẻ hơn 71 bước. Chia ra thì cần 1 vòng.
7 · Ba cái trần, và cây của bạn nằm đâu
floor(log2(15)) + 1, và log2(15) ≈ 3,91trần của cây AVL: 5 tầngcây này: 4 tầng, ở vị trí 0,0% trên thangtrần khi không xoay: 15 tầng
n, tức mỗi tầng đúng một nútN(h) = 1 + N(h-1) + N(h-2): cây AVL cao h tầng cần ít nhất N(h) nút, nên 15 nút nhét được nhiều nhất 5 tầng. Quy tắc quen thuộc 1,44 × log₂(n) cho 5,63, tức là xấp xỉ chứ không phải chính cái trần: nó nói gần đúng từ phía trên, và ở n bằng 1, 2 hay 4 thì nó còn thấp hơn cả trần thật.8 · Tìm một khoá ✎ sửa được
| bước | so với nút | độ sâu | hệ số cân bằng | 110 so với nút này | đi đâu tiếp |
|---|---|---|---|---|---|
| 1 | 80 | 1 | 0 | lớn hơn | sang con phải |
| 2 | 120 | 2 | 0 | nhỏ hơn | sang con trái |
| 3 | 100 | 3 | 0 | lớn hơn | sang con phải |
| 4 | 110 | 4 | 0 | bằng | dừng, đây là nút cần tìm |
- Cây AVL không cân bằng hoàn hảo. Luật chỉ đòi hệ số cân bằng nằm trong {−1, 0, +1}, nên với 15 nút nó cho phép tới 5 tầng trong khi sàn là 4. Trên 9999 hạt giống xáo của bộ 15 khoá, cây AVL chạm sàn 4 tầng đúng 456 lần và dừng ở 5 tầng 9543 lần.
- Một phép xoay ở đây là một phép xoay ĐƠN, nên xoay kép tính là hai. Nhiều sách tính xoay kép là một thao tác, và mọi con số phép xoay trong bài sẽ giảm nếu đổi quy ước. Đây là quy ước, không phải chân lý.
- Mô hình chi phí là một lựa chọn. Bài tính một bước là một phép so sánh, một lần cập nhật chiều cao, hay một lần ghi liên kết, và coi ba loại đó ngang giá nhau. Trên máy thật chúng không ngang nhau. Núm giá phép xoay cho bạn vặn thử, và điểm hoà vốn dịch theo.
- Nó đếm phép, nó không đo giây. Cây thấp hơn không tự động nhanh hơn: các nút nằm rải rác trong bộ nhớ, còn một mảng đã sắp thì liền một dải. Muốn biết cái nào nhanh hơn thì phải đo trên máy của bạn.
- Bài này không cài đặt phép xoá của cây AVL. Xoá khó hơn chèn thật sự: một lần chèn cần nhiều nhất một lần cân bằng lại, còn một lần xoá có thể phải cân bằng lại ở mọi tầng trên đường về gốc. Bốn ca xoay thì vẫn đúng, nhưng có thêm một ca mà chèn không bao giờ gặp: nút con lệch 0.
- Bài này cũng không dạy cây đỏ đen. Cây đỏ đen nới lỏng điều kiện cân bằng, cho nhánh dài nhất được gấp đôi nhánh ngắn nhất, nên nó xoay ít hơn AVL khi ghi và cây cao hơn một chút khi đọc. Không có gì trong sim này chứng minh điều đó, vì không dòng nào ở đây cài đặt nó.
Ở trạng thái mở đầu, sim đang nói gì
Dãy khoá vẫn là 15 số quen thuộc: 10, 20, 30 cho tới 150. Thứ tự chèn đang là thứ tự đã sắp, tức đúng cái thứ tự đã giết cây của bài trước. Tự cân bằng đang BẬT.
Cây thu được có 15 nút và chiều cao 4. Tổng chiều sâu 49, nên chiều sâu trung bình là 49/15, tức 3,27. Tìm khoá 110 mất 4 phép so sánh. Có 8 nút lá, và mọi nút đều có hệ số cân bằng 0.
Bốn phép so sánh để tìm một khoá trong 15 khoá chính là cái mà tìm nhị phân trên mảng đã sắp cũng cho bạn, và đó là điều lời hứa của cây tìm kiếm nói tới. Khác biệt là ở đây bạn giữ được nó trong khi vẫn chèn và xoá rẻ.
Bạn đã thấy cả bốn con số đó ở bài trước, ở cột thứ tự cân bằng. Và đây không phải trùng hợp: cây AVL dựng từ dãy đã sắp có dãy duyệt trước là
80 40 20 10 30 60 50 70 120 100 90 110 140 130 150
tức là trùng khít với cây cân bằng dựng tay của bài trước, từng nút một. Phép xoay đã dựng lại đúng cái hình dạng tối ưu ấy mà không hề được cho biết hình dạng ấy là gì. Nó chỉ đi theo một luật địa phương: nút nào lệch quá một tầng thì nối lại liên kết ở đó.
Bây giờ bấm TẮT · cây thường. Dãy khoá không đổi, thứ tự chèn không đổi, chỉ thuật toán chèn đổi.
| trên đúng 15 khoá đó, chèn theo thứ tự đã sắp | tự cân bằng BẬT | tự cân bằng TẮT |
|---|---|---|
| số nút | 15 | 15 |
| chiều cao | 4 | 15 |
| chiều sâu trung bình | 3,27 | 8,00 |
| phép so sánh để tìm 110 | 4 | 11 |
| phép xoay đã dùng | 11 | 0 |
| tổng chi phí dựng cây | 145 | 105 |
| là cây AVL hợp lệ | ✓ có | ✗ không |
Hai dòng cuối là chỗ bài này khác bài trước. Chiều cao 4 không miễn phí, và cột bên phải rẻ hơn ở khâu dựng cây. Phần cái giá ở dưới bóc con số đó ra.
Về cột phải: cây thoái hoá có 13 trên 15 nút phạm luật AVL, và hệ số lệch nhất là 14. Chỉ hai nút thoát: nút lá lệch 0, và cha của nó lệch 1, mà lệch một tầng thì vẫn hợp lệ.
Hệ số cân bằng, và vì sao mốc là 1 chứ không phải 0
Mỗi nút mang một con số bằng chiều cao con trái − chiều cao con phải. Quy ước chiều cao ở đây giống hệt bài trước: đếm bằng số nút trên đường dài nhất, nên một lá cao 1 và một nhánh rỗng cao 0.
Luật AVL là |hệ số| ≤ 1. Đây là chỗ dễ đọc lướt mà hiểu sai, nên nói thẳng: luật không đòi hai nhánh bằng nhau. Nó cho phép lệch đúng một tầng.
Bấm bộ khoá 2 khoá trong sim. Cây có hai nút, nút gốc 10 có con phải 20, nên hệ số của gốc là 0 − 1 = −1. Lệch một tầng, tức vẫn hợp lệ, nên không phép xoay nào xảy ra. Nếu luật là "phải bằng 0" thì một cây hai nút đã là bất khả thi, vì không cách nào xếp hai nút cho cân.
Bấm tiếp 3 khoá tăng dần, tức 10 20 30. Chèn 30 làm hệ số của nút 10 tụt xuống −2, và đó mới là phạm luật. Cây xoay đúng một lần, nút 20 lên làm gốc, chiều cao còn 2 thay vì 3. Đây là lần xoay đầu tiên trong đời một cây chèn tăng dần, và sim khoá cái mốc đó ở cả hai phía: sau 2 khoá vẫn 0 phép xoay, sau 3 khoá là 1.
Kéo thanh số khoá đã chèn ở trạng thái mở đầu và bạn thấy cùng chuyện đó lặp lại: sau 7 khoá cây cao 3 tầng với 4 phép xoay; chèn khoá thứ 8 thì cây cao lên 4 tầng mà vẫn 4 phép xoay, vì mở một tầng mới thì không ai lệch cả.
Bốn phép xoay, và ca thứ ba mới là ca khó
Khi một nút phạm luật, chỉ có bốn hình dạng có thể xảy ra, phân theo nút lệch về bên nào và con nặng của nó lệch về bên nào. Mục 3 của sim cho bạn bấm từng ca và đi từng bước.
| ca | hình dạng lúc lệch | dãy chèn 3 khoá | chữa bằng | phép xoay đơn |
|---|---|---|---|---|
| RR | lệch phải, con phải cũng lệch phải | 10, 20, 30 | xoay trái tại nút lệch | 1 |
| LL | lệch trái, con trái cũng lệch trái | 30, 20, 10 | xoay phải tại nút lệch | 1 |
| LR | lệch trái, nhưng con trái lại lệch phải | 30, 10, 20 | xoay trái ở con, rồi xoay phải | 2 |
| RL | lệch phải, nhưng con phải lại lệch trái | 10, 30, 20 | xoay phải ở con, rồi xoay trái | 2 |
Cả bốn dãy trên đều dừng ở cùng một cây: gốc 20, con trái 10, con phải 30, cao 2 tầng, mọi hệ số về 0. Bốn đường đi khác nhau, một đích.
Hai ca đơn thì hiển nhiên. Cây nghiêng phải và nhánh phải cũng nghiêng phải, tức cả thân cây cong cùng một chiều: kéo con phải lên làm gốc, đẩy gốc cũ xuống làm con trái, xong. Chiều cao nhánh trở về đúng giá trị trước khi chèn, nên mọi nút phía trên cũng tự cân trở lại.
Hai ca kép mới là chỗ code thật hay hỏng. Ở ca LR, cây nghiêng trái nhưng nhánh con lại cong ngược, hình chữ chi. Nếu bạn cứ thế xoay phải một phát thì được một cây lệch y hệt, chỉ đổi chiều. Bấm sang ca LR trong sim rồi đi tới bước 3 mà xem: sau phép xoay đầu tiên, nút gốc vẫn còn hệ số +2, tức vẫn hỏng, và cây vẫn cao 3 tầng. Cái mà bước đó làm được là đổi ca: từ LR nó thành LL. Bước 4 mới là bước chữa thật.
Nói cách khác, phép xoay kép không phải là "xoay hai lần cho chắc". Nó là bẻ nhánh con về cùng chiều trước, rồi mới xoay. Và vì nó là hai phép xoay đơn nên bài này tính là 2. Nhiều sách tính một phép xoay kép là một thao tác, và nếu đổi quy ước thì mọi con số phép xoay trong bài giảm theo. Nói ra để bạn khỏi ngơ ngác khi đọc sách khác.
Một chi tiết đo được mà sách hay bỏ: khi chèn, con nặng của nút phạm luật luôn lệch đúng 1, không bao giờ lệch 0. Cổng kiểm số của bài soi 1712 lần cân bằng lại và không gặp lần nào con nặng lệch 0. Lý do: nhánh ấy vừa cao thêm đúng một tầng. Hệ quả là khi chèn thì bốn ca trên là bốn ca duy nhất, không có ca thứ năm. Phép xoá thì có, và bài này không dạy xoá.
Cái giá, đếm thật
Đây là phần mà mô tả bằng lời không thay được. Cây AVL làm thêm ba việc mà cây thường không làm, và cả ba đều đếm được:
- phép so sánh đi xuống, giống hệt cây thường;
- cập nhật chiều cao trên đường đi ngược lên, một lần cho mỗi nút đã thăm, cộng hai lần cho mỗi phép xoay đơn;
- ghi liên kết khi xoay: một phép xoay đơn nối lại ba liên kết.
Trên 15 khoá đã sắp, hoá đơn là:
| khoản | tự cân bằng BẬT | tự cân bằng TẮT |
|---|---|---|
| phép so sánh | 45 | 105 |
| cập nhật chiều cao | 67 | 0 |
| ghi liên kết (11 xoay × 3) | 33 | 0 |
| tổng | 145 | 105 |
Con số 67 không phải rơi từ trên trời: nó bằng 45 + 2×11, tức số nút đã thăm cộng hai lần mỗi phép xoay. Cổng kiểm số khoá đẳng thức đó trên mọi lần chèn của cả lưới cây, chứ không riêng ca này.
Chú ý cột trái: cây AVL so sánh ít hơn hẳn, 45 so với 105, đúng vì cây nó dựng thấp hơn. Con số 105 kia là 14×15/2, tức tổng 1 + 2 + ... + 14: dựng một cái que là việc bậc hai theo số khoá, đúng cái bậc tăng bạn đã gặp ở bậc tăng. Còn 45 thì bò theo n log n, và khoảng cách giữa hai đường ấy chỉ nới rộng thêm khi n lớn lên. Nhưng nó tốn 67 + 33 = 100 bước phụ trội, nên tổng vẫn đắt hơn: 145 so với 105, tức thêm 40 bước.
Còn ở khâu tìm thì ngược hẳn. Tổng chiều sâu là 49 so với 120, nên một vòng tìm hết cả 15 khoá tốn 49 bước thay vì 120, rẻ hơn 71 bước.
Số phép xoay cũng có công thức đóng. Với dãy đã sắp n khoá, cây AVL luôn chạm sàn floor(log₂ n) + 1 và luôn tốn đúng n − floor(log₂ n) − 1 phép xoay. Với n = 15 thì đó là 15 − 3 − 1 = 11. Cổng kiểm số khẳng định cả hai công thức cho mọi n từ 1 tới 400, tức xa hơn cái sim vẽ được nhiều. Nhìn cột phép xoay trong bảng từng lần chèn: nó bằng 0 đúng ở các lần chèn thứ 1, 2, 4, 8, 16, 32, tức các luỹ thừa của 2, và bằng 1 ở mọi lần còn lại.
Điểm hoà vốn, và một ca không bao giờ hoà
Chèn đắt hơn, tìm rẻ hơn. Vậy đắt hay rẻ thì tuỳ vào bạn tìm bao nhiêu lần trên mỗi lần chèn.
Đặt r là số lần tìm trên mỗi khoá đã chèn. Vì một lần tìm trúng tốn đúng bằng độ sâu của nút, nên r vòng tìm hết cả cây tốn đúng r × tổng chiều sâu. Mọi đại lượng đều là số nguyên, không có chỗ cho làm tròn:
tổng chi phí = chi phí dựng cây + r × tổng chiều sâu
Trên dãy đã sắp:
| r | tự cân bằng BẬT | tự cân bằng TẮT | ai rẻ hơn |
|---|---|---|---|
| 0 | 145 + 0×49 = 145 | 105 + 0×120 = 105 | TẮT |
| 1 | 145 + 1×49 = 194 | 105 + 1×120 = 225 | BẬT |
Nên trên dãy đã sắp, điểm hoà vốn là 1 lần tìm trên mỗi lần chèn. Chèn xong mà mỗi khoá được hỏi tới đúng một lần thôi là cây AVL đã có lãi. Sim khoá mốc này ở cả hai phía, tức khẳng định rằng ở r = 0 cây AVL còn đắt hơn và ở r = 1 thì nó đã rẻ hơn.
Bây giờ bấm thứ tự cân bằng ở ô thứ tự chèn. Đây là thứ tự mà cây tìm kiếm thường đã chạm sàn ở bài trước, nên chả có gì để chữa.
- Cây thường: chiều cao 4, tổng chiều sâu 49, chi phí dựng 34.
- Cây AVL: chiều cao 4, tổng chiều sâu 49 y hệt, nhưng chi phí dựng 110, và vẫn tiêu 6 phép xoay để đi tới đúng cái cây mà cây thường đã có sẵn.
Tiết kiệm mỗi vòng tìm là 0. Nên điểm hoà vốn ở đây là không bao giờ, và sim in ra đúng chữ đó. Một khoản chi không mua được gì thì bao nhiêu lần tìm cũng không hoàn lại được. Đây là ca mà tự cân bằng thuần tuý là chi phí, và nó không hiếm: dữ liệu đã được ai đó sắp khéo trước khi tới tay bạn là chuyện thường.
Bấm thứ tự xáo với hạt giống 7 thì ra ca thứ ba, ca thú vị nhất. Cây thường cao 5 tầng, cây AVL cũng cao 5. Tổng chiều sâu 52 so với 50, tức mỗi vòng tìm chỉ rẻ hơn 2 bước, trong khi dựng cây đắt hơn 117 so với 37. Điểm hoà vốn nhảy lên 41 lần tìm trên mỗi lần chèn, và sim lại in cả hai phía: ở 40 lần hai bên hoà đúng bằng nhau, cùng 2117 bước, còn ở 41 lần thì cây AVL rẻ hơn 2 bước.
Ba con số 1, "không bao giờ", và 41, trên cùng một bộ khoá. Câu hỏi "cây AVL có đáng không" không có câu trả lời phổ quát, nó có câu trả lời theo thứ tự dữ liệu đi vào và theo tỉ lệ đọc trên ghi.
Kéo núm giá của một phép xoay để thấy nốt một chuyện: điểm hoà vốn còn phụ thuộc vào mô hình chi phí bạn chọn. Trên thứ tự xáo, tính 1 lần ghi liên kết mỗi phép xoay thì hoà vốn ở 34, tính 2 thì 37, tính 3 thì 41, tính 5 thì 48, tính 10 thì 65. Cây thì không đổi một nút nào: giá không đổi được thuật toán, nó chỉ đổi câu trả lời cho câu hỏi "có đáng không".
Trần chiều cao của cây AVL, và một con số bị nói quá
Câu hay được in đậm là "cây AVL giữ chiều cao ở mức O(log n)". Đúng, nhưng nó che mất một chi tiết đáng biết: cây AVL không cân bằng hoàn hảo, và trần của nó cao hơn sàn.
Trần tính được chính xác. Muốn một cây AVL cao h tầng mà ít nút nhất, ta cho một nhánh lệch hết mức luật cho phép: nhánh này cao h−1, nhánh kia cao h−2. Vậy
N(1) = 1, N(2) = 2, N(h) = 1 + N(h-1) + N(h-2)
tức 1, 2, 4, 7, 12, 20, 33, 54, 88, ..., chính là dãy Fibonacci dịch đi: N(h) = Fib(h+2) − 1. Trần chiều cao cho n nút là h lớn nhất thoả N(h) ≤ n.
Với 15 nút: N(5) = 12 ≤ 15 còn N(6) = 20 > 15, nên trần là 5. Sàn là floor(log₂15) + 1 = 4. Vậy cây AVL 15 nút được bảo đảm cao 4 hoặc 5 tầng, không phải bảo đảm cao 4. Cây tìm kiếm thường thì chỉ được bảo đảm 4 tới 15. Thanh đo ở mục 7 của sim vẽ cả ba mốc đó, và vạch đứt ở giữa chính là trần AVL.
Và đây là bằng chứng đo được, không phải suy diễn. Cổng kiểm số quét toàn bộ 9999 hạt giống xáo trên đúng 15 khoá này:
- cây AVL cao thấp nhất 4, cao nhất 5, trung bình 4,95;
- nó chạm sàn 4 tầng đúng 456 lần, và dừng ở 5 tầng 9543 lần;
- cây thường trên cùng 9999 hạt giống: thấp nhất 5, cao nhất 12, trung bình 6,84.
Nghĩa là trong 95,4% số lần, cây AVL đứng ở trần của chính nó chứ không ở sàn. Nó không bao giờ cao hơn cây thường, đúng ở cả 9999 lần. Nhưng nói nó thắng ở mọi lần thì quá tay: nó chỉ thấp hơn hẳn ở 9313 lần, còn 686 lần kia hai cây cao bằng nhau, cùng 5 tầng. Hạt giống 7 mà mục trước vừa lấy làm ví dụ chính là một trong 686 lần hoà đó. Và nó không cho bạn cây tối ưu. Nếu ai đó bảo bạn "AVL luôn cân bằng hoàn hảo" thì đây là 9543 phản ví dụ.
Còn con số 1,44 thì sao? Sách hay viết "chiều cao tối đa của cây AVL khoảng 1,44 × log₂(n)". Nó là xấp xỉ tiệm cận, không phải cái trần. Với 15 nút, 1,44 × log₂(15) ≈ 5,63 trong khi trần thật là 5: xấp xỉ này nằm trên trần, tức an toàn nhưng lỏng. Cổng kiểm số so hai đại lượng đó cho mọi n từ 1 tới 2000 và đo được hai điều:
- ở
nbằng 1, 2 và 4, xấp xỉ ấy nằm thấp hơn trần thật, tức nó không phải một cận trên; - từ
n = 5trở lên nó luôn nằm trên, và vượt trần thật nhiều nhất 1,32 tầng.
Nên cách nói đúng là: 1,44 × log₂(n) bám khá sát trần thật từ phía trên khi n đủ lớn, và công thức Fibonacci ở trên mới là cái trần. Bài này in cả hai cạnh nhau chính vì thế.
Một chi tiết nữa mà thanh đo bóc ra: trần AVL bằng đúng sàn chỉ ở các cỡ 0 tới 6, 8 tới 11, 16 tới 19, và 32. Từ 33 nút trở lên, cho tới 2000, trần luôn cao hơn sàn ít nhất một tầng. Cây 15 nút mà bài đang vẽ đã nằm ngoài danh sách đó rồi.
Còn cây đỏ đen thì sao
Cây đỏ đen giải cùng bài toán bằng một luật lỏng hơn: thay vì đòi hai nhánh chênh nhau không quá một tầng, nó chỉ đòi nhánh dài nhất không quá gấp đôi nhánh ngắn nhất. Luật lỏng hơn nghĩa là ít lần phải xoay hơn khi ghi, đổi lại cây cao hơn một chút nên đọc đắt hơn một chút. Đó là lý do các thư viện chuẩn thường chọn đỏ đen cho map và set nói chung, còn AVL hay xuất hiện ở chỗ đọc nhiều ghi ít.
Nói thẳng: bài này không dạy cây đỏ đen, và sim này không cài đặt nó. Không có nút đỏ nút đen nào trong engine, và câu vừa rồi về việc nó xoay ít hơn là một khẳng định về thuật toán không nằm trong sim, nên cổng kiểm số của bài không chứng minh nó. Cái sim chứng minh được là chuyện khác và hẹp hơn: giữ cân bằng thì tốn bao nhiêu, và tiết kiệm được bao nhiêu.
Sim này đếm gì và không đếm gì
Một phép xoay ở đây là một phép xoay đơn. Xoay kép tính là 2. Nhiều sách tính là 1, và nếu đổi quy ước thì con số 11 ở trên vẫn là 11 (vì cả 11 đều là xoay đơn), nhưng mọi ca LR và RL ở nơi khác sẽ giảm nửa. Đây là quy ước, không phải chân lý.
Mô hình chi phí là một lựa chọn, không phải một phép đo. Bài coi một phép so sánh, một lần cập nhật chiều cao và một lần ghi liên kết là ngang giá. Trên máy thật chúng không ngang. Núm giá phép xoay cho bạn vặn một trong ba, và điểm hoà vốn dịch theo, đúng như nó phải dịch.
Nó đếm phép, nó không đo giây. Một cây thấp hơn không tự động chạy nhanh hơn, vì các nút nằm rải rác trong bộ nhớ. Muốn biết cái nào nhanh hơn trên máy của bạn thì phải đo, và đừng suy ra từ trang này.
Bài này không cài đặt phép xoá của cây AVL. Xoá khó hơn chèn thật sự, chứ không phải khó hơn cho có: một lần chèn cần nhiều nhất một lần cân bằng lại, còn một lần xoá có thể phải cân bằng lại ở mọi tầng trên đường về gốc. Bốn ca xoay vẫn đúng, nhưng xoá còn sinh ra một ca mà chèn không bao giờ gặp, là ca con nặng lệch 0, và cổng kiểm số của bài đã đo được rằng chèn thật sự không gặp nó lần nào trong 1712 lần cân bằng lại.
Cổng kiểm số canh phép tính, không canh lời khẳng định về thế giới. Nó chứng minh được rằng chèn 15 khoá đã sắp vào cây AVL cho chiều cao 4 và tốn đúng 11 phép xoay, và nó so cây của engine với một bản cài đặt AVL thứ hai viết theo lối lặp trên mảng phẳng, khác hẳn lối đệ quy của engine, trên từng cây một. Còn chuyện cây đỏ đen xoay ít hơn thì nó không chứng minh, vì đỏ đen không nằm trong engine.
Cây AVL bắt mỗi nút nhớ chiều cao nhánh của nó, và giữ hệ số cân bằng (chiều cao trái trừ chiều cao phải) của mọi nút trong {−1, 0, +1}. Khi một lần chèn phá luật, đúng bốn hình dạng có thể xảy ra, và hai trong bốn ca cần hai phép xoay đơn chứ không phải một, vì phép xoay đầu chỉ đổi ca chứ chưa chữa. Trên đúng dãy đã sắp đã làm cây tìm kiếm cao 15 tầng, cây AVL giữ chiều cao ở 4, tốn 11 phép xoay, và cho ra đúng cái cây mà bài trước phải sắp tay mới có. Cái giá đo được: dựng cây tốn 145 bước thay vì 105, nhưng một vòng tìm hết 15 khoá tốn 49 thay vì 120, nên chỉ cần 1 lần tìm trên mỗi lần chèn là hoà vốn. Trên thứ tự chèn đã cân sẵn thì hoà vốn là không bao giờ, và trên thứ tự xáo hạt giống 7 thì là 41: cùng một bộ khoá, ba câu trả lời. Và đừng nói AVL cân bằng hoàn hảo: với 15 nút nó bảo đảm 4 hoặc 5 tầng, và trên 9999 hạt giống nó dừng ở 5 tầng tới 9543 lần.
- 1Một nút trong cây AVL có hệ số cân bằng −1. Chuyện gì xảy ra?
- 2Bạn chèn lần lượt 30, 10, 20 vào một cây AVL rỗng. Cần mấy phép xoay đơn, và vì sao?
- 3Trên 15 khoá 10 tới 150, cây AVL dựng tốn 145 bước còn cây thường tốn 105, nhưng tổng chiều sâu là 49 so với 120. Nói gì được về điểm hoà vốn?