CHƯƠNG 11: CÁC CÂY TÌM KIẾM CÂN BẰNG

Chia sẻ: Chao Hello | Ngày: | Loại File: DOC | Số trang:45

Thêm vào BST

Báo xấu

201
lượt xem 70
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong mục 8.4 chúng ta đã nghiên cứu CTDL cây tìm kiếm nhị phân và sử dụng CTDL này để cài đặt KDLTT tập động. Chúng ta đã chỉ ra rằng, các phép toán tập động trên cây tìm kiếm nhị phân, trong trường hợp xấu nhất, sẽ đòi hỏi thời gian O(n), trong đó n là số đỉnh của cây. Đó là trường hợp cây suy biến thành danh sách liên kết, tức là tất cả các nhánh trái (phải) của mọi đỉnh đều rỗng....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: CHƯƠNG 11: CÁC CÂY TÌM KIẾM CÂN BẰNG

PHẦN II CÁC CẤU TRÚC DỮ LIỆU CAO CẤP 40
CHƯƠNG 11 CÁC CÂY TÌM KIẾM CÂN BẰNG Trong mục 8.4 chúng ta đã nghiên cứu CTDL cây tìm kiếm nhị phân và sử dụng CTDL này để cài đặt KDLTT tập động. Chúng ta đã chỉ ra rằng, các phép toán tập động trên cây tìm kiếm nhị phân, trong trường hợp xấu nhất, sẽ đòi hỏi thời gian O(n), trong đó n là số đỉnh của cây. Đó là trường hợp cây suy biến thành danh sách liên kết, tức là tất cả các nhánh trái (phải) của mọi đỉnh đều rỗng. Trường hợp này sẽ xảy ra khi chúng ta xen vào cây một dãy dữ liệu đã được sắp xếp theo thứ tự tăng (giảm), một hoàn cảnh thường gặp trong thực tiễn. Trong chương này chúng ta sẽ nghiên cứu một số loại cây tìm kiếm cân bằng, khắc phục được sự chênh lệch nhiều về số đỉnh giữa nhánh trái và nhánh phải tại mọi đỉnh, và do đó thời gian thực hiện các phép toán tập động, trong trường hợp xấu nhất, cũng chỉ là O(logn). Các cây tìm kiếm cân bằng mà chúng ta sẽ đưa ra là cây AVL và cấy đỏ - đen. Chúng ta sẽ đưa vào chương này phương pháp phân tích mới, từ trước đến nay chúng ta chưa bao giờ sử dụng tới, đó là phân tích trả góp. Phương pháp này cho phép ta đánh giá cận trên chặt của thời gian thực hiện một dãy phép toán trên CTDL tự điều chỉnh. Cuối chương này chúng ta sẽ nghiên cứu CTDL cây tán loe: một dạng CTDL tự điều chỉnh, và sử dụng phương pháp phân tích trả góp để đánh giá thời gian thực hiện một dãy phép toán tập động trên cây tán loe. Trước hết chúng ta đưa vào các phép toán quay trên cây nhị phân. Các phép quay này sẽ được sử dụng đến trong các mục tiếp theo. 11.1 CÁC PHÉP QUAY Các cây AVL, cây đỏ - đen, cây tán loe mà chúng ta sẽ lần lượt xét trong chương này đều là cây tìm kiếm nhị phân, tức là chúng đều phải thoả mãn tính chất tìm kiếm nhị phân (hay tính chất được sắp): dữ liệu chứa trong một đỉnh bất kỳ có khoá lớn hơn khoá của mọi dữ liệu chứa trong cây con trái và nhỏ hơn khoá của mọi dữ liệu chứa trong cây con phải. Chúng chỉ khác nhau bởi các điều kiện áp đặt nhằm giảm độ cao của cây hoặc không làm mất cân bằng giữa nhánh trái và nhánh phải tại mọi đỉnh. Mỗi khi thực hiện một phép toán (xen hoặc loại) làm cho cây không còn thoả mãn các điều kiện áp đặt, chúng ta sẽ cấu tạo lại cây bằng cách sử dụng các phép quay. 41
Có hai phép quay cơ bản là quay trái và quay phải được chỉ ra trong hình 11.1. Giả sử p là một đỉnh trong cây nhị phân, và đỉnh con trái của nó là v. Phép quay phải đỉnh p sẽ đặt v vào vị trí của đỉnh p, p trở thành con phải của v và cây con phải của đỉnh v trở thành cây con trái của đỉnh p. Trong hình 11.1, phép quay phải đỉnh p sẽ biến cây ở vế trái thành cây ở vế phải. Đối xứng qua gương của phép quay phải là phép quay trái, như được chỉ ra trong hình 11.1. P P quay phải p v p quay trái v v p T T T T T T Hình 11.1. Các phép quay cơ bản. Bây giờ chúng ta chứng minh một khẳng định quan trọng: các phép quay cơ bản (trái hoặc phải) không phá vỡ tính chất tìm kiếm nhị phân. Chúng ta chứng minh cho phép quay phải tại đỉnh p. Phép quay này chỉ tác động đến đỉnh p và v, và do đó ta chỉ cần chỉ ra rằng, sau khi quay đỉnh p và v vẫn còn thoả mãn tính chất tìm kiếm nhị phân. Ta có nhận xét rằng, phép quay không ảnh hưởng gì đến cây con trái của v và cây con phải của đỉnh p.Trước khi quay, cây con phải của v là T2 thuộc cây con trái của đỉnh p,do đó, khoá của mọi đỉnh trong cây con T2 lớn hơn khoá của đỉnh v và nhỏ hơn khoá của đỉnh p; mặt khác, khoá của mọi đỉnh trong cây con T3 lớn hơn khoá của đỉnh p, và do đó lớn hơn khoá của đỉnh v, vì khóa của đỉnh p lớn hơn khoá của đỉnh v. Từ các kết luận đó, ta thấy ngay rằng, các đỉnh p và v sau phép quay phải vẫn còn thoả mãn tính chất tìm kiếm nhị phân. 11.2 CÂY AVL 42
Trong mục này chúng ta nghiên cứu CTDL cây AVL, do các nhà toán học Nga Adelson- Velskii và Landis đề xuất. Nhớ lại rằng, chúng ta xác định độ cao của cây nhị phân là số đỉnh trên đường đi dài nhất từ gốc tới lá, và độ cao của cây rỗng bằng 0. Cây AVL được định nghĩa như sau: Định nghĩa 11.1. Cây AVL là cây tìm kiếm nhị phân, trong đó độ cao của cây con trái và độ cao của cây con phải của mỗi đỉnh khác nhau không quá 1. Như vậy, mỗi đỉnh của cây AVL sẽ ở một trong ba trạng thái: cây con trái và phải có độ cao bằng nhau (ta ký hiệu trạng thái này là EH), cây con trái cao hơn cây con phải 1 (trạng thái LH) và cây con phải cao hơn cây con trái 1 (trạng thái RH). Sau này chúng ta sẽ nói đỉnh ở một trong ba trạng thái trên là đỉnh cân bằng. Còn nếu một đỉnh có độ cao cây con trái lớn hơn độ cao cây con phải 2 thì nó được xem là đỉnh lệch bên trái. Tương tự, ta có khái niệm đỉnh lệch bên phải. Hình 11.1 cho ta một ví dụ về cây AVL 1 5 1 3 8 1 6 Hình 11.1. Một cây AVL Bây giờ chúng ta chứng minh một tính chất quan trọng về độ cao của cây AVL. Định lý 11.1. Độ cao của cây AVL có n đỉnh là O(logn). Thay cho đánh giá độ cao lớn nhất của cây AVL chứa n đỉnh, ta đánh giá số đỉnh ít nhất của cây AVL với độ cao h. Ta ký hiệu N(h) là số đỉnh ít nhất của cây AVL có độ cao h. Các cây AVL có số đỉnh ít nhất với độ cao h = 1, 2, 3 được chỉ ra trong hình 11.2a. Như vậy N(0) = 0, N(1) = 1, N(2) = 2, N(3) = 3. Cây AVL có số đỉnh ít nhất với độ cao h là cây trong hình 11.2b, nó có cây con trái là cây AVL có số đỉnh ít nhất với độ cao h-1, và cây con phải là cây AVL có số đỉnh ít nhất với độ cao h-2. Do đó 43
N(h) = N(h-1) + N(h-2) + 1 (1) h=1 h=2 h=3 h-1 h-2 Hình 11.2. Các cây AVL có số đỉnh ít nhất. Từ đẳng thức (1) và tính chất của dãy só Fibonacci, bằng quy nạp ta chứng minh được N(h) = F(h + 1) – 1 (2) trong đó F(m) là số thứ m trong dãy số Fibonacci. 1 ˆ Nhưng F(m) = (φ m − φ m ) , trong đó 5 1 ˆ 1 φ = (1 + 5 ) và φ = (1 − 5 ) , do đó 2 2 1 ˆ N(h) = (φ h +1 − φ h +1 ) − 1 5 ˆ 1 ˆ Chú ý rằng φ = (1 − 5 ) < 1. Do đó hạng thức φ h+1 sẽ gần với 0 khi h lớn. 2 Do đó, ta có đánh giá 44
1 N(h) ≈ φ h +1 5 Từ đó ta có h = O(log N(h)) Vì N(h) là số đỉnh ít nhất của cây AVL có độ cao h, do đó độ cao h của cây AVL có n đỉnh là h = O(logn). Chúng ta sẽ sử dụng tính chất về độ cao của cây AVL để đánh giá thời gian thực hiện các phép toán tập động trên cây AVL. 12.2.1 Các phép toán tập động trên cây AVL Bởi vì cây AVL là cây tìm kiếm nhị phân, nên các phép toán hỏi: tìm kiếm dữ liệu có khoá k cho trước, tìm dữ liệu có khoá nhỏ nhất (lớn nhất) được thực hiện theo các thuật toán như trên cây tìm kiếm nhị phân. Chúng ta đã chỉ ra rằng, độ cao của cây AVL chứa n đỉnh là O(logn), do đó thời gian thực hiện các phép toán hỏi trên cây AVL là O(logn). Nhưng nếu chúng ta thực hiện phép toán xen (hoặc phép loại) trên cây AVL thì chúng ta không thể chỉ tiến hành như trên cây tìm kiếm nhị phân, bởi vì sau khi xen (loại) tính cân bằng tại một số đỉnh có thể bị phá vỡ, tức là độ cao của cây con trái (phải) lớn hơn độ cao cây con phải (trái) 2. Trong các trường hợp đó, chúng ta cần phải cấu trúc lại cây bằng cách sử dụng các phép quay để thiết lập lại sự cân bằng của các đỉnh. Phép toán xen. Việc xen vào cây AVL một đỉnh mới trước hết được thực hiện theo thuật toán xen vào cây tìm kiếm nhị phân. Khi đó các đỉnh nằm trên đường đi từ đỉnh mới xen vào lên gốc có thể không còn cân bằng nữa. Vì vậy chúng ta cần phải đi từ đỉnh mới lên gốc, gặp đỉnh nào mất cân bằng thì sử dụng các phép quay để làm cho nó trở thành cân bằng. Một đỉnh mất cân bằng chỉ có thể là lệch bên trái hoặc lệch bên phải. Chúng ta xét trường hợp đỉnh lệch bên trái. Gải sử a là đỉnh đầu tiên trên đường đi từ đỉnh mới lên gốc bị lệch bên trái. Giả sử P là con trỏ liên kết trong cây trỏ tới đỉnh a. Giả sử đỉnh con trái của a là đỉnh b, cây con trái của b là T1, cây con phải của b là T2, cây con phải của đỉnh a là T3. Trường hợp đỉnh a bị lệch trái chỉ xảy ra khi mà trước khi xen vào đỉnh mới, độ cao cây con trái của đỉnh a lớn hơn độ cao cây con phải 1 và đỉnh mới được xen vào cây con trái của a, làm tăng độ cao cây con trái của a lên 1. Do đó nếu cây con T 3 có độ cao h, thì một trong hai cây con T1, T2 phải có độ cao h + 1, còn cây kia có độ cao là h. Chúng ta xét từng trường hợp. • Mẫu quay phải. Trường hợp cây con T1 có độ cao h + 1 và cây con T2 có độ cao h (h ≥ 0), như trong hình 11.3a, chúng ta chỉ cần thực 45
hiện phép quay phải đỉnh a. Kết quả ta nhận được cây trong hình 11.3b. Dễ dàng thấy rằng sau phép quay phải, cả hai đỉnh a và b đều ở trạng thái cân bằng EH và độ cao của cây P giảm đi 1 so với trước khi quay. P a b h T h+1 T h T 1 (a) P b a T 1 T T (b) 46
Hình 11.3. Mẫu quay phải • Mẫu quay kép trái - phải. Trường hợp cây con T1 có độ cao h, và cây con T2 có độ cao h + 1, nếu chúng ta thực hiện phép quay phải đỉnh a thì đỉnh P lại trở thành lệch phải (hãy thử xem). Trong trường hợp này chúng ta phải tiến hành phép quay kép. Giả sử cây con T2 có gốc là đỉnh c, cây con trái của c là Tl, cây con phải là Tr. Để cho T2 có độ cao h + 1, thì ít nhất một trong hai cây con Tl và Tr phải có độ cao h, còn cây kia có thể có độ cao h hoặc h – 1. Chúng ta có cây như trong hình 11.4a. Đầu tiên ta quay trái đỉnh b để nhận được cây trong hình 11.4b Sau đó ta quay phải đỉnh a, cây kết quả là cây trong hình 11.4c. Dễ dàng thấy sau hai phép quay liên tiếp trái, phải này thì cả ba đỉnh a, b, c đều trở thành cân bằng, đỉnh c ở trạng thái EH, đỉnh b ở trạng thái EH hoặc EH, còn đỉnh a ở trạng thái EH hoặc RH. Chúng ta thấy rằng, sau phép quay kép trái - phải này thì độ cao của cây P cũng giảm đi 1 so với trước khi thực hiện phép quay. P a b h T c h T h-1 h T T (a) 47
P a c T b T T T (b) P c b a T T T T (c) 48
Hình 11.4. Mẫu quay kép trái - phải Chúng ta có một nhận xét quan trọng: cả hai mẫu quay, quay phải hoặc quay kép trái - phải, đều làm giảm độ cao của cây P đi 1, tức là trở lại độ cao của cây P trước khi ta thực hiện phép xen vào. Trường hợp đỉnh a bị lệch bên phải, ta cũng có hai trường hợp riêng. Đó là các cây là đối xứng qua gương của cây trong hình 11.3a và 11.4a. Nếu đỉnh a lệch phải và có dạng đối xứng qua gương cúa cây trong hình 11.3a, ta chỉ cần thực hiện phép quay trái đỉnh a. Nếu đỉnh a lệch phải và có dạng đối xứng qua gương của cây trong hình 11.4a, ta thực hiện phép quay phải – trái (đầu tiên quay phải đỉnh b, sau đó quay trái đỉnh a). Từ nhận xét ở trên, ta suy ra rằng, khi xen vào một đỉnh mới, ta đi từ đỉnh mới lên gốc cây, gặp đỉnh đầu tiên mất cân bằng ta chỉ cần thực hiện một phép quay đơn (phải hoặc trái) hoặc một phép quay kép (trái - phải hoặc phải – trái) là cây trở thành cân bằng. Ví dụ. Khi xen vào cây AVL đỉnh mới 8, ta có cây ở vế trái trong hình 11.5a. Đi từ đỉnh 8 lên, ta thấy đỉnh đầu tiên mất cân bằng là đỉnh 15. Quay phải đỉnh 15 ta nhận được cây AVL ở vế phải hình 11.5a. Bây giờ thay cho đỉnh 8 ta xen vào đỉnh mới 12, ta có cây ở vế trái hình 11.5b. Trường hợp này, đỉnh lệch bên trái cũng là đỉnh 15. Nhưng trong hoàn cảnh này, chúng ta phải sử dụng phép quay kép trái - phải. Đầu tiên quay trái đỉnh 10, sau đó quay phải đỉnh 15 ta nhận được cây AVL ở vế phải hình 11.5b. 49
6 quay phải đỉnh 15 6 5 1 5 1 3 1 17 3 9 1 9 1 8 1 1 8 (a) quay trái đỉnh 10 6 6 quay phải đỉnh 15 5 1 5 1 3 1 1 3 1 1 9 1 9 1 1 1 (b) Hình 11.5. Xen vào cây AVL một đỉnh mới Phép toán loại. Giả sử chúng ta cần loại khỏi cây AVL một đỉnh chứa dữ liệu với khoá k. Đầu tiên ta sử dụng thuật toán loại trên cây tìm kiếm nhị phân để loại đỉnh chứa khoá k. Nhớ lại rằng, nếu đỉnh p chứa khoá k có đầy đủ cả hai con thì ta tìm đến đỉnh ngoài cùng bên phải v của cây con trái của đỉnh p. Lưu dữ liệu trong đỉnh v vào đỉnh p và cắt bỏ đỉnh v (đỉnh v là lá hoặc chỉ có một đỉnh con trái). Trong mọi trường hợp, đỉnh 50
thực sự bị cắt bỏ là đỉnh v, nó là lá hoặc chỉ có một đỉnh con trái hoặc phải. Giả sử cha của đỉnh v là đỉnh u. Sau khi cắt bỏ đỉnh v thì độ cao cây con trái (phải) của u sẽ giảm đi 1, nếu v là đỉnh con trái (phải) của u. Do đó đỉnh u có thể mất cân bằng. Bởi vậy, cũng giống như khi thực hiện phép xen, chúng ta đi từ đỉnh bị cắt bỏ lên gốc cây, gặp đỉnh nào mất cân bằng chúng ta cần áp dụng phép quay đơn (quay trái hoặc phải) hoặc phép quay kép (quay trái - phải hoặc quay phải – trái) để lập lại sự cân bằng cho đỉnh đó. Nhưng lưu ý rằng, phép quay đơn hoặc quay kép tại u làm giảm độ cao của cây con gốc u đi 1, và do đó khi ta thực hiện phép quay đơn (kép) làm cho đỉnh u trở lại cân bằng thì đỉnh cha nó có thể lại mất cân bằng. Do đó, không giống như khi thực hiện phép xen, chỉ cần một lần quay đơn (hoặc quay kép) tại một đỉnh là cây trở lại cân bằng, khi thực hiện phép loại sự mất cân bằng được truyền từ đỉnh bị cắt bỏ lên gốc. Trong trường hợp xấu nhất, tất cả các đỉnh trên đường đi từ đỉnh bị cắt bỏ lên gốc đều lần lượt bị mất cân bằng. Ví dụ. Giả sử chúng ta cần loại khỏi cây AVL trong hình 11.5a đỉnh chứa khoá 7. Tìm đến đỉnh ngoài cùng bên phải của cây con trái đỉnh 7 là đỉnh 5. Chép dữ liệu từ đỉnh 5 lên đỉnh 7 và cắt bỏ đỉnh 5 ta nhận được cây tìm kiếm nhị phân như trong hình 11.5b. Trong cây hình 11.5b, đỉnh 4 mất cân bằng, thực hiện phép quay phải tại đỉnh 4, ta nhận được cây trong hình 11.5c. Đến đây đỉnh 5 lại mất cân bằng, thực hiện phép quay kép phải – trái tại đỉnh 5 chúng ta nhận được cây AVL trong hình 11.5d. 7 4 1 3 5 1 1 1 8 1 1 1 (a) 51
5 4 1 3 1 1 1 8 1 1 1 (b) 5 3 1 1 4 1 1 8 1 1 1 (c) 52
1 5 1 3 8 1 1 1 4 1 1 (d) Hình 11.5. Loại khỏi cây AVL Thời gian thực hiện phép toán xen, loại trên cây AVL. Các phép toán xen và loại trên cây AVL đều cần phải đi từ đỉnh mới xen vào hoặc đỉnh bị cắt bỏ ngược lên gốc, và tiến hành khôi phục lại sự cân bằng của các đỉnh bởi các phép quay. Nhưng thời gian thực hiện phép quay đơn hoặc quay kép là O(1). Do đó, thời gian thực hiện phép xen, loại là tỷ lệ với độ cao của cây AVL. Nhưng độ cao của cây AVL với n đỉnh, theo định lý 11.1, là O(logn), do đó các phép xen, loại trên cây AVL chỉ đòi hỏi thời gian O(logn). 11.2.2 Cài đặt tập động bởi cây AVL CTDL biểu diễn đỉnh của cây AVL là cấu trúc biểu diễn đỉnh của cây tìm kiếm nhị phân được bổ sung thêm một trường lưu giữ trạng thái cân bằng của đỉnh. enum stateType { LH, EH, RH}; struct Node { Item data ; Node* left, right ; StateType balance ; } 53
Trong đó, Item là một cấu trúc chứa một trường key là khoá của dữ liệu. Trước hết chúng ta cài đặt các hàm thực hiện các mẫu quay đơn và các mẫu quay kép. Hàm quay phải (RightRotation): Void RightRotation (Node* & P) // Quay phải đỉnh P, P là con trỏ liên kết trong cây. { Node* Q = P  left ; P  left = Q  right ; Q  right = P ; P=Q; } Tương tự, bạn đọc hãy viết ra hàm quay trái (LeftRotation). Các hàm quay kép trái - phải (LR_ Rotation) và quay kép phải – trái (RL_ Rotation) chứa các lời gọi hàm quay đơn. Cụ thể là như sau: void LR_Rotation (Node* & P) { LeftRotation (P  left): RightRotation (P) ; } void RL_Rotation (Node* & P) { RightRotation ( P  right) ; LeftRotation (P) ; } Sau đây chúng ta cài đặt hàm xen vào cây AVL một đỉnh mới chứa dữ liệu là d. Hàm xen. Hàm Insert được cài đặt là hàm đệ quy void Insert (Node* & P, const Item & d, bool & taller) // Xen vào cây P một đỉnh mới chứa dữ liệu d. // Biến taller nhận giá trị true nếu sau khi xen độ cao của cây P tăng // lên 1, nó nhận giá trị false nếu sau khi xen độ cao cây P không thay 54
// đổi Giả sử khi chúng ta xen đỉnh mới vào cây con trái của đỉnh P, đỉnh P ở trạng thái LH và sau khi xen độ cao của cây con trái tăng lên 1. Rõ ràng trong trường hợp này đỉnh P bị lệch trái, chúng ta cần phải sử dụng phép quay phải hoặc phép quay kép trái - phải để lập lại sự cân bằng cho đỉnh P. Hành động này được cài đặt bởi hàm cân bằng trái (LeftBalance). void LeftBalance (Node* & P) { switch (P  left  balance) { case LH : // Trường hợp hình 11.3a RightRotation(P) ; P  balance = EH ; P  right  balance = EH ; break ; case RH : // Trường hợp hình 11.4t LR_Rotation(P) ; switch (P  balance) { case EH : P left  balance = EH ; P  right  balance = RH ; break ; case LH : P left  balance = EH ; P  right  balance = RH ; break ; case RH : P  left  balance = LH ; P right  balance = EH ; } P  balance = EH ; } } Tương tự, nếu đỉnh P ở trạng thái RH, và đỉnh mới được xen vào cây con phải của đỉnh P và làm tăng độ cao cây con phải lên 1, thì đỉnh P 55
trở thành lệch phải và chúng ta cần sử dụng hàm cân bằng phải (RightBalance). Hàm này được cài đặt tương tự hàm LeftBalance (bài tập) Đến đây chúng ta có thể viết được hàm Insert. void Insert (Node* & P, const Item & d, bool & taller) { if (P = = NULL) { P = new Node ; P  data = d ; P  left = P  right = NULL ; P  balance = EH; taller = true ; } else if (d.key < P  data.key) { Insert (P  left, d, taller) if (taller) switch (P  balance) { case LH : LeftBalance (P) ; taller = false ; break ; case EH : P  balance = LH ; taller = true ; break ; case RH : P  balance = EH ; taller = false ; } } else if (d.key > P  data.key) { Insert (P  right, d, taller) // Các dòng lệnh còn lại tương tự như các dòng lệnh đi sau // Insert (P  left, d, taller) } 56
} Hàm loại. Hàm loại cũng được cài đặt là hàm đệ quy. void Delete (Node* & P, keyType k, bool shorter) // Loại khỏi cây P đỉnh chứa dữ liệu có khoá là k. // Biến shorter nhận giá trị true nếu sau khi loại độ cao cây P ngắn đi 1 // và nhận giá trị false nếu sau khi loại độ cao của cây P không thay // đổi. Giả sử đỉnh bị loại ở cây con phải của đỉnh P và sau khi loại, độ cao cây con phải của P ngắn đi 1. Khi đó, nếu đỉnh P ở trạng thái LH thì sau khi loại, đỉnh P sẽ bị lệch bên trái, trong trường hợp này ta cần sử dụng hàm LeftBalance (P) để lập lại sự cân bằng cho đỉnh P. Nếu đỉnh P không ở trạng thái LH thì sau khi loại, ta cũng cần phải xác định lại trạng thái cân bằng của đỉnh P. Chúng ta cài đặt các hành động cần thực hiện đó trong môt hàm BalanceLeft (P, shorter) như sau: void BalanceLeft (Node* & P, bool shorter) // Xác định lại trạng thái cân bằng cho đỉnh P // Biến shorter nhận giá trị true nếu cây P ngắn đi 1 và nhận giá trị // false nếu độ cao cây P không đổi. // Hàm này được sử dụng khi đỉnh bị loại thuộc cây con phải của P và // phép loại làm cho cây con phải của P ngắn đi 1. { switch (P  balance) { case LH : LeftBalance(P) ; shorter = true; break ; case EH : P  balance = LH ; shorter = false ; break ; case RH : P  balance = EH ; shorter = true : 57
} } Tương tự, khi đỉnh bị loại thuộc cây con trái của đỉnh P, và phép loại làm cho cây con trái của P ngắn đi 1, chúng ta cần sử dụng hàm BalanceRight (P, shorter). Hàm này được cài đặt tương tự như hàm BalanceLeft. Chúng ta cần một hàm thực hiện nhiệm vụ cắt bỏ đỉnh ngoài cùng bên phải của cây R, dữ liệu chứa trong đỉnh bị cắt bỏ sẽ được lưu trong đỉnh Q. void Remove (Node* & R, Node* Q, bool shorter) { if (R  right = = NULL) { Q  data = R  data ; Node* Ptr = R ; R = R  left ; shorter = true ; delete Ptr ; } else { Remove (R  right, Q, shorter) ; if (shorter) BalanceLeft (R, shorter) ; } } Khi đã tìm ra đỉnh chứa dữ liệu với khoá k là đỉnh Q, chúng ta sẽ sử dụng hàm Del (Q, shorter) để loại bỏ đỉnh Q khỏi cây. void Del (Node* & Q, bool & shorter) { if (Q  right = = NULL) { Q = Q  left ; shorter = true ; } else if (Q  left = = NULL) 58
{ Q = Q  right ; shorter = true ; } else { Remove (Q  left, Q, shorter) if (shorter) BalanceRight (Q, shorter) ; } } Bây giờ, sử dụng các hàm BalanceLeft, BalanceRight và hàm Del, chúng ta có thể cài đặt hàm đệ quy Delete như sau: void Delete (Node* & P, keyType k, bool shorter) { if (P! = NULL) if (k < P  data.key) { Delete (P  left, k, shorter) ; if (shorter) BalanceRight (P, shorter) ; } else if (k > P  data.key) { Delete (P  right, k, shorter); if (shorter) BalanceLeft (P, shorter) ; } else Del (P, shorter) ; } Trên đây chúng ta đã cài đặt phép xen và phép loại trên cây AVL bởi các hàm đệ quy. Có thể cài đặt các phép toán xen, loại bởi các hàm không đệ quy được không? Đương nhiên là có, nhưng chúng ta cần phải sử dụng một ngăn xếp để lưu lại các đỉnh trên đường đi từ gốc tới đỉnh mới xen vào, hoặc đường đi từ gốc tới đỉnh bị cắt bỏ. 11.3 CÂY ĐỎ - ĐEN 59