Ta sẽ thấy rõ hơn ở hình dưới đây:


Biểu diễn Đỏ-Đen của các 3-nút và 4-nút

Các 4-nút được biểu diễn bởi ba 2-nút được nối bởi các liên kết đỏ và các 3-nút được biểu diễn bởi hai 2-nút được nối bởi một liên kết đỏ (các liên kết đỏ được biểu hiện trên hình là các nét đậm).

Ở phần trước chúng ta đã xây dựng một cây 2-3-4. Hãy để ý hình sau:


Ví dụ về một cây đỏ-đen

Rõ ràng đây là một biểu diễn của cây cuối cùng trong hình 3 (số báo trước). Nếu chúng ta bỏ đi các liên kết đỏ và kéo tất cả các nút lên ngang hàng nhau thì sẽ thấy ngay đó là hình cuối cùng của hình 3. Bit trợ giúp cho mỗi nút được dùng để lưu trữ màu cho liên kết trỏ tới nút đó: ta sẽ gọi các cây 2-3-4 biểu diễn bằng phương pháp này là các CÂY ĐỎ-ĐEN.

Với phương pháp này, mỗi 3-nút được xác định bởi các thuật toán được mô tả bên dưới. Có nhiều cây đỏ đen tương ứng với mỗi cây 2-3-4.

Những cây này có các tính chất cấu trúc được suy ra từ cách định nghĩa chúng. Một ví dụ cụ thể là: sẽ không bao giờ có hai liên kết Đỏ kề nhau dọc theo bất kỳ con đường nào từ gốc tới một nút ngoài, và tất cả các con đường đều có số liên kết Đen bằng nhau.

Chú ý rằng có thể một con đường (luân phiên đen-đỏ) dài gấp hai lần một con đường khác (tất cả đen), nhưng tất cả các độ dài đường đi đều xấp xỉ logN.

Một chức năng nổi bật của cây nói trên là vị trí của các khoá bằng nhau. Thuật toán trên cây cân bằng sẽ làm cho các mẩu tin có khoá bằng với một nút cho trước rơi vào cả hai phía của nút đó; ngược lại, trường hợp không cân bằng có thể gây ra một chuỗi dài các bằng nhau. Điều này cũng có nghĩa là chúng ta không thể tìm thấy tất cả các nút với một khoá đã cho bằng cách gọi lặp lại các thủ tục tìm kiếm. Tuy nhiên, điều này không quan trọng bởi vì đối với tất cả các nút trong cây con mà có cùng khoá với nút gốc của cây con thì đều có thể được tìm thấy bởi một thủ tục đệ quy đơn giản giống như thủ tục dưới đây:

++++++++++++++++



+++++++++++++++++

Một tính chất rất đẹp của các cây đỏ-đen là thủ tục treesearch để tìm kiếm trên cây nhị phân chuẩn sẽ không cần sửa đổi (ngoại trừ đối với các khoá bằng nhau mà ta đã xét bên trên). Chúng ta sẽ cài đặt các màu liên kết bằng cách thêm một trường (red) vào mỗi nút.

Red kiểu boolean; nhận giá trị true nếu liên kết trỏ tới nút là đỏ và nhận giá trị false nếu liên kết là đen;

Thủ tục treesearch không bao giờ truy xuất tới trường red. Thông thường mỗi khoá được chèn vào chỉ một lần nhưng có thể được tìm kiếm nhiều lần, do đó chúng ta cải tiến được thời gian tìm kiếm bởi vì cây cân bằng và không cần thêm các thao tác để duy trì sự cân bằng của cây trong suốt các quá trình tìm kiếm.

++++++++++



++++++++++++

Hơn nữa khả năng tách rất hiếm trong quá trình chèn, chúng ta chỉ làm thêm một số việc khi thấy các 4-nút, và trong cây không có nhiều 4-nút bởi vì chúng ta luôn tách chúng ra. Trong cài đặt sau đây của thủ tục chèn, ta thấy chỉ cần một kiểm tra trợ giúp trong vòng lặp (nếu một nút có hai con đỏ, nó là một bộ phận của một 4-nút).

++++++++++++



++++++++++++

Trong chương trình này, x di chuyển hướng xuống dưới cây như trước đây và gg, g và p được lưu để trỏ đến ông cố, ông nội và cha của x ở trong cây. Để có thể thấy tại sao cần các liên kết này, hãy xem việc thêm Y vào cây ở hình dưới đây.


Hình 1- Chèn Y vào một cây đỏ-đen

Khi gặp nút ngoài bên phải của 3-nút chứa S và X, gg là R, g là S, và P là X. Bây giờ Y phải được thêm vào để tạo một 4-nút chứa S, X, và Y, kết quả như ta đã thấy trên hình.

