Cây tìm kiếm nhị phân là gì?
Cây tìm kiếm nhị phân là một thuật toán nâng cao được sử dụng để phân tích nút, các nhánh bên trái và bên phải của nó, được mô hình hóa theo cấu trúc cây và trả về giá trị. BST được phát minh trên kiến trúc của một thuật toán tìm kiếm nhị phân cơ bản; do đó nó cho phép tra cứu, chèn và xóa các nút nhanh hơn. Điều này làm cho chương trình thực sự nhanh chóng và chính xác.
Trong hướng dẫn Cấu trúc dữ liệu này, bạn sẽ học:
- Cây tìm kiếm nhị phân là gì?
- Các thuộc tính của cây tìm kiếm nhị phân
- Tại sao chúng ta cần một cây tìm kiếm nhị phân?
- Các loại cây nhị phân
- Cách hoạt động của cây tìm kiếm nhị phân?
- Điều khoản quan trọng
Các thuộc tính của cây tìm kiếm nhị phân
Một BST được tạo bởi nhiều nút và bao gồm các thuộc tính sau:
- Các nút của cây được biểu diễn trong mối quan hệ cha-con
- Mỗi nút cha có thể không có nút con hoặc tối đa hai nút con hoặc cây con ở hai bên trái và phải.
- Mỗi cây con, còn được gọi là cây tìm kiếm nhị phân, có các nhánh con ở bên phải và bên trái của chính chúng.
- Tất cả các nút được liên kết với các cặp khóa-giá trị.
- Các khóa của các nút hiện diện trên cây con bên trái nhỏ hơn các khóa của nút cha của chúng
- Tương tự, các khóa của nút cây con bên trái có giá trị nhỏ hơn khóa của nút cha của chúng.
- Có nút chính hoặc nút cha cấp 11. Dưới đó, có các nút / nhánh bên trái và bên phải với các giá trị khóa riêng của chúng
- Cây con bên phải có các giá trị khóa lớn hơn nút cha
- Cây con bên trái có các giá trị hơn nút cha
Tại sao chúng ta cần một cây tìm kiếm nhị phân?
- Hai yếu tố chính khiến cây tìm kiếm nhị phân trở thành giải pháp tối ưu cho bất kỳ vấn đề nào trong thế giới thực là Tốc độ và Độ chính xác.
- Do thực tế là tìm kiếm nhị phân có định dạng giống như nhánh với quan hệ cha-con, thuật toán biết vị trí của cây mà các phần tử cần được tìm kiếm. Điều này làm giảm số lượng so sánh khóa-giá trị mà chương trình phải thực hiện để định vị phần tử mong muốn.
- Ngoài ra, trong trường hợp phần tử cần tìm kiếm lớn hơn hoặc nhỏ hơn nút cha, nút đó sẽ biết phía cây nào cần tìm kiếm. Lý do là, cây con bên trái luôn nhỏ hơn nút cha, và cây con bên phải có giá trị luôn bằng hoặc lớn hơn nút cha.
- BST thường được sử dụng để thực hiện các tìm kiếm phức tạp, logic trò chơi mạnh mẽ, các hoạt động tự động hoàn thành và đồ họa.
- Thuật toán hỗ trợ hiệu quả các hoạt động như tìm kiếm, chèn và xóa.
Các loại cây nhị phân
Ba loại cây nhị phân là:
- Cây nhị phân hoàn chỉnh: Tất cả các cấp độ trong cây đều có đầy đủ các ngoại lệ có thể có của cấp độ cuối cùng. Tương tự như vậy, tất cả các nút đều đầy, hướng về phía xa bên trái.
- Cây nhị phân đầy đủ: Tất cả các nút đều có 2 nút con trừ lá.
- Cây nhị phân cân bằng hoặc hoàn hảo: Trong cây, tất cả các nút đều có hai nút con. Bên cạnh đó, có cùng một mức độ của mỗi subnode.
Cách hoạt động của cây tìm kiếm nhị phân?
Cây luôn có một nút gốc và các nút con khác, cho dù ở bên trái hay bên phải. Thuật toán thực hiện tất cả các hoạt động bằng cách so sánh các giá trị với gốc và các nút con xa hơn của nó trong cây con bên trái hoặc bên phải tương ứng.
Phụ thuộc vào phần tử được chèn, tìm kiếm hoặc xóa, sau khi so sánh, thuật toán có thể dễ dàng loại bỏ cây con bên trái hoặc bên phải của nút gốc.
BST chủ yếu cung cấp ba loại thao tác sau để bạn sử dụng:
- Tìm kiếm: tìm kiếm phần tử từ cây nhị phân
- Chèn: thêm một phần tử vào cây nhị phân
- Xóa: xóa phần tử khỏi cây nhị phân
Mỗi thao tác có cấu trúc và phương pháp thực hiện / phân tích riêng, nhưng phức tạp nhất là thao tác Xóa.
Hoạt động tìm kiếm
Luôn khởi tạo cây phân tích tại nút gốc và sau đó di chuyển xa hơn đến cây con bên phải hoặc bên trái của nút gốc tùy thuộc vào phần tử được định vị là nhỏ hơn hoặc lớn hơn gốc.
- Phần tử cần tìm là 10
- So sánh phần tử với nút gốc 12, 10 <12, do đó bạn chuyển sang cây con bên trái. Không cần phân tích cây con bên phải
- Bây giờ so sánh 10 với nút 7, 10> 7, vì vậy hãy chuyển sang cây con bên phải
- Sau đó so sánh 10 với nút tiếp theo, là 9, 10> 9, tìm trong cây con bên phải
- 10 khớp với giá trị trong nút, 10 = 10, trả về giá trị cho người dùng.
Chèn hoạt động
Đây là một hoạt động rất đơn giản. Đầu tiên, nút gốc được chèn, sau đó giá trị tiếp theo được so sánh với nút gốc. Nếu giá trị lớn hơn gốc, nó được thêm vào cây con bên phải, và nếu nhỏ hơn gốc, nó được thêm vào cây con bên trái.
- Có một danh sách gồm 6 phần tử cần được chèn vào BST theo thứ tự từ trái sang phải
- Chèn 12 làm nút gốc và so sánh các giá trị tiếp theo 7 và 9 để chèn tương ứng vào cây con bên phải và bên trái
- So sánh các giá trị còn lại 19, 5 và 10 với nút gốc 12 và đặt chúng cho phù hợp. 19> 12 đặt nó là con bên phải của 12, 5 <12 & 5 <7, do đó đặt nó là con bên trái của 7.
- Bây giờ so sánh 10, 10 là <12 & 10 là> 7 & 10 là> 9, đặt 10 là cây con bên phải của 9.
Xóa hoạt động
Xóa là tiên tiến và phức tạp nhất trong số tất cả các thao tác khác. Có nhiều trường hợp được xử lý để xóa trong BST.
- Trường hợp 1- Nút không có con: đây là trường hợp dễ nhất, bạn chỉ cần xóa nút không có con nào ở bên phải hoặc bên trái.
- Trường hợp 2 - Nút có một nút con: khi bạn xóa nút, chỉ cần kết nối nút con của nó với nút cha của giá trị đã xóa.
- Trường hợp 3 Nút có hai con: đây là tình huống khó nhất và nó hoạt động theo hai quy tắc sau
- 3a - Theo Thứ tự Tiền nhiệm: bạn cần xóa nút có hai nút con và thay thế nó bằng giá trị lớn nhất trên cây con bên trái của nút đã xóa
- 3b - Trong Đơn hàng kế vị: bạn cần xóa nút có hai nút con và thay thế nó bằng giá trị lớn nhất trên cây con bên phải của nút đã xóa
- Đây là trường hợp xóa đầu tiên mà bạn xóa một nút không có nút con. Như bạn có thể thấy trong sơ đồ 19, 10 và 5 không có con. Nhưng chúng tôi sẽ xóa 19.
- Xóa giá trị 19 và xóa liên kết khỏi nút.
- Xem cấu trúc mới của BST không có 19
- Đây là trường hợp xóa thứ hai trong đó bạn xóa một nút có 1 nút con, như bạn có thể thấy trong biểu đồ rằng 9 nút có một nút con.
- Xóa nút 9 và thay thế nó bằng nút con 10 và thêm một liên kết từ 7 đến 10
- Xem cấu trúc mới của BST không có 9
- Ở đây bạn sẽ xóa nút 12 có hai nút con
- Việc xóa nút sẽ xảy ra dựa trên quy tắc tiền nhiệm theo thứ tự, có nghĩa là phần tử lớn nhất ở cây con bên trái của 12 sẽ thay thế nó.
- Xóa nút 12 và thay thế nó bằng 10 vì nó là giá trị lớn nhất trên cây con bên trái
- Xem cấu trúc mới của BST sau khi xóa 12
- 1 Xóa nút 12 có hai nút con
- 2 Việc xóa nút sẽ xảy ra dựa trên quy tắc Theo thứ tự kế thừa, có nghĩa là phần tử lớn nhất ở cây con bên phải của 12 sẽ thay thế nó
- 3 Xóa nút 12 và thay thế nó bằng 19 vì nó là giá trị lớn nhất trên cây con bên phải
- 4 Xem cấu trúc mới của BST sau khi xóa 12
Điều khoản quan trọng
- Chèn - Chèn một phần tử vào cây / tạo cây.
- Tìm kiếm - Tìm kiếm một phần tử trong cây.
- Đặt hàng trước Traversal - Duyệt cây theo cách đặt hàng trước.
- Inorder Traversal - Duyệt cây theo thứ tự.
- Postorder Traversal - Duyệt cây theo cách có thứ tự sau.
Tóm lược
- BST là một thuật toán mức nâng cao thực hiện các hoạt động khác nhau dựa trên việc so sánh các giá trị của nút với nút gốc.
- Bất kỳ điểm nào trong hệ thống phân cấp cha-con đại diện cho nút. Ít nhất một nút cha hoặc nút gốc vẫn luôn hiện diện.
- Có một cây con bên trái và cây con bên phải. Cây con bên trái chứa các giá trị nhỏ hơn nút gốc. Tuy nhiên, cây con bên phải chứa giá trị lớn hơn nút gốc.
- Mỗi nút có thể có không, một hoặc hai nút con.
- Cây tìm kiếm nhị phân tạo điều kiện cho các hoạt động chính như tìm kiếm, chèn và xóa.
- Xóa là phức tạp nhất có nhiều trường hợp, ví dụ, một nút không có con, nút có một con và nút có hai con.
- Thuật toán được sử dụng trong các giải pháp trong thế giới thực như trò chơi, dữ liệu tự động hoàn thành và đồ họa.