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 theo cấu trúc cây và trả về giá trị. BST được phát minh dựa trên archikiế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à loại bỏ 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.
Thuộc tính của cây tìm kiếm nhị phân
Một BST được tạo thành từ nhiều nút và bao gồm các nút sau:wing thuộc tính:
- 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 để triển khai complex tìm kiếm, 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 các dịch vụ theo dõiwing ba loại hoạt động để 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 hoạt động có cấu trúc và phương pháp thực hiện/phân tích riêng, nhưng phổ biến nhất làplex trong số đó là thao tác Xóa.
Hoạt động tìm kiếm
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ả cho Searching 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 thao tác
Đâ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 hoạt động
Để 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ể xóa nó, nhưng nếu muốn xóa một nút gốc, chúng ta cần thay thế giá trị của nút gốc bằng một nút khác. Hãy theo dõiwing thí dụ:
Thuật toán tìm kiếm nhị phân được thực hiện như thế nào?
Thuật toán tìm kiếm nhị phân hoạt động trên các mảng đã được sắp xếp. Thuật toán bắt đầu bằng việc so sánh một phần tử đứng chính giữa mảng với giá trị cần tìm. Nếu bằng nhau, vị trí của nó trong mảng sẽ được trả về. Nếu giá trị cần tìm nhỏ hơn phần tử này, quá trình tìm kiếm tiếp tục ở nửa nhỏ hơn của mảng.
Cho biết tính chất của một cây nhị phân tìm kiếm là gì?
Cây nhị phân tìm kiếm là cây nhị phân mà trong đó, các phần tử của cây con bên trái đều nhỏ hơn phần tử hiện hành và các phần tử của cây con bên phải đều lớn hơn phần tử hiện hành. Do tính chất này, cây nhị phân tìm kiếm không được có phần tử cùng giá trị.
Xây dựng cây nhị phân tìm kiếm là gì?
Cây tìm kiếm nhị phân là một cấu trúc dữ liệu cơ bản được sử dụng để xây dựng các cấu trúc dữ liệu trừu tượng hơn như các tập hợp, đa tập hợp, các dãy kết hợp. Nếu một BST có chứa các giá trị giống nhau thì nó biểu diễn một đa tập hợp. Cây loại này sử dụng các bất đẳng thức không nghiêm ngặt.
Node gốc là gì?
node gốc [root node]: Là node ở vị trí đầu tiên của cây quyết định. Mọi phương án đều bắt nguồn từ node này. Ở ví dụ trên là [Tổng điểm >= 28.5] node cha [parent node]: Là node mà có thể rẽ nhánh xuống những node khác bên dưới.