Cây tìm kiếm nhị phân

3.1 Định nghĩa cây tìm kiếm nhị phân (BST)

Cây tìm kiếm nhị phân (BST) là một cây nhị phân có các tính chất sau:

• Đối với bất kỳ nút nào, cây con trái chỉ chứa các nút có khóa nhỏ hơn khóa của nút đó.
• Đối với bất kỳ nút nào, cây con phải chỉ chứa các nút có khóa lớn hơn khóa của nút đó.
• Cả hai cây con của mỗi nút cũng là cây tìm kiếm nhị phân.

Ví dụ về BST:

BST là viết tắt của Binary Search Tree - nghĩa là "Cây tìm kiếm nhị phân". Thực tế nó là một tổ chức dữ liệu dưới dạng "cây", mà qua đó bạn có thể tìm kiếm rất nhanh. Cấu trúc cây thực tế là một kiểu sắp xếp ẩn/khéo léo của các phần tử.

Phép duyệt trung tâm (in-order traversal)

Nhiệm vụ duyệt là tạo ra danh sách các nút theo một cách nhất định (hoặc dữ liệu từ các nút, vấn đề thuật ngữ và có ý nghĩa trong thực tế). Duyệt trung tâm (đối xứng) là phép duyệt mà tại đó gốc cây chiếm vị trí giữa kết quả của phép duyệt tương ứng của cây con trái và phải.

Cùng với thuộc tính của cây tìm kiếm nhị phân (liên quan đến bất đẳng thức, xem lý thuyết) điều này nói rằng duyệt trung tâm của cây tìm kiếm nhị phân sẽ hình thành cho chúng ta danh sách các nút được sắp xếp - tuyệt vời! Đây là cách duyệt của cây đã được xác định trước đó:

3.2 Nguyên tắc hoạt động và thuộc tính của BST

Nguyên tắc hoạt động:

• Tổ chức dữ liệu: BST tổ chức dữ liệu để cung cấp việc tìm kiếm, chèn và xóa phần tử hiệu quả.
• Cấu trúc đệ quy: Mỗi nút trong BST tuân theo cùng quy tắc với gốc cây, làm cho cấu trúc đệ quy.
• Cân bằng: Để đảm bảo hiệu suất tối ưu, BST cần được cân bằng, tức là chiều cao của cây con trái và phải cần phải gần như bằng nhau.

Thuộc tính của BST:

• Thứ tự: Bất cứ lúc nào có thể duyệt cây theo thứ tự "in-order" (cây con trái → nút hiện tại → cây con phải) để lấy tất cả các phần tử theo thứ tự đã sắp xếp.
• Thời gian thao tác:
  • Trung bình, thời gian thực hiện thao tác tìm kiếm, chèn và xóa là O(log n), với n là số lượng nút.
  • Trong trường hợp xấu (nếu cây không cân bằng) thời gian thực hiện thao tác có thể lên tới O(n).
• Khóa duy nhất: Tất cả các khóa trong BST phải là duy nhất để duy trì thứ tự.

3.3 Các thao tác chính

1. Chèn (Insertion):

Nguyên tắc hoạt động:

• Bắt đầu từ nút gốc.
• So sánh khóa của nút mới với khóa của nút hiện tại.
• Nếu khóa mới nhỏ hơn, chuyển sang cây con trái, nếu lớn hơn thì chuyển sang cây con phải.
• Lặp lại quá trình cho đến khi tìm được vị trí thích hợp để chèn nút mới (hoặc cây con trái hay cây con phải bị thiếu).

Thuật toán:

1. Nếu cây trống, nút mới sẽ trở thành nút gốc.
2. Ngược lại, đệ quy tìm vị trí đúng và thêm nút mới.

2. Xóa (Deletion):

Nguyên tắc hoạt động:

• Tìm nút cần xóa.
• Xem xét ba trường hợp:
• Nút là lá (không có con): chỉ cần xóa nút.
• Nút có một đứa con: thay thế nút bằng đứa con của nó.
• Nút có hai đứa con: tìm nút nhỏ nhất trong cây con phải (hoặc lớn nhất trong cây con trái), sao chép giá trị của nó vào nút bị xóa và đệ quy xóa nút nhỏ nhất trong cây con phải.

Thuật toán:

1. Tìm nút với khóa được chỉ định.
2. Tùy thuộc vào trường hợp thực hiện xóa và chia lại nút tương ứng.

3. Tìm kiếm (Search):

Nguyên tắc hoạt động:

• Bắt đầu từ nút gốc.
• So sánh khóa của nút cần tìm với khóa của nút hiện tại.
• Nếu khóa trùng, trả về nút.
• Nếu khóa nhỏ hơn, chuyển sang cây con trái, nếu lớn hơn thì chuyển sang cây con phải.
• Lặp lại quá trình cho đến khi tìm thấy nút với khóa cần tìm hoặc đạt tới cuối cây (trong trường hợp này nút không được tìm thấy).

Thuật toán:

1. Nếu cây trống hoặc khóa của nút trùng với khóa cần tìm, trả về nút.
2. Nếu khóa của nút cần tìm nhỏ hơn, đệ quy tìm trong cây con trái.
3. Nếu khóa của nút cần tìm lớn hơn, đệ quy tìm trong cây con phải.

3.4 Ví dụ về các bài toán được giải bằng cách sử dụng BST

1. Tìm kiếm phần tử trong tập số động

Cần hỗ trợ một tập số mà bạn có thể thêm phần tử mới, xóa phần tử hiện có và nhanh chóng tìm kiếm xem một số nhất định có nằm trong tập không.

Giải pháp bằng cách sử dụng BST:

• Chèn phần tử mới vào cây.
• Xóa phần tử hiện có.
• Tìm kiếm phần tử trong cây.

Ví dụ sử dụng:

Duy trì danh sách người dùng đã đăng ký trong hệ thống, nơi người dùng có thể được thêm và xóa, và hệ thống cần nhanh chóng kiểm tra xem người dùng đã đăng ký hay chưa.

2. Tìm phần tử nhỏ nhất và lớn nhất

Cần nhanh chóng tìm giá trị nhỏ nhất và lớn nhất trong tập dữ liệu.

Giải pháp bằng cách sử dụng BST:

• Phần tử nhỏ nhất nằm ở nút trái nhất của cây.
• Phần tử lớn nhất nằm ở nút phải nhất của cây.

Ví dụ sử dụng:

Duy trì một hệ thống theo dõi giá cổ phiếu, nơi cần nhanh chóng tìm giá thấp nhất và cao nhất tại thời điểm hiện tại.

3. Kiểm tra cân bằng biểu thức

Cho một biểu thức toán học, cần kiểm tra sự cân bằng của nó về số lượng dấu ngoặc mở và đóng.

Giải pháp bằng cách sử dụng BST:

Sử dụng BST để lưu trữ trạng thái trung gian kiểm tra cân bằng dấu ngoặc.

Ví dụ sử dụng:

Phân tích và biên dịch mã, cần kiểm tra độ chính xác của việc sử dụng dấu ngoặc trong biểu thức.

4. Xây dựng từ điển

Cần tạo một cấu trúc dữ liệu để lưu trữ từ điển, nơi các từ có thể được thêm, xóa và tìm nhanh chóng.

Giải pháp bằng cách sử dụng BST:

• Các từ được thêm vào cây theo thứ tự bảng chữ cái.
• Tìm kiếm từ được thực hiện theo khóa.

Ví dụ sử dụng:

Hệ thống tự động sửa văn bản, nơi cần nhanh chóng tìm và sửa các từ.