Cây tìm kiếm nhị phân (BST) với ví dụ

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 trái và phải của nó, được mô hình hóa trong cấu trúc cây và trả về giá trị. BST được thiết kế dựa trên kiến trúc của 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 nút nhanh hơn. Điều này làm cho chương trình thực sự nhanh và chính xác.

Thuộc tính của cây tìm kiếm nhị phân

BST được tạo thành từ 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 nào hoặc có tối đa hai nút con hoặc cây con ở bên trái và bên phải.
Mỗi cây con, còn được gọi là cây tìm kiếm nhị phân, đều 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ị.
Khóa của các nút có trên cây con bên trái nhỏ hơn khóa của nút cha của chúng
Tương tự, 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ó nút chính hoặc cấp độ cha mẹ 11. Bên dưới nó, có các nút/nhánh trái và phải với các giá trị khóa riêng
Cây con bên phải có giá trị khóa lớn hơn nút cha
Cây con bên trái có giá trị hơn nút cha

Tại sao chúng ta cần Cây tìm kiếm nhị phân?

Hai yếu tố chính làm cho cây tìm kiếm nhị phân trở thành giải pháp tối ưu cho mọi vấn đề trong thế giới thực là Tốc độ và Độ chính xác.
Do tìm kiếm nhị phân có định dạng giống nhánh với quan hệ cha-con, nên thuật toán biết các phần tử cần được tìm kiếm ở vị trí nào của cây. Đ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 để xác định vị trí 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 tìm kiếm phức tạp, logic trò chơi mạnh mẽ, 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ể xảy ra ở cấp độ cuối cùng. Tương tự, tất cả các nút đều đầy, hướng về phía bên trái.
Cây nhị phân đầy đủ: Tất cả các nút đều có 2 nút con ngoại trừ nút 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. Ngoài ra, mỗi subnode đều có cùng cấp độ.

Tìm hiểu thêm về Cây nhị phân trong cấu trúc dữ liệu nếu bạn quan tâm đến.

Cây tìm kiếm nhị phân hoạt động như thế nào?

Cây luôn có nút gốc và các nút con khác, dù ở bên trái hay bên phải. Thuật toán thực hiện tất cả các thao tác bằng cách so sánh các giá trị với nút gốc và các nút con tiếp theo của nó trong cây con bên trái hoặc bên phải tương ứng.

Tùy 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 trái hoặc phải của nút gốc.

BST chủ yếu cung cấp ba loại hoạt động sau để bạn sử dụng:

Tìm kiếm: tìm kiếm phần tử từ cây nhị phân
Insert: 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 đều 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.

Tìm kiếm Operasản xuất

Luôn bắt đầu phân tích cây tại nút gốc và sau đó di chuyển xa hơn sang 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ị nhỏ hơn hay lớn hơn nút 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 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.

Mã giả để tìm kiếm trong BST

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

Chèn Operasản xuất

Đây là một hoạt động rất thẳng về phía trước. Đầu tiên, nút gốc được chèn vào, 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ó sẽ được thêm vào cây con bên phải và nếu nó nhỏ hơn gốc, nó sẽ được thêm vào cây con bên trái.

Có danh sách 6 phần tử cần chèn vào BST theo thứ tự từ trái qua 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 như cây con bên phải của 9.

Mã giả để chèn nút vào BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

Xóa bỏ Operations

Để xóa một nút khỏi BST, có một số trường hợp, tức là xóa nút gốc hoặc xóa nút lá. Ngoài ra, sau khi xóa một nút gốc, chúng ta cần nghĩ đến nút gốc.

Giả sử chúng ta muốn xóa một nút lá, chúng ta có thể chỉ cần xóa nó, nhưng nếu chúng ta muốn xóa một gốc, chúng ta cần thay thế giá trị của gốc bằng một nút khác. Hãy lấy ví dụ sau:

Trường hợp 1- Nút không có con: đây là tình huống dễ dàng 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ó khăn nhất và nó hoạt động theo hai quy tắc sau
3a – Trong Thứ tự tiền nhiệm: bạn cần xóa nút có XNUMX nút con và thay bằng giá trị lớn nhất trên cây con bên trái của nút bị xóa
3b – Trong Order Successor: bạn cần xóa nút có XNUMX nút con và thay bằng giá trị lớn nhất trên cây con bên phải của nút bị xóa

Đây là trường hợp xóa đầu tiên trong đó 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 sơ đồ rằng nút 9 có một nút con.
Xóa nút 9 và thay thế bằng nút con 10 và thêm 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ẽ diễn ra dựa trên quy tắc theo thứ tự trước đó, có nghĩa là phần tử lớn nhất trên cây con bên trái của 12 sẽ thay thế nó.
Xóa nút 12 và thay thế bằng nút 10 vì đây 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ẽ diễn ra dựa trên quy tắc In Order Successor, có nghĩa là phần tử lớn nhất trên cây con bên phải của 12 sẽ thay thế nó
3 Xóa nút 12 và thay thế bằng nút 19 vì đây 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

Mã giả để xóa nút

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Điều khoản quan trọng

Insert: 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.
Traversal đặt hàng trước: Duyệt cây theo cách đặt hàng trước.
Traversal theo thứ tự: Duyệt cây theo thứ tự.
Traversal sau thứ tự: Duyệt cây theo cách thứ tự sau.

Tổng kết

BST là một thuật toán cấp 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ị 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 đều đại diện cho nút. Ít nhất một nút cha hoặc nút gốc luôn hiện diện.
Có cây con trái và cây con 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ó 0, một hoặc hai nút con.
Cây tìm kiếm nhị phân hỗ trợ các hoạt động chính như tìm kiếm, chèn và xóa.
Xóa là lệnh phức tạp nhất, có nhiều trường hợp, ví dụ, nút không có nút con, nút có một nút con và nút có hai nút con.
Thuật toán được sử dụng trong các giải pháp thực tế như trò chơi, dữ liệu tự động hoàn thành và đồ họa.