5 Phút Thông Thạo Binary Search Tree Là Gì ? Binary Search Tree Là Gì

Ngoài am hiểu giải thuật thì có kiến thức về cấu trúc dữ liệu là điều kiện kiên quyết để trở thành một lập trình viên chuyên nghiệp. Trong bài này mình giới thiệu tới các bạn một trong những cấu trúc dữ liệu cơ bản nhất cũng như cách hoạt động của nó. Đó chính là cây tìm kiếm nhị phân – Binary Search Tree.

Đang xem: Binary search tree là gì

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

Cây tìm kiếm nhị phân có tên tiếng anh là Binary Search Tree (BST), là một trong những cấu trúc dữ liệu cơ bản bên cạnh queue, stack, linked-list, array. Cây tìm kiếm nhị phân là 1 dạng đồ thị nhưng các nút (node) của cây phải có những tính chất sau:

Mỗi node chỉ có thể có tối đa 2 node conGiá trị của node con bên trái phải nhỏ hơn node cha của nóGiá trị của node con bên phải lớn hơn node cha của nó

Tính chất cũng phải đúng cới các node con của 2 node con trên, nói cách khác giá trị tất cả các con bên trái của 1 node phải nhỏ hơn giá trị của node đó và giá tị tất cả các con bên phải của node đó phải lớn hơn giá tị của nó. Sự so sánh giá trị ở trên có thể là so sánh toán học, so sánh chuỗi kí tự,…

Đặc biệt trong 1 cây tìm kiếm nhị phân không cho phép 2 giá trị trùng nhau. Chính quy luật và cách sắp xếp như trên cấu trúc BST đã giúp sắp xếp dữ liệu theo một cách có trật tự, từ đó giúp người sử dụng dễ dàng hơn trong việc tổ chức dữ liệu cũng như việc tìm kiếm.

Sau đây là một vài khái niệm trong cây tìm kiếm nhị phân:

Root node (nút gốc) : node đầu tiên của cây.Leaf node (nút lá): node không có con trái và con phải.Internal node : những node không phải nút gốc cũng không phải nút lá.Level (tầng): như hình minh họa trên chúng ta có 2 cây với 3 tầng.

Về cơ bản chúng ta có 3 loại cây nhị phân:

Full binary tree: Những node không phải nút lá đều có 2 con trái và phải.

Complete binary tree: Tất cả các tầng đều chứa đầy nodes ngoại trừ tầng cuối có thể đầy hoặc không nhưng các node tầng cuối phải đc xếp lần lượt từ trái đến phải.

Perfect binary tree: tất cả nodes đều có 2 con và các nút lá ở cùng một level.

Với cây tìm kiến nhị phân chúng ta có những tác vụ cơ bản sau:

Search: Tìm kiếm.Insert: Thêm 1 node.Remove: Xóa 1 node.Traversal: Duyệt cây với 3 loại cơ bản: pre-oder traversal, In-order traversal, post-order traversal.

Bên trên là những khái niệm cơ bản về cấu trúc dữ liệu cây nói chung và cây tìm kiếm nhị phân nói riêng, sau đây chúng ta đến với cách hoạt động của các tác vụ trong cây tìm kiếm nhị phân.

2. Cây tìm kiếm nhị phân dùng để làm gì?

2.1. Search

Để bắt đầu hoạt động tìm kiếm một giá trị x cho trước, chúng ta bắt đầu từ nút gốc (root). Nếu giá trị x nhỏ hơn giá trị của root thì chuyển đến so sánh với node con trái của root vì như đã nói ở trên mọi node bên trái root sẽ nhỏ hơn root nên nếu giá trị x có tồn tại thì chỉ có thể ở bên trái root, còn với x lớn hơn giá trị của root thì chuyển đến so sánh với node con phải của root.

Tiếp tục quá trình xét như trên với các node tiếp theo đến khi tìm được, còn nếu đến nút lá mà so sánh x không bằng giá trị nút lá thì xác nhận không tìm thấy.

Cùng xét ví dụ sau:

Trường hợp thứ nhất, ta muốn xác nhận 4 có nằm trong cây trên hay không thì các node ta sẽ đi qua là 5,3. Ban đầu bắt đầu từ 5, vì 43 nên so sánh tiếp với con phải của 3 là 4, ở đây 4 = 4 nên kết quả là có tìm thấy.

Trường hợp thứ 2, ta muốn xác nhận 7 có nằm trong cây trên không? Các node đi qua sẽ là 5,8,6 (không tìm thấy). Ban đầu chúng ta cũng bắt đầu từ root node là 5 sau đó lần lượt đến 8 và 6, cuối cùng xác nhận không tìm thấy.

