tailieunhanh - CHƯƠNG 8: CÂY

Các CTDL được nghiên cứu trong các chương trước (danh sách, ngăn xếp, hàng đợi) là các CTDL tuyến tính (các thành phần dữ liệu được sắp xếp tuyến tính). Trong chương này chúng ta sẽ nghiên cứu một loại CTDL không tuyến tính: CTDL cây. Cây là một trong các CTDL quan trọng nhất trong khoa học máy tính. Hầu hết các hệ điều hành đều tổ chức các file dưới dạng cây. | Trong mục chúng ta đã chỉ ra rằng, thời gian thực hiện các phép toán Search, Insert và Delete trên cây tìm kiếm nhị phân là O(h), trong đó h là độ cao của cây. Tuy nhiên, cùng một tập dữ liệu chúng ta có thể lưu trong các cây tìm kiếm nhị phân có độ cao rất khác nhau. Chúng ta đã chỉ ra điều đó trong hình , ở đó chúng ta đã đưa ra ba cây tìm kiếm nhị phân cùng biểu diễn một tập gồm 6 dữ liệu với các giá trị khóa là 4, 1, 3, 7, 5, 9. Xuất phát từ cây tìm kiếm nhị phân rỗng, bằng cách sử dụng phép toán xen vào cây một dãy các dữ liệu, ta sẽ nhận được một cây tìm kiếm nhị phân biểu diễn tập dữ liệu đó. Chẳng hạn, chúng ta có cây trong hình , khi chúng ta xen vào cây rỗng lần lượt các dữ liệu với các khóa 4, 7, 5, 1, 3, 9; cây này có độ cao là 3. Nhưng nếu chúng ta xen vào cây rỗng lần lượt các dữ liệu với các giá trị khóa được sắp xếp theo thứ tự tăng dần, chúng ta sẽ nhận được cây trong hình . Cây có đặc điểm là tất cả các cây con trái của mỗi đỉnh đều rỗng, nó có độ cao là 6, cây này thực sự là một DSLK, việc tìm kiếm, xen, loại trên cây này là tìm kiếm, xen, loại trên DSLK. Như vậy, cây tìm kiếm nhị phân biểu diễn tập N dữ liệu trong trường hợp xấu nhất (khi cây suy biến thành DSLK), thời gian thực hiện các phép toán Search, Insert, Delete trên cây tìm kiếm nhị phân là O(N).