5 Phút Thông Thạo Binary Search Tree: Khám phá cấu trúc dữ liệu tuyệt vời của lập trình viên chuyên nghiệp
Cây tìm kiếm nhị phân là gì? Đó là một trong những câu hỏi thường xuyên gặp của những ai muốn trở thành lập trình viên chuyên nghiệp. Trên thực tế, kiến thức về cấu trúc dữ liệu là một phần quan trọng không thể thiếu trong việc hiểu về giải thuật. Và trong bài viết này, chúng ta sẽ cùng tìm hiểu về cây tìm kiếm nhị phân – một cấu trúc dữ liệu cơ bản nhưng cực kỳ quan trọng.
Cây tìm kiếm nhị phân là gì?
Cây tìm kiếm nhị phân, trong tiếng Anh gọi là Binary Search Tree (BST), là một trong những cấu trúc dữ liệu cơ bản kế bên queue, stack, linked-list và array. Cây tìm kiếm nhị phân là một dạng đồ thị đặc biệt, mà các nút (node) trong cây này phải tuân thủ những quy tắc sau:
- Mỗi node chỉ có thể có tối đa 2 node con.
- Giá trị của node con bên trái phải nhỏ hơn giá trị của node cha.
- Giá trị của node con bên phải lớn hơn giá trị của node cha.
Quy tắc trên cũng áp dụng cho các node con của 2 node con đó nữa. Điều này có nghĩa là giá trị tất cả các node con bên trái của một node phải nhỏ hơn giá trị của node đó, và giá trị tất cả các node con bên phải của một node phải lớn hơn giá trị của node đó. So sánh giá trị ở đây có thể là so sánh toán học, so sánh chuỗi kí tự,…
Cây tìm kiếm nhị phân còn có một số khái niệm quan trọng như:
- 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 là nút gốc cũng không phải là nút lá.
- Level (tầng): mỗi tầng trong cây.
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 là nút lá đều có cả 2 con trái và phải.
- Complete binary tree: Tất cả các tầng đều chứa đầy node, ngoại trừ tầng cuối có thể đầy hoặc không nhưng các node tại 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ả các node đều có cả 2 con và các node lá ở cùng một tầng.
Với cây tìm kiếm nhị phân, chúng ta có những tác vụ cơ bản sau:
- Tìm kiếm (Search)
- Thêm một node (Insert)
- Xóa một node (Remove)
- Duyệt cây (Traversal) với 3 loại: pre-oder traversal, in-order traversal, post-order traversal.
Trên đây 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. Tiếp theo, chúng ta sẽ tìm hiểu về cách hoạt động của các tác vụ trong cây tìm kiếm nhị phân.
Cây tìm kiếm nhị phân dùng để làm gì?
2.1. Tìm kiếm (Search)
Để tìm kiếm một giá trị x trong cây nhị phân, ta bắt đầu từ nút gốc (root). Nếu giá trị x nhỏ hơn giá trị của root, ta tiếp tục 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 tồn tại, nó chỉ có thể nằm ở bên trái root. Còn nếu giá trị x lớn hơn giá trị của root, ta so sánh với node con phải của root.
Quá trình tìm kiếm tiếp tục như vậy cho đến khi tìm được giá trị hoặc đến nút lá mà giá trị x không bằng giá trị của nút lá. Khi đó, ta xác nhận rằng giá trị x không có trong cây.
Ví dụ:
- Để xác nhận xem 4 có nằm trong cây hay không, ta sẽ đi qua các node là 5,3. Ban đầu bắt đầu từ 5, vì 4 nằm bên phải 3, nên tiếp theo ta so sánh với con phải của 3 là 4. Vì 4 = 4, nên kết quả là tìm thấy.
- Để xác nhận xem 7 có nằm trong cây hay không, ta đi qua các node là 5,8,6 (không tìm thấy). Ban đầu bắt đầu từ root node là 5, sau đó đi qua 8 và 6, cuối cùng xác nhận là không tìm thấy.
Đây chính là ưu điểm của cây tìm kiếm nhị phân. Độ phức tạp của thuật toán tìm kiếm là O(logn), với trường hợp xấu nhất khi tất cả 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 trong trường hợp xấu nhất này, cây nhị phân sẽ trở thành một cấu trúc dữ liệu giống với mảng.
2.2. Thêm một node (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, ta tìm vị trí trống của cây con bên trái nút gốc. Ngược lại, nếu giá trị x lớn hơn giá trị 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 một node trong cây bằng x, ta xác nhận rằng x đã tồn tại trong cây.
Ví dụ:
- Với ví dụ trên, khi chúng ta muốn thêm số 4 vào cây nhị phân. Bắt đầu từ nút gốc là 6, ta thấy rằng giỏi 4 và 3 đều có một vị trí trống phía bên phải của nút 3. Do đó, đó là vị trí phù hợp để thêm số 4 vào cây.
2.3. Xóa một node (Remove)
Trong quá trình xóa một node của cây nhị phân, ta gặp phải 3 trường hợp sau:
- Node cần xóa chỉ có một node con (trái hoặc phải).
- Node cần xóa không có node con.
- Node cần xóa có cả 2 node con.
Với trường hợp đầu tiên, khi node cần xóa có một node con, ta chỉ cần thay thế vị trí của node con đó với node cần xóa.
Ví dụ:
Với trường hợp node cần xóa không có node con, ta đơn giản chỉ cần xóa node đó khỏi cây.
Ví dụ:
Trường hợp cuối cùng, khi node cần xóa có cả 2 node con. Ta cần tìm một node thế (successor) để thay thế node cần xóa. 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, node 6 sẽ 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 một cây. Sau khi thay thế node 5 bằng node 6, ta cần xóa node 6 ở vị trí cũ đi. Khi đó, ta lại rơi vào trường hợp xóa một node có một node con, vì node 6 cũ có một node con nữa là 7.
Ví dụ:
Node thế (successor) có thể là left-most tree của cây con bên phải hoặc right-most tree của cây con bên trá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 tree là con phải cùng hay giá trị lớn nhất trong cây nhị phân.
2.4. Pre-order traversal
Trong cách duyệt pre-order, ta duyệt node cha trước sau đó đến node con trái và node con phải.
Ví dụ:
Đối với cây trên, thứ tự duyệt là: 6,3,1,10,9,12.
2.5. In-order traversal
Trong cách duyệt in-order, ta duyệt lần lượt node con trái, node cha và node con phải.
Ví dụ:
Duyệt cây trên sẽ cho ra một dãy số tăng dần: 1,3,6,9,10,12.
2.6. Post-order traversal
Trong cách duyệt post-order, ta duyệt lần lượt node con trái, node con phải và node cha.
Ví dụ:
Duyệt cây trên sẽ cho ra dãy số: 1,3,9,12,10,6.
Lời kết
Qua bài viết này, chúng ta đã 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ó. Hi vọng rằng bạn đã có những phút giây thú vị và hữu ích khi đọc bài viết này. Nếu bạn muốn tìm hiểu thêm hoặc có bất kỳ thắc mắc, đừng ngần ngại để lại đánh giá và comment dưới đây. Cảm ơn bạn đã đọc, chúc bạn thành công trên con đường học tập!