Các tập tin đã được xắp xếp thứ tự, các tập tin với thứ tự ngược, các tập các khoá lớn, nhỏ xen lẫn nhau hay các tập tin với sự phân đoạn lớn có cấu trúc đơn giản có thể làm thuật toán tìm trên cây hoạt động rất tồi.

Với thuật toán QuickSort, cái mà chúng ta cần để cái tiến tình huống là sắp xếp lại để có trường hợp ngẫu nhiên: bằng cách chọn một phần tử phân hoạch ngẫu nhiên, chúng ta có thể dựa vào quy luật xác xuất để tránh khỏi trường hợp xấu nhất. Với tìm kiếm trên cây nhị phân thì may mắn hơn, bởi vì chúng ta có thể làm tốt hơn nhiều; có một kỹ thuật tổng quát cho phép chúng ta bảo đảm trường hợp xấu nhất sẽ không xuất hiện. Kỹ thuật này gọi là Cân bằng đã được dùng làm cơ sở cho nhiều thuật toán khác nhau về “cây cân bằng”. Chúng ta sẽ xem xét kỹ một thuật toán thuộc loại đó và cùng nhau thảo luận tóm tắt về sự liên quan của nó đối với các phương pháp khác.

Phải nói rằng: việc cài các thuận toán cây cân bằng là một việc “nói dễ hơn làm”. Thông thường khái niệm tổng quát trước một thuật toán thì dễ dàng mô tả, nhưng cài đặt nó lại là hàng loạt trường hợp đặc biệt và đối xứng. Bài viết này không chỉ đưa ra một phương pháp tìm kiếm quan trọng mà còn minh hoạ mối quan hệ đẹp mắt giữa một sự mô tả “cấp cao” (high-level) và một chương trình Pascal cấp thấp (low-level) khi cài đặt một thuật toán.

Top - Down 2-3-4 Trees (Các cây 2-3-4 từ trên xuống)

Các cây 2-3-4 là gì?

Trước khi tìm hiểu về thuật toán, chúng ta cần hiểu rõ thế nào là một cây 2-3-4 từ trên xuống? Để các bạn tiện hình dung, tôi xin đưa ra một hình ảnh của cây 2-3-4 như sau:

(Hình 1. Một 2-3-4 cây)

Để khử trường hợp xấu nhất cho cây tìm kiếm nhị phân, chúng ta cần một vài linh động trong cấu trúc dữ liệu sẽ dùng. Để có sự linh động này, chúng ta hãy giả sử rằng các nút trong cây của chúng ta có thể chứa nhiều hơn một khoá. Cụ thể hơn chúng ta sẽ thừa nhận các 3-nút và 4-nút mà có thể chứa tương ứng hai và ba khoá. Có thể mô tả chi tiết như sau:

Một 3-nút có 3 liên kết ra khỏi nó

+ Một liên kết dành cho tất cả các mẩu tin có khoá nhỏ hơn cả hai khoá của nó

+ Một cho các mẩu tin với các khoá nằm giữa hai khoá của nó

+ Một cho tất cả các mẩu tin với các khoá lớn hơn cả hai khóa của nó.

Tương tự như vậy, một 4-nút có 4 liên kết đi ra khỏi nó, mỗi liên kết dành cho một đoạn trong các đoạn được định nghĩa bởi 3 khoá của nó. (Các nút trong một cây tìm kiếm nhị phân chuẩn có thể gọi là 2-nút: một khoá và hai liên kết). Chúng ta sẽ thấy một số phương pháp hiệu quả để định nghĩa và cài đặt các thao tác cơ sở trong các nút mở rộng này; bây giờ giả sử chúng ta có thể sử dụng chúng một cách hình thức và xem việc tạo nên cây như thế nào.

Hãy để ý hình ví dụ trên là một cây 2-3-4, cây chứa khoá A S E A R C H I N. Dễ dàng để thấy được cách tìm kiếm trên một cây như thế. Ví dụ, để tìm khoá G, chúng ta sẽ dò theo liên kết giữa của gốc, bởi vì G ở giữa E và R, kế đến kết thúc quá trình tìm kiếm không thành công ở liên kết trái từ nút H, I, và N.

