Bài tập cây nhị phân tìm kiếm c++ năm 2024
Trong các phần trước, chúng ta đã thảo luận về các cách biểu diễn cây khác nhau và trong tất cả chúng, chúng ta không áp đặt bất kỳ hạn chế nào đối với dữ liệu trong node. Do đó, để tìm kiếm một phần tử, chúng ta cần kiểm tra cả cây con bên trái và cây con bên phải. Do đó, độ phức tạp trong trường hợp xấu nhất của thao tác tìm kiếm là O(n). Show
Trong phần này, chúng ta sẽ thảo luận về một biến thể khác của cây nhị phân: Cây tìm kiếm nhị phân (BST). Như tên gợi ý, công dụng chính của biểu diễn này là để tìm kiếm. Trong biểu diễn này, chúng ta áp đặt hạn chế đối với loại dữ liệu mà một node có thể chứa. Trong biểu diễn này, chúng ta áp đặt hạn chế đối với loại dữ liệu mà một node có thể chứa. Kết quả là, nó giảm thao tác tìm kiếm trung bình trong trường hợp xấu nhất xuống O(logn). Các tính chất của Binary Search TreesTrong cây tìm kiếm nhị phân, tất cả các phần tử của cây con bên trái phải nhỏ hơn dữ liệu gốc và tất cả các phần tử của cây con bên phải phải lớn hơn dữ liệu gốc. Đây được gọi là thuộc tính cây tìm kiếm nhị phân. Lưu ý rằng, thuộc tính này phải được thỏa mãn tại mọi node trong cây.
Ví dụ: Cây bên trái là cây tìm kiếm nhị phân và cây bên phải không phải là cây tìm kiếm nhị phân (tại node 6, nó không thỏa mãn thuộc tính của cây tìm kiếm nhị phân). Khai báo cây tìm kiếm nhị phânKhông có sự khác biệt giữa khai báo cây nhị phân thông thường và khai báo cây nhị phân tìm kiếm. Sự khác biệt chỉ ở dữ liệu chứ không phải ở cấu trúc. Nhưng để thuận tiện, chúng ta đổi tên cấu trúc thành:
Thao tác trên cây tìm kiếm nhị phânCác thao tác chính Các hoạt động chính được hỗ trợ bởi cây tìm kiếm nhị phân:
Hoạt động phụ trợ
Notes về cây tìm kiếm nhị phân
Tìm phần tử trong cây tìm kiếm nhị phânThao tác tìm rất đơn giản trong BST. Bắt đầu với thư mục gốc và tiếp tục di chuyển sang trái hoặc phải bằng thuộc tính của BST. Nếu dữ liệu chúng ta đang tìm kiếm giống với dữ liệu node thì chúng ta trả về node hiện tại. Nếu dữ liệu chúng ta đang tìm kiếm nhỏ hơn dữ liệu node thì tìm kiếm cây con bên trái của node hiện tại; mặt khác tìm kiếm cây con bên phải của node hiện tại. Nếu không có dữ liệu, chúng ta sẽ return null link.
Time Complexity: O(n), trong trường hợp xấu nhất (khi cây tìm kiếm nhị phân đã cho là cây nghiêng). Space Complexity: O(n), dành cho ngăn xếp đệ quy. Phiên bản non recursive của thuật toán trên có thể là:
Time Complexity: O(n). Space Complexity: O(1). Tìm phần tử nhỏ nhất trong cây tìm kiếm nhị phânTrong các BST, phần tử nhỏ nhất là node ngoài cùng bên trái mà không có node con bên trái. Trong BST bên dưới, phần tử tối thiểu là 4.
Time Complexity: O(n), trong trường hợp xấu nhất (khi BST là cây lệch trái). Space Complexity: O(n), đối với ngăn xếp đệ quy. Phiên bản non recursive của thuật toán trên có thể là:
Time Complexity: O(n). Space Complexity: O(1). Tìm phần tử lớn nhất trong cây tìm kiếm nhị phânTrong các BST, phần tử lớn nhất là node ngoài cùng bên phải, không có node con bên phải. Trong BST bên dưới, phần tử tối đa là 16.
Time Complexity: O(n), trong trường hợp xấu nhất (khi BST là cây lệch trái). Space Complexity: O(n), đối với ngăn xếp đệ quy. Phiên bản non recursive của thuật toán trên có thể là:
Time Complexity: O(n). Space Complexity: O(1). Inorder Predecessor và Successor ở đâu?Đâu là Inorder Predecessor(tiền nhiệm) và Successor(kế nhiệm) của node X trong cây tìm kiếm nhị phân giả sử tất cả các node là khác nhau?\ Nếu X có hai node con thì inorder predecessor của nó là giá trị lớn nhất trong cây con bên trái của nó và giá trị kế tiếp thứ tự của nó là giá trị nhỏ nhất trong cây con bên phải của nó. Nếu nó không có con bên trái, thì node inorder predecessor là tổ tiên bên trái đầu tiên của nó. Chèn một phần tử từ cây tìm kiếm nhị phânĐể chèn dữ liệu vào cây tìm kiếm nhị phân, trước tiên chúng ta cần tìm vị trí cho phần tử đó. Chúng ta có thể tìm vị trí chèn bằng cách làm theo cơ chế tương tự như cơ chế của thao tác tìm. Trong khi tìm vị trí, nếu dữ liệu đã có ở đó thì chúng ta chỉ cần bỏ qua và đi ra. Nếu không, hãy chèn dữ liệu vào vị trí cuối cùng trên đường dẫn đi qua. Như một ví dụ, chúng ta hãy xem xét cây sau đây. node chấm chấm cho biết phần tử (5) sẽ được chèn vào. node có các gạch đứt cho biết phần tử (5) sẽ được chèn vào. Để chèn 5, duyệt qua cây bằng chức năng tìm. Tại node có giá trị 4, chúng ta cần đi sang phải, nhưng không có cây con, vì vậy 5 không có trong cây và đây là vị trí chính xác để chèn.
Lưu ý: Trong đoạn mã trên, sau khi chèn một phần tử vào cây con, cây được trả về node cha của nó. Time Complexity: O(n). Space Complexity: O(n), cho ngăn xếp đệ quy. Nếu sử dụng vòng lặp, space complexity là O(1). |