/ / Cây tìm kiếm nhị phân là gì?

Cây tìm kiếm nhị phân là gì?

Cây tìm kiếm nhị phân là một trong những cấu trúc dữ liệu khác nhau giúp chúng ta tổ chức và sắp xếp dữ liệu. Đó là một cách hiệu quả để lưu trữ dữ liệu theo hệ thống phân cấp và rất linh hoạt.

Trong bài viết này, chúng ta sẽ xem xét kỹ hơn cách thức hoạt động của nó — cùng với các thuộc tính và ứng dụng của nó.

Cây tìm kiếm nhị phân là gì?


Cấu trúc dữ liệu cây tìm kiếm nhị phân
Tín dụng hình ảnh: Pat Hawks / Wikimedia Commons

Cây tìm kiếm nhị phân là một cấu trúc dữ liệu bao gồm các nút — tương tự như Danh sách được liên kết. Có thể có hai loại nút: nút cha và nút con. Nút gốc là điểm đầu của cấu trúc phân nhánh thành hai nút con, được gọi là nút bên trái và nút bên phải.

Mỗi nút chỉ có thể được tham chiếu bởi cha của nó và chúng ta có thể duyệt qua các nút của cây tùy thuộc vào hướng. Cây tìm kiếm nhị phân có ba thuộc tính chính:

  1. Nút bên trái nhỏ hơn nút cha của nó.

  2. Nút bên phải lớn hơn nút cha của nó.

  3. Các cây con bên trái và bên phải phải là Cây tìm kiếm nhị phân.

Cây tìm kiếm nhị phân hoàn hảo đạt được khi tất cả các cấp được lấp đầy và mọi nút đều có nút con bên trái và bên phải.

Liên quan: Thư viện khoa học dữ liệu cho Python mà mọi nhà khoa học dữ liệu nên sử dụng

Các hoạt động cơ bản của cây tìm kiếm nhị phân

Bây giờ bạn đã hiểu rõ hơn về Cây tìm kiếm nhị phân là gì, chúng ta có thể xem các hoạt động cơ bản của nó bên dưới.

1. Hoạt động Tìm kiếm

Tìm kiếm cho phép chúng tôi xác định một giá trị cụ thể có trong cây. Chúng ta có thể sử dụng hai loại tìm kiếm: tìm kiếm theo chiều rộng (BFS) và tìm kiếm theo chiều sâu (DFS). Tìm kiếm theo chiều rộng là một thuật toán tìm kiếm bắt đầu từ nút gốc và di chuyển theo chiều ngang, từ bên này sang bên kia, cho đến khi tìm thấy mục tiêu. Mỗi nút được truy cập một lần trong quá trình tìm kiếm này.

Mặt khác, tìm kiếm theo chiều sâu đi qua cây theo chiều dọc – bắt đầu từ nút gốc và làm việc xuống một nhánh duy nhất. Nếu mục tiêu được tìm thấy, hoạt động kết thúc. Nhưng nếu không, nó sẽ tìm kiếm các nút khác.

2. Chèn hoạt động

Thao tác chèn sử dụng thao tác tìm kiếm để xác định vị trí nơi nút mới sẽ được chèn. Quá trình bắt đầu từ nút gốc và quá trình tìm kiếm bắt đầu cho đến khi đạt được đích. Có ba trường hợp cần xem xét với sự chèn.

  • Trường hợp 1: Khi không có nút nào tồn tại. Nút được chèn vào sẽ trở thành nút gốc.

Cây tìm kiếm nhị phân Chèn nút gốc
  • Trường hợp 2: Không có con. Trong trường hợp này, nút sẽ được so sánh với nút gốc. Nếu nó lớn hơn, nó sẽ trở thành đứa trẻ phù hợp; nếu không, nó sẽ trở thành đứa con trái.

Cây tìm kiếm nhị phân Chèn nút con
  • Trường hợp 3: Khi gốc và con của nó có mặt. Nút mới sẽ được so sánh với mỗi nút trên đường dẫn của nó để xác định nút nào nó sẽ truy cập tiếp theo. Nếu nút lớn hơn nút gốc, nó sẽ đi qua cây con bên phải hoặc nếu không thì bên trái. Tương tự, so sánh được thực hiện ở mỗi cấp độ để xác định xem nó sẽ đi sang phải hay sang trái cho đến khi nó đến đích.


Cây tìm kiếm nhị phân Chèn nhiều nút

3. Thao tác Xóa

Thao tác xóa được sử dụng để xóa một nút cụ thể trong cây. Việc xóa được coi là phức tạp vì sau khi xóa một nút, cây phải được tổ chức lại cho phù hợp. Có ba trường hợp chính cần xem xét:

  • Trường hợp 1: Xóa một nút lá. Nút lá là nút không có nút con nào. Đây là cách dễ nhất để loại bỏ vì nó không ảnh hưởng đến bất kỳ nút nào khác; chúng tôi chỉ cần đi ngang qua cái cây cho đến khi chúng tôi đến được nó và xóa nó đi.