(Hình 2.Ví dụ Chèn (khoá G) vào một 2-3-4 vây)

Để chèn một nút mới vào một 2-3-4 cây, chúng ta thực hiện một quá trình tìm kiếm không thành công và sau đó móc nút mới vào. Nếu kết thúc quá trình tìm kiếm ở một 2-nút thì chỉ cần sửa nó thành 3-nút. Ví dụ X có thể được thêm vào cây trong (hình 2) bằng cách thêm nó (và một liên kết khác) vào nút chứa S.

Tương tự một 3-nút có thể dễ dàng sửa thành 4-nút. Nhưng chúng ta sẽ làm gì để chèn một nút mới vào một 4-nút? Cụ thể là làm thế nào để chèn G vào cây trong hình 1?

Một khả năng là treo nó vào như một con mới bên phải của nhất của 4-nút chứa H, I và N. Nhưng một cách giải quyết tốt hơn được cho trong hình 2: trước tiên phân rã 4-nút thành 2-nút và chuyển một trong các khoá của nó lên cha nó, 4-nút chứa H, I, N được tách thành 2-nút (một chứa H, một chứa N), “khoá giữa I” được đẩy lên 3-nút chứa E và R để đổi nó thành 4-nút.Kế đó là nơi ở của G là 2-nút chưa H.

Vấn đề nảy sinh ở chỗ nếu chúng ta tách một 4-nút mà cha của nó cũng là 4-nút thì sao? Một phương pháp là cũng sẽ tách cha nó, nhưng chúng ta có thể làm mãi điều này cho đến gốc của cây. Một giải pháp dễ hơn là luôn bảo đảm cha của bất kỳ nút nào đều không là 4-nút bằng cách tách hết mọi 4-nút của cây từ trên xuống.

Chúng ta có thể thấy rằng dễ dàng chèn các nút mới vào các 2-3-4 cây bằng cách thực hiện quá trình tìm kiếm và tách các 4-nút của cây từ trên xuống. Cụ thể như trong hình 3 phía dưới: mỗi khi chúng ta gặp một 2-nút được nối với một 4-nút, chúng ta chuyển đổi nó thành một 3-nút được nối với hai 2-nút, và mỗi khi chúng ta chạm phải một 3-nút được nối với một 4-nút, chúng ta nên chuyển nó thành một 4-nút nối với hai 2-nút.

Thao tác “tách” này làm việc nhiều bởi vì không chỉ các khoá mà cả các con trỏ cũng có thể bị di chuyển. Hai 2-nút có cùng số con trỏ (bốn con trỏ) như một 4-nút, nên quá trình tách có thể làm mà không thay đổi bất kỳ cái gì bên dưới nút được tách. Và một 3-nút không thể được thay đổi thành 4-nút bằng cách chỉ thêm vào một khoá khác; cũng phải cần thêm một con trỏ nữa (trường hợp này con trỏ trợ giúp được cung cấp bởi thao tác tách). Mỗi chuyển đổi một khoá từ một 4-nút lên cha của nó và xây dựng lại liên kết tương ứng.

HÌnh 3 - Tách các 4-nút

Chú ý rằng chúng ta không cần lo ngại về nút cha là một 4-nút, bởi vì các chuyển đổi của chúng ta bảo đảm rằng khi chúng ta đi qua mỗi nút trong cây thì luôn đi ra khỏi một nút không phải là 4-nút. Cụ thể khi chúng ta đi ra khỏi đáy của cây thì chúng ta không ở trên một 4-nút, và chúng ta có thể chèn một nút mới trực tiếp vào cây bằng cách chuyển đổi một 2-nút thành 3-nút hay một 3-nút thành 4-nút. Trong quá trình chèn thêm nút, chúng ta quy ước tách 4-nút “ảo” ở đáy mà sắp sửa nhận thêm một nút mới. Bất cứ khi nào gốc của cây trở thành một 4-nút chúng ta sẽ tách nó thành ba 2-nút. Trường hợp này sẽ làm cho cây cao thêm một tầng.