Chúng ta cần một con trỏ tới R (gg) bởi vì liên kết phải của R phải được thay đổi để trỏ tới X, chứ không phải S. Để thấy chính xác điều này, chúng ta cần quan sát thao tác của thủ thục split. Hãy xem biểu diễn đỏ-đen cho hai phép biến đổi mà chúng ta phải thực hiện: nếu chúng ta một 2-nút nối tới một 4-nút, thì chúng ta sẽ đổi chúng thành một 3-nút nối tới một 4-nút, thì chúng ta nên đổi chúng thành một 4-nút nối với hai 2-nút. Khi một nút mới được thêm vào đáy, nó được xem là nút giữa của một 4-nút ảo (nghĩa là suy nghĩ về z như red mặc dù điều này không được kiểm tra một cách tường minh).

Sẽ dễ dàng chuyển đổi nếu chúng ta gặp một 2-nút nối với một 4-nút, và cũng như vậy nếu chúng ta có một 3-nút nối với một 4-nút theo cách nối bên phải như hình dưới


Hình a. Tách các 4-nút

Như vậy, thủ tục split bắt đầu bằng cách đánh dấu x là đỏ và con của x là đen.

Trường hợp chúng ta gặp một 3-nút nối tới 4-nút sẽ có hai trường hợp xảy ra. Trong những trường hợp này, việc tách các 4-nút giữ lại hai nút đỏ trên cùng một hàng, đây là một trường hợp không hợp lệ cần phải được giải quyết. Trường hợp này được kiểm tra dễ dàng trong chương trình: chúng ta phải đánh dấu x là đỏ, vì vậy nếu cha p của x cũng đỏ thì chúng ta phải làm thêm thao tác. Tình huống này không tồi bởi vì chúng ta có ba nút được nối bằng các liên kết đỏ, tất cả những gì mà chúng ta cần làm là chuyển cây sao cho các liên kết đỏ chỉ xuống dưới từ cùng một nút.

Không quá khó vì chúng ta có một thao tác đơn giản để có được điều mong muốn. Ta hãy bắt đầu với trường hợp dễ hơn trong hai trường hợp nói trên, trường hợp đầu tiên:


Hình b. Tách các 4-nút, cần đến phép quay

Các liên kết đỏ có cùng hướng. Vấn đề là 3-nút được hướng theo phương ngược lại, nên chúng ta xây dựng lại cây để đổi hướng của 3-nút, và do đó đưa trường hợp này về trường hợp thứ hai trong hình (Hình a) chỉ cần đổi màu của x và các con của nó là xong. Việc xây dựng lại cây để đổi hướng một 3-nút bao gồm thay đổi ba liên kết như hình dưới:


(Hình 2. Quay một 3-nút trong Hình 1)

Có thể thấy rằng hình trên giống như Hình 1 nhưng nó có 3-nút chứa N và R được quay. Liên kết trái của R được thay đổi để trỏ tới P, liên kết phải của N được thay đổi để trỏ tới R, và liên kết phải của I được thay đổi để trỏ tới N. Cũng vậy, cẩn thận chú ý rằng màu của hai nút cũng bị đổi.

Thao tác quay đơn (single rotation) được định nghĩa trên cây tìm kiếm nhị phân bất kỳ (nếu chúng ta không chú ý các thao tác về màu) và là cơ sở cho nhiều thuật toán về cây cân bằng, bởi vì nó giữ gìn đặc trưng cần thiết của cây tìm kiếm và là sự sửa đổi địa phương bao gồm chỉ ba thao tác thay đổi liên kết. Tuy nhiên một chú ý rất quan trọng là một thao tác quay đơn không nhất thiết cải tiến sự cân bằng của cây. Trong Hình 2 thao tác quay tất cả các nút bên trái của N gần gốc hơn một tầng so với trước đó, nhưng tất cả các nút bên phải của R thì bị thấp hơn một tầng, trường hợp này làm cây ít cân bằng hơn. Các cây 2-3-4 từ trên xuống có thể được xem đơn giản như một phương tiện quy ước để đồng nhất các thao tác quay đơn để cải tiến sự cân bằng.

Việc làm một thao tác quay đơn bao gồm sự sửa đổi cấu trúc của cây, và điều này phải được làm cẩn thận. Giả sử rằng các liên kết y, c, và gc trỏ tương ứng tới I, R, và N trong Hình 1. Khi đó có sự chuyển đổi tới Hình 2 được gây ra bằng cách thay đổi liên kết:



Ta có ba trường hợp tương tự khác: 3 nút có thể được định hướng theo cách khác, hay nó có thể là bên trái của y. Một phương pháp truyền thống để xử lý bốn trường hợp khác nhau là dùng việc tìm kiếm khoá v để “tìm trở lại” con trực tiếp c và cháu nội gc của nút y (chúng ta đã biết rằng chỉ định lại hướng một 3-nút nếu tìm đến nút đáy). Nhờ điều đó mà chúng ta có chương trình đơn giản hơn phải nhớ không những hai liên kết tương ứng với c và gc mà còn phải nhớ chúng nó là các liên kết phải hay liên kết trái trong suốt quá trình tìm kiếm. Chúng ta có hàm sau đây để định hướng lại một 3-nút dựa theo con đường tìm kiếm cho v mà cha của nó là y:

+++



+++

