Video: (2) Binary search algorithm – Thuật toán tìm kiếm nhị phân trên mảng sắp xếp 2025
Một cấu trúc cây đặc biệt là đống nhị phân, nơi đặt mỗi phần tử node theo một trật tự đặc biệt. Cây tìm kiếm cho phép bạn tìm kiếm dữ liệu một cách nhanh chóng. Lấy các mục dữ liệu, đặt chúng theo thứ tự sắp xếp trong cây, và sau đó tìm kiếm cây đó là một trong những cách nhanh nhất để tìm thông tin.
Trong một đống nhị phân, nút gốc luôn chứa giá trị nhỏ nhất. Khi xem các chi nhánh, bạn sẽ thấy rằng các chi nhánh cấp trên luôn là một giá trị nhỏ hơn các nhánh và bậc thấp hơn. Hiệu quả là giữ cho cây cân bằng và theo thứ tự có thể dự đoán được để việc tìm kiếm trở nên cực kỳ hiệu quả. Chi phí là giữ cây cân bằng.
Trong tất cả các nhiệm vụ mà ứng dụng làm, việc tìm kiếm tốn nhiều thời gian hơn và cũng là yêu cầu nhiều nhất. Mặc dù việc thêm dữ liệu (và sắp xếp nó sau này) đòi hỏi một khoảng thời gian, lợi ích để tạo và duy trì một bộ dữ liệu đến từ việc sử dụng nó để thực hiện công việc hữu ích, có nghĩa là tìm kiếm nó cho các thông tin quan trọng. Do đó, đôi khi bạn có thể nhận được bằng chức năng CRUD kém hiệu quả hơn và thậm chí là một quy trình sắp xếp ít hơn mức tối ưu, tuy nhiên các tìm kiếm phải tiến hành càng hiệu quả càng tốt. Vấn đề duy nhất là không có một tìm kiếm thực hiện mọi công việc có hiệu quả tuyệt đối, vì vậy bạn phải cân nhắc các lựa chọn của mình dựa trên những gì bạn mong đợi để làm như là một phần của các thói quen tìm kiếm.
Hai trong số các phương pháp tìm kiếm hiệu quả hơn bao gồm việc sử dụng cây tìm kiếm nhị phân (BST) và đống nhị phân. Cả hai kỹ thuật tìm kiếm đều dựa vào cấu trúc giống cây để giữ các phím được sử dụng để truy cập các phần tử dữ liệu. Tuy nhiên, sự sắp xếp của hai phương pháp là khác nhau, đó là lý do tại sao một trong những có lợi thế hơn khác khi thực hiện một số nhiệm vụ. Con số này cho thấy sự sắp xếp cho một BST.
Lưu ý cách các phím thực hiện theo thứ tự trong đó số ít xuất hiện ở bên trái và số lớn hơn xuất hiện ở bên phải. Nút gốc chứa một giá trị nằm giữa khoảng khóa, tạo cho BST một cách tiếp cận cân bằng dễ hiểu để lưu trữ các khóa. Ngược lại sự sắp xếp này với đống nhị phân được hiển thị ở đây.
Mỗi cấp có chứa các giá trị nhỏ hơn mức trước, và gốc chứa giá trị khóa cực đại cho cây. Ngoài ra, trong trường hợp cụ thể này, giá trị nhỏ hơn xuất hiện ở bên trái và bên phải lớn hơn (mặc dù lệnh này không được thi hành nghiêm ngặt). Hình vẽ mô tả một đống nhị phân tối đa. Bạn cũng có thể tạo một đống nhị phân min, trong đó gốc chứa giá trị khóa thấp nhất và mỗi cấp độ được xây dựng để có giá trị cao hơn, với các giá trị cao nhất xuất hiện như một phần của lá.
Như đã lưu ý trước đây, BST có một số ưu điểm so với heap nhị phân khi được sử dụng để thực hiện tìm kiếm. Danh sách sau đây cung cấp một số điểm nổi bật của những lợi thế này:
- Tìm kiếm một phần tử đòi hỏi thời gian O (log n), so với O (n) thời gian cho một đống nhị phân.
- Việc in các phần tử theo thứ tự chỉ đòi hỏi thời gian O (log n), tương ứng với thời gian O (n log n) cho một đống nhị phân.
- Tìm sàn và trần nhà đòi hỏi thời gian O (log n).
- Định vị phần tử nhỏ nhất / lớn thứ K cần thời gian O (log n) khi cây được cấu hình đúng.
Cho dù thời gian này là quan trọng phụ thuộc vào ứng dụng của bạn. BST có xu hướng làm việc tốt nhất trong những tình huống mà bạn dành nhiều thời gian tìm kiếm và ít thời gian hơn để xây dựng cây. Một đống nhị phân có xu hướng làm việc tốt nhất trong các tình huống động, trong đó các phím thay đổi thường xuyên. Heap nhị phân cũng cung cấp các lợi ích, như được mô tả trong danh sách dưới đây:
- Tạo các cấu trúc yêu cầu đòi hỏi ít tài nguyên hơn bởi vì heaps nhị phân dựa vào các mảng, làm cho chúng trở nên thân thiện với bộ nhớ cache hơn.
- Xây dựng một đống nhị phân đòi hỏi thời gian O (n), tương phản với BST, đòi hỏi thời gian O (n log n).
- Sử dụng con trỏ để thực hiện cây là không cần thiết.
- Dựa vào các biến đổi heap nhị phân (ví dụ, Fibonacci Heap) cung cấp những lợi thế như tăng và giảm thời gian then chốt của O (1) thời gian.