Thuật toán được phác thảo cung cấp một phương pháp để tìm kiếm và chèn trong 2-3-4 cây; bởi vì các 4-nút được tách tử đỉnh trở xuống, cây nói trên cũng được gọi là cây 2-3-4 từ trên xuống. Một điều rất lý thú là mặc dù chúng ta đã không tìm đến sự cân bằng nhưng kết quả lại là một cây hoàn toàn cân bằng! Chúng ta có thể dễ dàng hình dung cách hoạt động và hướng đi của thuật toán này qua sự mô tả khi xây dựng một cây 2-3-4 như sau: (Xuất phát điểm sẽ là cây trong hình 2 ở trên và chúng ta sẽ chèn X vào cây này)

*** Các thao tác tìm kiêm cây 2-3-4 chứa N nút không bao giờ duyệt nhiều hơn lgN+1 nút.

Khoảng cách từ gốc tới mỗi nút ngoài là như nhau: các thao tác chuyển đổi mà chúng ta thực hiện không ảnh hưởng đến khoảng cách từ một nút bất kỳ tới gốc, ngoại trừ khi chúng ta tách nút gốc.Trong trường hợp này khoảng cách từ tất cả các nút tới gốc được tăng lên một. Nếu tất cả các nút là 2-nút, kết quả đã khẳng định đúng bởi vì cây giống như cây nhị phân đầy đủ; nếu có các 3-nút và 4-nút thì chiều cao chỉ có thể ngắn hơn.

*** Các thao tác chèn vào cây 2-3-4 chứa N nút cần ít nhất lgN+1 nút trong trường hợp xấu nhất và dường như số lần tách nút trung bình thì nhỏ hơn .

Trường hợp xấu nhất có thể xảy ra là tất cả các nút trên đường dẫn tới nơi chèn đều là 4-nut, tất cả chúng sẽ bị tách. Nhưng trong một cây được xây dựng từ một hoán vị ngẫu nhiên của N phần tử, không những trường hợp xấu nhất này ít xuất hiện mà ngay cả các thao tác tách về mặt trung bình cũng ít cần đến bởi vì không có nhiều 4-nút trong cây. Sự mô tả ở trên đã đủ để định nghĩa một thuật toán dùng 2-3-4 cây để tìm kiếm, thuật toán này bảo đảm sự thực hiện tốt trường hợp xấu nhất. Tuy nhiên chúng ta chỉ thực hiện được phân nửa một cài đặt thực sự. Mặc dù có thể viết một thuật toán thực hiện các sự chuyển đổi trên các dạng dữ liệu khác nhau biểu diễn cho 2-, 3-, và 4-nút, nhưng mọi việc sẽ bị gượng ép trong biểu diễn trực tiếp này (Nếu các bạn chưa tin điều này hãy thử cố gắng cài đặt ngay cả trường hợp đơn giản của các sự chuyển đổi hai nút). Hơn nữa, việc thao tác trên các cấu trúc nút quá phức tạp sẽ làm các thuật toán hoạt động chậm hơn thuật toán trên cây nhị phân thông thường. Mục đích chính của sự cân bằng là cung cấp “sự bảo hiểm” để chống lại trường hợp xấu nhất, nhưng lại vô tình bị trả giá quá đắt sự “bảo hiểm” đó trong mỗi lần hoạt động. Vậy có cách nào giản đơn hơn để biểu diễn 2-, 3-, và 4-nút mà cho phép các chuyển đổi được làm tốt và trả giá ít hơn tìm kiếm trên cây nhị phân? Chúng ta sẽ xét một khái niệm cây rất hay đó là: Red-Black trees.

Red-black trees (Các cây đỏ đen)

Chúng ta có thể biểu diễn 2-3-4 cây như một cây nhị phan chuẩn (chỉ có các 2-nút) bằng cách dùng một bit trợ giúp cho mỗi nút. Ý tưởng là biểu diễn các 3-nút và 4-nút như các cây nhị phân nhỏ với các liên kết “đỏ”

School@net