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ânvà sử dụng CTDL này để cài đặt KDLTT tập động. Chúng ta đã chỉ rarằ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ợpxấ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ánhtrái (phải) của mọi đỉnh đều rỗng....
Nội dung trích xuất từ tài liệu:
CHƯƠNG 11: CÁC CÂY TÌM KIẾM CÂN BẰNG PHẦN IICÁ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ânvà sử dụng CTDL này để cài đặt KDLTT tập động. Chúng ta đã chỉ rarằ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ợpxấ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ánhtrái (phải) của mọi đỉnh đều rỗng. Trường hợp này sẽ xảy ra khi chúng taxen 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ênhlệ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ựchiện một dãy phép toán trên CTDL tự điều chỉnh. Cuối chương này chúngta 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ộtdã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éttrong chương này đều là cây tìm kiếm nhị phân, tức là chúng đều phảithoả mãn tính chất tìm kiếm nhị phân (hay tính chất được sắp): dữ liệuchứa trong một đỉnh bất kỳ có khoá lớn hơn khoá của mọi dữ liệu chứatrong cây con trái và nhỏ hơn khoá của mọi dữ liệu chứa trong cây conphải. Chúng chỉ khác nhau bởi các điều kiện áp đặt nhằm giảm độ caocủ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ạimọi đỉnh. Mỗi khi thực hiện một phép toán (xen hoặc loại) làm cho câykhô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âybằ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 tronghì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 conphả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épquay 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 pvà 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 đỉnhp,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 T3lớ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ánhọ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ớilá, 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 nhaukhông quá 1. Như vậy, mỗi đỉnh của cây AVL sẽ ở một trong ba trạng thái: câycon trái và phải có độ cao bằng nhau (ta ký hiệu trạng thái này là EH), câycon trái cao hơn cây con phải 1 (t ...