So sánh cấu trúc trie và binary search trê
Cây nhị phân tìm kiếm là một cấu trúc thường được sử dụng trong tin học. Điển hình là các kiểu dữ liệu set và map của C++ được cài đặt bằng cây nhị phân tìm kiếm. Bài viết này sẽ cung cấp những kiến thức cơ bản về cây nhị phân tìm kiếm và cách cài đặt một cây nhị phân tìm kiếm đơn giản (không hiệu quả). Show Cách cài đặt trong bài này không được sử dụng trong thực tế tuy nhiên sẽ là nền tảng để nghiên cứu các cấu trúc cây nhị phân cao cấp hơn. Sơ lược về cây nhị phânCây nhị phân gồm nhiều nút, mỗi nút có nhiều nhất là 2 nút con, gọi là nút con trái và nút con phải. Các nút không có nút con nào gọi là nút lá. Ngoài ra, mỗi nút đều có duy nhất một nút cha, trừ nút gốc của cây không có cha. Mỗi nút có thể chứa thêm thông tin, gọi là khóa. Khóa của nút thường là một số nguyên, tuy nhiên có thể là bất cứ kiểu dữ liệu nào. Sau đây là ví dụ một cây nhị phân với khóa là các số nguyên: Ngoài ra, nếu cắt một nhánh của cây ta sẽ được một cây con: Với cây nhị phân tìm kiếm, khóa của các đỉnh thỏa tính chất sau:
Khóa của đỉnh phải là một kiểu dữ liệu có thể so sánh được. Ví dụ một cây nhị phân tìm kiếm với khóa là số nguyên: Khi cài đặt, ta cần một kiểu dữ liệu để lưu nút của cây:
Trong đó:
Để cho thuận tiện, ta thêm một constructor cho kiểu dữ liệu vừa tạo. Thao tác thêmPhần này sẽ trình bày thao tác thêm một nút có khóa Việc thêm một khóa được thực hiện một cách đệ quy:
Với quy trình như trên, nút mới luôn là nút lá. Cài đặt trong C++ như sau:
Ví dụ sử dụng hàm trên:
Chú ý khi gọi hàm, cần gán lại nút gốc như trên. Thao tác tìm kiếmPhần này trình bày thao tác tìm một nút có khóa bằng
5. Thao tác tìm kiếm cũng được thực hiện đệ quy tương tự như trên. Cụ thể:
Cài đặt của thao tác này đơn giản hơn:
Việc khử đệ quy hàm trên khá dễ, bạn đọc có thể tự tìm hiểu. Thao tác xóaXóa một nút phức tạp hơn so với việc thêm và tìm kiếm. Ta có 3 trường hợp: Nút cần xóa không có nút con nàoỞ trường hợp này, chỉ đơn giản là xóa đi nút đó, không làm gì thêm. Nút cần xóa có 1 nút conỞ trường hợp này, ta thay nút cần xóa bằng nút con của nó. Ví dụ: Nút cần xóa có 2 nút conỞ trường hợp này, ta tìm nút thay thế cho nút cần xóa, sau đó chuyển khóa của nút thay thế lên nút cần xóa, rồi cuối cùng mới xóa nút thay thế. Ví dụ: Ta thấy, nút thay thế phải là 1 trong 2 nút có khóa gần nhất với nút cần xóa, để việc chuyển khóa lên trên không vi phạm tính chất của cây. Khi xóa nút thay thế, cũng phải xét xem nó có bao nhiêu nút con như khi xóa một nút bình thường. Cài đặtCài đặt trong C++:
Khi gọi hàm, tương tự như khi thêm nút, ta cũng phải gán:
Độ phức tạpĐộ phức tạp của các thao tác trên tùy thuộc vào độ cao của cây khi truy vấn. Với dữ liệu ngẫu nhiên, cách cài đặt cây nhị phân trong bài này có độ phức tạp trung bình cho mỗi thao tác là \(O(\log N)\), với \(N\) là số nút trên cây. Tuy nhiên, độ phức tạp trong trường hợp xấu nhất là \(O(N)\), vì vậy cây này không được sử dụng trong thực tế. |