Cây tìm kiếm nhị phân Xóa nút lá
  • Trường hợp 2: Xóa một nút có một nút con. Xóa nút cha với một nút sẽ dẫn đến việc con chiếm vị trí của nó và tất cả các nút tiếp theo sẽ tăng lên một cấp. Sẽ không có thay đổi về cấu trúc cây con.

Cây tìm kiếm nhị phân Xóa nút mẹ 1
  • Trường hợp 3: Xóa một nút có hai nút con. Khi chúng ta phải loại bỏ một nút có hai nút con, trước tiên chúng ta phải tìm một nút tiếp theo có thể thay thế vị trí của nó. Hai nút có thể thay thế nút đã bị loại bỏ, nút kế nhiệm hoặc nút tiền nhiệm nhỏ hơn. Cây kế cận nhỏ hơn là con ngoài cùng bên trái của cây con bên phải và tiền thân nhỏ hơn là con ngoài cùng bên phải của cây con bên trái. Chúng tôi sao chép nội dung của nút kế nhiệm / tiền nhiệm và xóa người kế nhiệm / tiền nhiệm inorder.


Cây tìm kiếm nhị phân Xóa nút mẹ 2

Liên quan: Cách xây dựng cấu trúc dữ liệu với lớp JavaScript ES6

Làm thế nào để Travers một cây tìm kiếm nhị phân

Truyền tải là quá trình mà qua đó chúng tôi điều hướng Cây tìm kiếm nhị phân. Nó được thực hiện để xác định vị trí một mục cụ thể hoặc để in phác thảo của cây. Chúng ta luôn bắt đầu từ nút gốc và phải đi theo các cạnh để đến các nút khác. Mỗi nút nên được coi là một cây con và quá trình này được lặp lại cho đến khi tất cả các nút được truy cập.

  • Truyền theo thứ tự: Di chuyển theo thứ tự sẽ tạo ra một bản đồ theo thứ tự tăng dần. Với phương pháp này, chúng ta bắt đầu từ cây con bên trái và tiếp tục đến cây con gốc và cây con bên phải.

Binary Search Tree Inorder Sort
  • Giao dịch đặt hàng trước: Trong phương pháp này, nút gốc được truy cập đầu tiên, tiếp theo là cây con bên trái và cây con bên phải.

Cây tìm kiếm nhị phân Sắp xếp trước
  • Giao dịch sau đơn đặt hàng: Quá trình truyền tải này liên quan đến việc truy cập vào nút gốc lần cuối. Chúng ta bắt đầu từ cây con bên trái, sau đó đến cây con bên phải, và sau đó là nút gốc.


Binary Search Tree Postorder Sắp xếp

Ứng dụng trong thế giới thực

Vì vậy, làm thế nào để chúng ta sử dụng các thuật toán cây tìm kiếm nhị phân? Như có thể phỏng đoán, chúng cực kỳ hiệu quả trong việc tìm kiếm và phân loại. Sức mạnh lớn nhất của cây nhị phân là cấu trúc có tổ chức của chúng. Nó cho phép thực hiện tìm kiếm với tốc độ đáng kể bằng cách cắt giảm một nửa lượng dữ liệu chúng ta cần phân tích cho mỗi lần chuyển.

Cây tìm kiếm nhị phân cho phép chúng tôi duy trì một cách hiệu quả tập dữ liệu thay đổi động ở dạng có tổ chức. Đối với các ứng dụng có dữ liệu được chèn và gỡ bỏ thường xuyên, chúng rất hữu ích. Công cụ trò chơi điện tử sử dụng một thuật toán dựa trên cây được gọi là phân vùng không gian nhị phân để giúp hiển thị các đối tượng một cách có trật tự. Microsoft Excel và hầu hết các phần mềm bảng tính sử dụng cây nhị phân làm cấu trúc dữ liệu cơ bản của chúng.

Bạn có thể ngạc nhiên khi biết rằng mã Morse sử dụng cây tìm kiếm nhị phân để mã hóa dữ liệu. Một lý do nổi bật khác khiến Cây tìm kiếm nhị phân rất hữu ích là do chúng có nhiều biến thể. Tính linh hoạt của chúng đã dẫn đến nhiều biến thể được tạo ra để giải quyết tất cả các loại vấn đề. Khi được sử dụng đúng cách, Cây tìm kiếm nhị phân là một tài sản lớn.

Cây tìm kiếm nhị phân: Điểm khởi đầu hoàn hảo

Một trong những cách chính để đánh giá chuyên môn của một kỹ sư là thông qua kiến ​​thức và ứng dụng của họ về cấu trúc dữ liệu. Cấu trúc dữ liệu rất hữu ích và có thể giúp tạo ra một hệ thống hiệu quả hơn. Cây tìm kiếm nhị phân là phần giới thiệu tuyệt vời về cấu trúc dữ liệu cho bất kỳ nhà phát triển nào mới bắt đầu.


javascript-array-method
15 phương pháp mảng JavaScript mà bạn nên nắm vững ngay hôm nay

Bạn muốn hiểu các mảng JavaScript nhưng không thể hiểu rõ về chúng? Kiểm tra các ví dụ về mảng JavaScript của chúng tôi để được hướng dẫn.

Đọc tiếp


Giới thiệu về tác giả

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *