Cây tìm kiếm nhị phân, và cái cây bị lệch
Cây tìm kiếm nhị phân, và cái cây bị lệch
Cây tìm kiếm nhị phân hứa cho bạn tìm trong khoảng log n bước. Lời hứa đó có một điều kiện mà hầu như không sách nào in đậm: cây phải cân. Bài này cho bạn bấm một nút để phá lời hứa đó, trên đúng bộ khoá cũ.
Bạn có một đống khoá và muốn hỏi ba câu về chúng: khoá này có không, thêm khoá mới vào đâu, và bỏ một khoá đi thì làm sao. Mảng đã sắp trả lời câu đầu rất nhanh nhờ tìm nhị phân, nhưng hai câu sau thì đắt, vì chèn hay xoá giữa mảng phải dời cả đuôi. Danh sách liên kết thì ngược lại: chèn xoá rẻ, nhưng muốn tìm thì phải quét.
Cây tìm kiếm nhị phân là món đồ hứa lấy cả hai. Mỗi nút giữ một khoá, mọi khoá bên trái nó đều nhỏ hơn, mọi khoá bên phải đều lớn hơn. Đi tìm thì mỗi lần so sánh vứt đi một nhánh, y hệt tìm nhị phân. Chèn thì đi tới chỗ trống rồi treo nút mới vào, không phải dời ai. Nghe rất đẹp.
Có một điều kiện. Cái cây không tự sắp lại. Nó chỉ nhớ đúng thứ tự các khoá đi vào, và hình dạng cuối cùng là hệ quả của thứ tự đó chứ không phải của tập khoá. Nếu khoá đi vào theo thứ tự xấu, cây thành một cái que. Đây không phải chuyện hiếm gặp trong phòng thí nghiệm: dữ liệu đã sắp sẵn là thứ bạn gặp suốt, vì nó vừa được đọc ra từ một tệp đã sắp, hoặc vừa ra khỏi một câu lệnh ORDER BY.
Sim dưới đây dựng cây từ một dãy khoá bạn gõ vào, đi từng bước lúc chèn và lúc tìm, đếm thật mọi con số, và cho bạn bấm một nút để đổi thứ tự chèn trên đúng bộ khoá cũ. 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
d tốn d - 1 phép so sánh.2 · Cây được vẽ ra
✓ đánh dấu nút tìm thấy. Nút tô đậm là nút nằm trên đường đó. Nhãn ×k bên cạnh một nút nghĩa là khoá ấy đã được chèn k lần. Trục ngang là thứ tự duyệt giữa, nên đọc cây từ trái sang phải chính là đọc dãy đã sắp.3 · Cùng bộ khoá, hai thứ tự chèn
| trên đúng 15 khoá này | chèn theo thứ tự cân bằng | chèn theo thứ tự đã sắp |
|---|---|---|
| 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 so sánh để dựng cả cây | 34 | 105 |
4 · Đếm thật
floor(log2(15)) + 1, và log2(15) ≈ 3,91cây này: 4 tầng, cao hơn mức thấp nhất 0 tầng, tức ở vị trí 0,0% trên thangcao nhất có thể: 15 tầngn, tức mỗi tầng đúng một nút5 · Tìm một khoá ✎ sửa được
| bước | so với nút | độ sâu | 110 so với nút này | đi đâu tiếp |
|---|---|---|---|---|
| 1 | 80 | 1 | lớn hơn | sang con phải |
| 2 | 120 | 2 | nhỏ hơn | sang con trái |
| 3 | 100 | 3 | lớn hơn | sang con phải |
| 4 | 110 | 4 | bằng | dừng, đây là nút cần tìm |
6 · Xoá một nút, và ba ca của nó ✎ sửa được
Không con nào. Cắt liên kết từ cha xuống là xong, không có gì phải nối lại.
Kéo đứa con duy nhất lên đúng chỗ của cha. Mọi khoá trong nhánh đó vẫn nằm đúng phía so với ông nội, nên thứ tự không hỏng.
Cái lỗ không con nào lấp được, vì cả hai đều muốn cùng một chỗ. Chỉ hai khoá ngồi vào đó mà không phá thứ tự: khoá lớn nhất bên trái, hoặc khoá nhỏ nhất bên phải. Bài này lấy cái thứ hai, tức nút kế tiếp trong thứ tự duyệt giữa, rồi xoá chính nút đó, việc này dễ vì nút trái nhất chắc chắn không có con trái.
7 · Ba cách duyệt
- Nó đếm phép so sánh, nó không đo giây. Một cây thấp có thể vẫn chậm hơn một mảng đã sắp trên cùng dữ liệu, vì các nút nằm rải rác trong bộ nhớ còn mảng thì liền một dải. Muốn biết cái nào nhanh hơn trên máy của bạn thì phải đo.
- Một phép so sánh ở đây là một lần đối chiếu ba chiều với một nút. Code C hay Java thường viết thành hai phép so sánh hai chiều mỗi vòng lặp, tức nhân đôi mọi con số ở đây. Đó là quy ước, không phải chân lý.
- Khoá trùng không tạo nút mới, nó chỉ tăng số đếm của nút đã có. Cách khác cũng đúng và cũng phổ biến là cho khoá trùng đi về một phía cố định, lúc đó số nút và chiều cao sẽ khác. Đây là một lựa chọn cài đặt, và bài chọn cách thứ nhất.
- Ca xoá hai con lấy nút kế tiếp trong thứ tự duyệt giữa. Lấy nút liền trước cũng đúng y như vậy, và cho ra một cây khác. Sách nào cũng chọn một trong hai rồi hiếm khi nói là mình đã chọn.
- Cây tự cân bằng (AVL, đỏ đen) sinh ra chính là để chữa cái thoái hoá bạn thấy ở đây. Sim này không cài đặt chúng và không chứng minh gì về chúng. Nó chỉ cho thấy vì sao chúng cần tồn tại.
Ở trạng thái mở đầu, sim đang nói gì
Dãy khoá là 15 số: 10, 20, 30 cho tới 150. Thứ tự chèn đang là thứ tự cân bằng, tức là sắp khoá lại, lấy khoá giữa làm gốc, rồi làm y hệt cho nửa trái và nửa phải. Với 15 khoá nó ra dãy này:
80 40 20 10 30 60 50 70 120 100 90 110 140 130 150
Cây thu được có 15 nút và chiều cao 4, tức đường dài nhất từ gốc xuống lá đi qua 4 nút. Nó đầy hoàn hảo: tầng 1 có 1 nút, tầng 2 có 2, tầng 3 có 4, tầng 4 có 8, và 8 nút lá.
Cộng chiều sâu của cả 15 nút lại được 1 + 2×2 + 4×3 + 8×4 = 49, chia cho 15 ra chiều sâu trung bình 3,27. Con số này không chỉ là một thống kê cho vui: chiều sâu của một nút chính bằng số phép so sánh để tìm ra nó, nên 3,27 cũng là chi phí trung bình của một lần tìm trúng, lấy đều trên mọi khoá.
Tìm khoá 110 mất 4 phép so sánh. Bạn đối chiếu với bảng các bước trong sim:
| bước | so với nút | 110 so với nút | đi đâu |
|---|---|---|---|
| 1 | 80 | lớn hơn | sang con phải |
| 2 | 120 | nhỏ hơn | sang con trái |
| 3 | 100 | lớn hơn | sang con phải |
| 4 | 110 | bằng | dừng, tìm thấy |
Một chuyện nhỏ mà đáng nói: một phép so sánh ở đây là một lần đối chiếu ba chiều với một nút, tức hỏi cùng lúc nhỏ hơn, bằng, hay lớn hơn. Code C hay Java thường viết thành hai phép so sánh hai chiều mỗi vòng lặp, tức nhân đôi mọi con số trong bài. Đó là quy ước, không phải chân lý, và đổi quy ước thì mọi con số dịch theo một cách dự đoán được.
Cuối cùng, dựng cả cây tốn 34 phép so sánh. Con số này có một cách tính thứ hai rất gọn: đặt một nút xuống độ sâu d thì phải đi qua d - 1 nút phía trên, nên tổng chi phí dựng cây bằng tổng chiều sâu trừ số nút, tức 49 - 15 = 34.
Bấm một nút, và cây sụp
Bây giờ bấm thứ tự đã sắp. Dãy khoá không đổi một chữ, vẫn đúng 15 số từ 10 tới 150. Chỉ có thứ tự chúng đi vào là đổi.
| trên đúng 15 khoá đó | chèn theo thứ tự cân bằng | chèn theo thứ tự đã sắp |
|---|---|---|
| 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 so sánh để dựng cả cây | 34 | 105 |
Chuyện gì đã xảy ra? Chèn 10 vào cây rỗng, nó thành gốc. Chèn 20, nó lớn hơn 10 nên đi về bên phải. Chèn 30, nó lớn hơn cả 10 lẫn 20 nên lại đi về bên phải, hai lần. Mỗi khoá mới đều lớn hơn mọi khoá đã có, nên nó luôn rơi xuống tận đáy của nhánh phải. Không nút nào có con trái. Cái cây đã trở thành một danh sách liên kết, chỉ khác là mỗi nút còn thêm một con trỏ NULL vô dụng.
Sim khoá số này chặt: với mọi n từ 1 tới 31, chèn theo thứ tự đã sắp cho chiều cao đúng bằng n, cây có đúng một lá, và mọi nút đều có nhiều nhất một con. Chèn theo thứ tự sắp ngược cũng vậy, chỉ đối xứng gương: mọi khoá đều đi về bên trái.
Và đây là chỗ hai chữ O lớn thay đổi ý nghĩa. Tìm kiếm trên cây cân bằng là O(log n). Tìm kiếm trên cái que này là O(n), vì nó đúng là quét tuyến tính, chỉ được vẽ theo chiều dọc. Ba mươi tư phép so sánh để dựng cây thành 105, và 105 chính là 14×15/2, tức tổng 1 + 2 + ... + 14, đúng công thức bậc hai mà bạn đã gặp ở bậc tăng.
Cần nói cho công bằng: cái que không xấu đều. Tìm một khoá nhỏ hơn mọi khoá trong cây, chẳng hạn 5, thì cây thoái hoá chỉ mất 1 phép so sánh, trong khi cây cân bằng mất 4. Nhưng tìm một khoá lớn hơn mọi khoá thì cây thoái hoá mất trọn 15. Nói cách khác, cái que rẻ đúng ở chỗ dữ liệu không nằm, và đắt ở khắp nơi còn lại. Một lần đo may mắn không làm cho hình dạng đó tốt lên.
Chiều cao có sàn và có trần, và cây của bạn nằm giữa
Với n nút thì chiều cao không thể tuỳ tiện. Nó bị kẹp giữa hai giá trị.
Trần dễ thấy: mỗi tầng ít nhất một nút, nên n nút thì nhiều nhất n tầng. Đó chính là cái que ở trên.
Sàn thì phải đếm: tầng d chứa được nhiều nhất 2^(d-1) nút, nên h tầng chứa được nhiều nhất 2^h - 1 nút. Muốn nhét n nút vào thì cần 2^h - 1 ≥ n, và h nhỏ nhất thoả điều đó chính là
chiều cao tối thiểu = floor(log2(n)) + 1
Với 15 nút: log2(15) ≈ 3,91, lấy phần nguyên ra 3, cộng 1 ra 4. Cây cân bằng của chúng ta đang chạm đúng sàn. Cây thoái hoá đang chạm đúng trần.
Cổng kiểm số của bài khoá cái mốc này ở cả hai phía, tại mọi luỹ thừa của 2 mà sim với tới: cây 2^k - 1 nút vừa khít k tầng, thêm đúng một nút nữa thì phải lên k + 1 tầng. Đây là chỗ dấu ≤ bị viết nhầm thành < sẽ sống sót qua hàng trăm khẳng định nếu không ai khẳng định ngay tại mốc. Nó cũng khoá rằng thứ tự chèn cân bằng luôn chạm đúng sàn, với mọi n từ 1 tới 31, chứ không phải chỉ đúng ở con số 15 đẹp đẽ.
Thanh đo trong sim vẽ đúng chuyện đó: bên trái là sàn, bên phải là trần, và cái ghim chỉ chỗ cây hiện tại đang đứng. Cây cân bằng ở mốc 0%, cây thoái hoá ở mốc 100%.
Có một chỗ dễ hiểu lầm mà sim bóc ra được. Kéo thanh số khoá đã chèn về 7, tức mới chèn được nửa dãy cân bằng. Cây lúc đó có 7 nút, sàn của 7 nút là 3 tầng, nhưng cây đang cao 4 tầng. Nghĩa là đi nửa chừng một quá trình chèn cân bằng thì cây chưa hề cân bằng. Lý do: dãy chèn cân bằng chính là dãy duyệt trước của cây đích, mà một đoạn đầu của dãy duyệt trước thì không phải là một dãy chèn cân bằng của riêng nó. Cây chỉ chạm sàn khi khoá cuối cùng đã vào.
Còn xáo trộn ngẫu nhiên thì sao
Câu trả lời quen thuộc cho chuyện thoái hoá là "xáo dữ liệu trước khi chèn". Bấm thứ tự xáo trong sim và nhìn con số.
Với hạt giống 7, cây cao 5 tầng, chiều sâu trung bình 3,47. Tốt hơn cái que rất nhiều, và chỉ hơn cây cân bằng đúng một tầng.
Nhưng đừng dừng ở một hạt giống. Cổng kiểm số quét toàn bộ 9999 hạt giống hợp lệ trên đúng 15 khoá này, và kết quả đo được là:
- chiều cao thấp nhất trong 9999 lần là 5;
- chiều cao cao nhất là 12;
- chiều cao trung bình là 6,84.
Hai điều rút ra, và cả hai đều là số đo chứ không phải lời hứa. Thứ nhất, xáo luôn thắng thứ tự đã sắp, vì 12 vẫn nhỏ hơn 15, và điều đó đúng ở cả 9999 lần. Thứ hai, xáo không bao giờ chạm sàn 4, ở không lần nào trong 9999. Nghĩa là "cứ xáo là ổn" là một câu nói về trung bình, không phải một bảo đảm. Bạn vẫn có thể xui, và trong bài toán thật thì bạn thường không được quyền xáo, vì khoá đi vào theo thứ tự người dùng gõ chứ không theo thứ tự bạn chọn.
Duyệt giữa, và vì sao nó luôn ra dãy đã sắp
Có ba cách đi hết một cây, khác nhau ở chỗ đặt việc "đọc chính nút này" vào đâu. Cả ba đều là đệ quy ba dòng.
| tên | thứ tự làm | trên cây cân bằng ở trạng thái mở đầu |
|---|---|---|
| duyệt trước | nút, trái, phải | 80 40 20 10 30 60 50 70 120 100 90 110 140 130 150 |
| duyệt giữa | trái, nút, phải | 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 |
| duyệt sau | trái, phải, nút | 10 30 20 50 70 60 40 90 110 100 130 150 140 120 80 |
Nhìn dòng giữa. Nó là dãy đã sắp. Đây không phải trùng hợp trên bộ khoá này, nó là tính chất định nghĩa của cây tìm kiếm: mọi khoá bên trái một nút đều nhỏ hơn nó, mọi khoá bên phải đều lớn hơn, nên đọc hết nhánh trái rồi tới nút rồi tới nhánh phải thì không thể ra thứ tự nào khác. Đổi thứ tự chèn bao nhiêu lần đi nữa, xoá bao nhiêu nút đi nữa, dòng giữa vẫn tăng dần. Chỉ hai dòng kia đổi. Cổng kiểm số quét toàn bộ lưới cây của bài và khẳng định điều này trên từng cây một, không phải bằng một lá cờ mà bằng cách so sánh với dãy khoá đã sắp, từng phần tử.
Hai chuyện nữa nằm trong bảng mà mắt thường dễ lướt qua.
Dãy duyệt trước chèn lại thì dựng đúng cái cây cũ. Bạn để ý là dòng duyệt trước ở trên trùng khít với thứ tự chèn cân bằng. Không ngẫu nhiên: khoá đầu tiên của dãy duyệt trước là gốc, đoạn tiếp theo toàn khoá nhỏ hơn gốc nên dựng lại đúng nhánh trái, phần còn lại dựng lại đúng nhánh phải, cứ thế xuống. Cổng kiểm số khoá điều này trên toàn bộ lưới cây chứ không riêng ca này. Đây là cách người ta cất một cây ra tệp rồi nạp lại.
Còn dãy duyệt giữa chèn lại thì dựng ra cây tệ nhất. Vì dãy duyệt giữa đã sắp, mà chèn dãy đã sắp thì ra cái que. Cây cao 4 nạp lại theo dòng giữa sẽ thành cây cao 15. Cùng một cây, cất ra hai cách, nạp lại ra hai kết quả khác hẳn nhau.
Trên cây thoái hoá, ba dòng đó co lại còn hai: duyệt trước và duyệt giữa trùng nhau, vì không có nhánh trái nào để đi trước, còn duyệt sau đúng bằng dãy đó đảo ngược.
Xoá một nút, phần khó nhất và hay bị bỏ qua nhất
Chèn thì dễ, ai cũng viết được. Xoá mới là chỗ code thật hay hỏng, vì nó có ba ca và ca thứ ba không hiển nhiên.
Ca 1, nút lá. Không con nào. Cắt liên kết từ cha xuống là xong. Trong sim, bấm xoá khoá 10 ở trạng thái mở đầu: nó là lá, cây còn 14 nút, không ai phải dời chỗ.
Ca 2, một con. Kéo đứa con duy nhất lên đúng chỗ của cha. Không phá thứ tự, vì mọi khoá trong nhánh đó vốn đã nằm đúng phía so với ông nội. Trong sim, sau khi xoá 10 thì nút 20 chỉ còn một con là 30, nên xoá 20 lúc này rơi vào ca 2.
Ca 3, hai con. Đây là ca thật sự khó. Cái lỗ không con nào lấp được, vì cả hai đều muốn cùng một chỗ. Chỉ đúng hai khoá trên đời ngồi vào đó mà không phá thứ tự: khoá lớn nhất bên trái, hoặc khoá nhỏ nhất bên phải. Đó chính là hai hàng xóm của khoá bị xoá trong dãy đã sắp.
Bài này lấy cái thứ hai, tức nút kế tiếp trong thứ tự duyệt giữa, hay nói cách khác là nút trái nhất của nhánh phải. Kéo khoá đó lên lấp lỗ, rồi đi xoá chính nút gốc của nó, và việc đó dễ vì một nút trái nhất chắc chắn không có con trái, nên nó rơi về ca 1 hoặc ca 2.
Trong sim, ở trạng thái mở đầu, xoá 40. Nó có hai con là 20 và 60. Nút kế tiếp của 40 trong dãy đã sắp là 50, và 50 đúng là khoá nhỏ nhất của nhánh phải. Sau khi xoá:
- cây còn 14 nút, và 50 giờ ngồi ở độ sâu 2, đúng chỗ 40 vừa nằm;
- chiều cao vẫn 4;
- tổng chiều sâu tụt từ 49 xuống 45, nên chiều sâu trung bình thành
45/14, tức 3,21; - duyệt giữa vẫn tăng dần, chỉ thiếu số 40.
Nếu bạn muốn thấy cả ba ca liên tiếp thì xoá lần lượt 10, rồi 20, rồi 40. Sim ghi rõ ca của từng lần. Sau ba lần cây còn 12 nút, tổng chiều sâu 37, chiều sâu trung bình 3,08.
Vài mốc biên mà code thật hay quên, và sim cho bạn bấm thử hết:
- Xoá gốc của cây chỉ có gốc. Bấm bộ khoá 1 khoá rồi xoá 42. Đây là ca 1, và kết quả là cây rỗng, không phải một cây có gốc
NULLmà vẫn đếm là 1 nút. Sau đó chiều cao 0 và mọi phép tìm tốn 0 phép so sánh. - Xoá gốc của cây lớn. Đây là chỗ code hỏng nhiều nhất, vì gốc không có cha để vá liên kết. Xoá 80 ở trạng thái mở đầu: ca 3, và 90 lên làm gốc mới.
- Xoá khoá không có. Xoá 115 chẳng hạn. Không có gì đổi, và điều đó phải đúng theo nghĩa mạnh: cây trả về phải y hệt cây cũ, không phải một cây trông giống.
- Xoá trên cây rỗng. Không nổ, không âm thầm, sim ghi rõ là cây đang rỗng.
Cổng kiểm số chạy toàn bộ phép xoá có thể có, tức xoá lần lượt từng khoá của từng cây trong lưới, 375 lần, và đối chiếu với một bản cài đặt xoá thứ hai viết theo lối lặp trên mảng chỉ số, hoàn toàn khác lối đệ quy của engine. Ngoài ra sau mỗi lần xoá nó kiểm ba bất biến: cây vẫn là cây tìm kiếm, số nút giảm đúng 1, và mọi khoá còn lại vẫn tìm được.
Khoá trùng, và một lựa chọn phải nói ra
Chèn một khoá đã có thì làm gì? Sách này không thống nhất, và cả hai cách đều đúng.
Bài này chọn: khoá trùng không tạo nút mới, nút đã có chỉ tăng số đếm của nó. Bấm bộ khoá có khoá trùng trong sim, dãy là 50 30 70 30 50 30 90. Kết quả: 4 nút, nhưng 7 khoá đã chèn, trong đó 3 lần trùng. Nút 30 mang nhãn ×3, nút 50 mang ×2. Ba con số đầu không phụ thuộc thứ tự chèn, còn chiều cao thì có: ở thứ tự cân bằng (mặc định) nó là 3, còn nếu bạn vừa bấm thứ tự đã sắp ở mục trên thì nút bộ khoá không đặt lại thứ tự, nên bạn sẽ thấy 4.
Cách còn lại, cũng rất phổ biến, là cho khoá trùng đi về một phía cố định, thường là phải. Lúc đó chèn 30 ba lần sẽ tạo ba nút xếp thành chuỗi, và chiều cao lẫn số nút đều khác. Không cách nào sai. Nhưng nếu bạn không nói mình chọn cách nào thì mọi con số bạn công bố đều mơ hồ, và đó là lý do đoạn này tồn tại. Chiều sâu trung bình ở đây tính trên các nút khác nhau, mỗi nút một lần, bất kể nó mang số đếm bao nhiêu.
Vậy sửa thế nào
Nếu vấn đề là thứ tự chèn quyết định hình dạng, thì cách chữa phải là làm cho cây tự sắp lại sau mỗi lần chèn hay xoá. Đó chính xác là việc mà cây AVL và cây đỏ đen làm: chúng giữ thêm một chút thông tin ở mỗi nút, và khi hình dạng lệch quá mức cho phép thì xoay lại vài liên kết, tốn thêm O(1) mỗi thao tác nhưng ép chiều cao ở lại mức O(log n) bất kể thứ tự chèn.
Nói thẳng: bài này không dạy chúng, và sim này không cài đặt chúng. Không có phép xoay nào trong engine, không có hệ số cân bằng nào, không có nút đỏ nút đen nào. Sim chỉ làm đúng một việc là cho bạn thấy vì sao chúng cần tồn tại. Khi bạn gặp lại AVL hay đỏ đen ở buổi sau, câu hỏi bạn nên mang theo không phải "phép xoay hoạt động ra sao" mà là "nó đang chặn cái gì", và cái đó thì bạn vừa nhìn thấy: chiều cao 4 thành 15 sau đúng một cú bấm.
Cũng nói thêm cho khỏi nhầm: chữ "cây" trong tin học không phải lúc nào cũng là cây tìm kiếm. Cây quyết định trong học máy cũng là cây nhị phân, cũng chia đôi ở mỗi nút, nhưng nó chia theo một thuộc tính của dữ liệu chứ không theo thứ tự của một khoá, và nó được dựng bằng cách chọn chỗ chia tốt nhất chứ không phải bằng cách chèn lần lượt. Cùng một hình vẽ, hai việc khác hẳn nhau.
Sim này đếm gì và không đếm gì
Nó đếm phép so sánh, nó không đo giây. Một cây thấp vẫn có thể chậm hơn một mảng đã sắp trên cùng dữ liệu, vì các nút của cây nằm rải rác khắp bộ nhớ còn mảng thì liền một dải: bộ nhớ đệm của máy nạp sẵn cả dải, còn cây thì gần như mỗi bước một lần đợi. 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.
Chiều sâu trung bình ở đây coi mọi khoá được hỏi đều nhau. Dữ liệu thật hiếm khi vậy: vài khoá bị hỏi liên tục, phần lớn thì không ai đụng tới. Nếu bạn biết phân bố truy vấn thì cây tốt nhất không còn là cây thấp nhất nữa, mà là cây đặt khoá hay bị hỏi lên gần gốc. Đó là một bài toán khác và sim này không chạm tới.
Cổng kiểm số của bài 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á theo thứ tự đã sắp cho chiều cao 15, và rằng cây AVL sẽ chặn được chuyện đó thì nó không chứng minh, vì AVL không nằm trong engine. Câu đó là chuyện của buổi sau.
Cây tìm kiếm nhị phân 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 cho chiều cao 4, chiều sâu trung bình 3,27, tìm khoá 110 mất 4 phép so sánh; chèn theo thứ tự đã sắp cho chiều cao 15, chiều sâu trung bình 8,00, và cùng khoá đó mất 11 phép so sánh. Cái cây đã trở thành danh sách liên kết, và O(log n) đã trở thành O(n). Chiều cao luôn kẹp giữa floor(log2(n)) + 1 và n, tức 4 và 15 ở đây, và hai thứ tự chèn kia đang đứng đúng ở hai đầu. Duyệt giữa thì bất biến: nó luôn cho dãy đã sắp, dù cây có méo cỡ nào. Xoá có ba ca, và ca hai con phải lấy nút kế tiếp trong thứ tự duyệt giữa. Cây tự cân bằng như AVL hay đỏ đen sinh ra để chặn đúng cái thoái hoá này, và bài này chỉ cho bạn thấy vì sao chúng cần tồn tại, chứ không dạy chúng.
- 1Bạn chèn 15 khoá 10, 20, 30, ..., 150 vào một cây tìm kiếm nhị phân theo đúng thứ tự đó. Cây thu được cao bao nhiêu tầng, và tìm khoá 110 mất bao nhiêu phép so sánh?
- 2Bạn xoá một nút có ĐỦ HAI con khỏi cây tìm kiếm nhị phân. Khoá nào được kéo lên lấp chỗ trống?
- 3Cây tìm kiếm nhị phân có 15 nút. Câu nào đúng về chiều cao của nó?