Đây chính là ưu điểm của cấu trúc cây tìm kiếm nhị phân, độ phức tạp của thuật toán tìm kiếm này là O(logn), với trường hợp xấu nhất khi tất cả cá node chỉ có con phải hoặc chỉ có con trái thì độ phức tạp là O(n), ta có thể thấy rằng với trường hợp xấu nhất này cây nhị phân sẽ giống với cấu trúc mảng.

Xem thêm: Bonfire Là Gì – Nghĩa Của Từ Bonfires Trong Tiếng Việt

Chúng ta nên tránh trường hợp này khi xây dựng cấu trúc dữ liệu với cây nhị phân tìm kiếm.

2.2. Insert

Khi muốn thêm một giá trị x vào cây nhị phân, ta bắt đầu tìm kiếm từ nút gốc (root), nếu giá trị x nhỏ hơn giá trị nút gốc thì tìm vị trí trống của cây con bên trái nút gốc, nếu x lớn hơn giá trj nút gốc ta tìm vị trí trống của cây con bên phải nút gốc. Trường hợp tìm được giá trị của 1 node trong cây bằng với x thì xác nhận x đã tồn tại trong cây.

Với ví dụ trong ảnh trên, ta cần thêm 4 vào trong cây nhị phân cho trước. Bắt đầu từ nút gốc là 6, vì 4 3 và có một ví trí trống phía bên phải của nút 3 vây nên đó là vị trí phù hợp để them 4 vào trong cây.

2.3. Remove

Trong hoạt động xóa 1 node của cây nhị phân chúng ta sẽ gặp phải 3 trường hợp sau:

Node cần xóa chỉ có 1 node con (trái hoặc phải)Node cần xóa không có node conNode cần xóa có cả 2 node

Với trường hợp đầu tiên node cần xóa có 1 node con, ta chỉ cần thay vị trí của node con đó với node cần xóa.

Với trường hợp node cần xóa không có node con thì chúng ta đơn giản chỉ cần xóa vị trí node đó khỏi cây.

Trường hợp cuối cùng node cần xóa có cả 2 node con. Với trường hợp này việc của ta cần làm là tìm được 1 node thế (successor) để lắp vào vị trí của node cần xóa, nói cách khác node thế phải có tính chất bé hơn tất cả node bên trái của node cần xóa và lớn hơn tất cả các node bên phải của node cần xóa.

Với cây nhị phân trong hình, khi ta muốn xóa node 5 thì node 6 chính là node thế cho node 5, node 6 còn được gọi là left-most tree, tức node trái cùng của 1 cây. Sau khi thay node 5 bằng node 6 ta cần xóa node 6 ở vị trí cũ đi, khi này ta quay trở lại trường hợp xóa 1 node có 1 node con tại vì node 6 cũ có 1 node còn là 7. Đây là kết quả sau khi xóa node 5:

Node thế (successor) có thể là left-most của cây con bên phải hoặc right-most tree của cây con bên trái. Với left-most tree được định nghĩa là con trái cùng hay giá trị nhỏ nhất trong cây nhị phân, right-most là conphair cùng, hay giá trị lớn nhất trong cây nhị phân

2.4 Pre-order traversal

Với cách duyệt này ta sẽ đi qua node cha trước sau đến node con trái rồi mới đến node con phải.

Với cây trên thứ tự các code sau khi duyệt là: 6,3,1,10,9,12.

2.5 In-order traversal

Trong cách duyệt in-order, duyệt lần lượt node con trái sau đến node cha rồi đến node con phải.

Duyệt cây nhị phân trên với inorder traversal ta được một dãy tăng dần: 1,3,6,9,10,12.

2.6 Post-order traversal

Ta duyệt lần lượt node con trái, node con phải rồi đến node cha.

Xem thêm: Điện Tử Y Sinh Là Gì ? Cơ Hội Nghề Nghiệp Ra Sao? Thông Tin Cần Biết Về Ngành Kỹ Thuật Y Sinh

Với cây trên thứ tự các code sau khi duyệt là1,3,9,12,10,6.

Lời kết

Qua bài viết này mình và các bạn đã tìm hiểu về khái niệm của cây tìm kiếm nhị phân và cách hoạt động của nó. Nếu thấy bài viết có ý nghĩa bạn đọc hãy để lại đánh giá cũng như commemt những thắc mắc để mọi người cùng giải đáp. Cảm ơn bạn đọc, chúc bạn đọc thành công trên con đường học tập!