Nếu y trỏ tới gốc, c là liên kết phải của y và gc là liên kết trái của c, điều này thực hiện chính xác các chuyển đổi liên kết cần để sản sinh ra cây trong hình 2 từ cây trong Hình 1. Độc giả có lẽ muốn kiểm tra các trường hợp khác. Hàm này trả về liên kết tới đỉnh của 3-nút, nhưng lại không làm chính thao tác đổi màu.

Do đó, để xử lý trường hợp thứ ba cho thủ tục split (Hinh b), chúng ta có thể làm đỏ g, cho x nhận giá trị rotate (v.gg), và làm đen x. Thao tác này đổi hướng của 3-nút bao gồm hai nút được trỏ tới bởi g và p, đồng thời nó cũng đưa trường hợp này trở về giống như trường hợp thứ hai khi 3-nút hướng về bên phải.

Cuối cùng, khi hai liên kết đỏ hướng tới hai phương khác nhau (Hình b), chúng ta chỉ cần cho nhận giá trị rotate (v.g). Thao tác này định lại hướng của 3-nút “không hợp lệ” bao gồm hai nút được trỏ tới bởi p và x. Các nút này có cùng màu, vì thế không cần thiết phải đổi màu chúng, và chúng ta trở về trường hợp thứ ba. Phối hợp thao tác này và phép quay của trường hợp thứ ba được gọi là sự quay kép (double rotation).

Chúng ta sẽ xét thao tác split xuất hiện trong ví dụ sau khi G được thêm vào.


(Hình 2. Quay một 3-nút trong Hình 1)

Trước tiên thao tác đổi màu để tách 4-nút chứa H, I, N. Kế đến là một thao tác quay kép: bộ phận đầu tiên xung quanh cạnh giữa I và R, bộ phận thứ hai xung quanh cạnh giữa E và I. Sau những sửa đổi này, G có thể được chèn vào bên trái của H.

Hàm sau đây sẽ bổ sung đủ các thao tác được thực hiện bởi split. Nó phải chuyển các màu của x và các con của nó, làm phần dưới của một thao tác quay nếu cần thiết và kế đến được thực hiện sự quay đơn nếu cần thiết.



Nếu gốc là một 4-nút thì thủ tục split làm cho gốc có màu đỏ: thao tác tương ứng với sự chuyển đổi nó cùng với nút nháp (dummy) ở phía trên nó thành một 3-nút. Đương nhiên không có lý do gì để làm điều này, vì vậy có một lệnh ở cuối của thủ tục split dùng để duy trì màu đen của gốc. Khi bắt đầu xử lý cần phải khởi tạo cẩn thận nút nháp như đoạn chương trình sau:



--*****

Dễ dàng thấy rằng cây đỏ-đen được tạo từ tập hợp khoá mẫu nhờ vào thuật toán trên. Với phương pháp này, chỉ phải trả giá một vài phép quay mà chúng ta có được một cây cân bằng. Thuật toán này thể hiện ưu thế hơn hẳn so với các phương pháp chúng ta đã từng biết trước đó.

*** Một thao tác tìm kiếm trên cây đỏ-đen với N nút được xây dựng từ các khoá ngẫu nhiên có lẻ đòi hỏi khoảng lgN phép so sánh, và về mặt trung bình thì một thao tác có lẻ chèn đòi hỏi ít hoen một phép quay.

Mặc dù, phải thừa nhận rằng: Sự phân tích chính xác trường hợp trung bình của thuật toán này chưa được thực hiện, nhưng có các kết quả thuyết phục từ các phân tích các trường hợp riêng và các trường hợp giả định.

Một điều thực sự đáng chú ý đối với các cây đỏ-đen là tính năng của nó trong trường hợp xấu nhất, chỉ cần trả giá rất ít cho trường hợp này. Giá phải trả đối với mỗi lần tìm kiếm thì cũng như khi cây cân bằng được xây dựng bởi thuật toán cơ bản và khi chèn thì cần một phép kiểm tra bit phụ trợ, một lần tách nút.

**** Một thao tác tìm kiếm trên một cây đỏ-đen N nút đòi hỏi ít hơn 2lgN+2 phép so sánh, và một thao tác chèn đòi hỏi số phép quay ít hơn một phần tư so với các phép so sánh.

Chỉ có các thao tác “tách” một 3-nút được nối với một 4-nút trong một cây 2-3-4 đòi hỏi một thao tác quay tương ứng như cây đỏ-đen. Trường hợp xấu nhất xảy ra khi đường dẫn tới điểm thực hiện thao tác chèn bao gồm luân phiên các 3-nút và 4-nút.

Tóm lại, bằng cách sử dụng phương pháp này, một khoá trong một tập tin cỡ nửa triệu mẩu tin có thể được tìm thấy sau khi thực hiện khoảng hai mươi phép so sánh. Trong trường hợp xấu nhất có thể cần khoảng gấp hai lần số phép so sánh, nhưng con số này cũng không phải nhiều lắm. Hơn nữa, mỗi phép so sánh đòi hỏi rất ít thời gian vì vậy thuật toán tìm kiếm sẽ rất nhanh.