Trong bài đăng này, chúng ta sẽ lại nghiên cứu về cấu trúc dữ liệu Cây, và chi tiết là cây nhị phân tìm kiếm. Đây chính là một cấu trúc dữ liệu được sử dụng khá phổ biến và có tính áp dụng cao. Hãy cùng mình tìm hiểu và cài đặt cây tìm kiếm nhị phân sử dụng ngôn ngữ C/C++ nhé.
Cây nhị phân tìm kiếm là gì ?
Một cây tìm kiếm nhị phân (Binary Search Tree – viết tắt là BST) là một cây mà trong đó tất cả các nút đều có các đặc điểm sau:
- Cây con bên trái của một nút có khóa (key) nhỏ hơn hoặc bằng thành quả khóa của nút cha (của cây con này).
- Cây con bên phải của một nút có khóa lớn hơn hoặc bằng giá trị khóa của nút cha (của cây con này).
Thế nên có khả năng nói rằng, một cây tìm kiếm nhị phân (BST) phân chia tất cả các cây con của nó thành hai phần: cây con bên trái và cây con bên phải và có thể được định nghĩa như sau:
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
Biểu diễn cây tìm kiếm nhị phân (BST)
Cây tìm kiếm nhị phân (BST) là một tập hợp gồm có các nút được sắp đặt theo cách để chúng có thể kéo dài hoặc tuân theo các dấu hiệu của cây tìm kiếm nhị phân. Mỗi một nút thì đều có một khóa và giá trị kết hợp với nó. Trong khi tìm kiếm, khóa cần tìm được so với các khóa trong cây tìm kiếm nhị phân (BST) và nếu như tìm thấy, giá trị liên kết sẽ được thu nhận.
>>>Xem thêm: Mã UTM code là gì? Cách đo lường hiệu quả chiến dịch quảng cáo
Cấu trúc dữ liệu cây
Cây nhị phân là một cấu trúc dữ liệu quan trọng được sử dụng cho mục tiêu lưu giữ dữ liệu. Một cây nhị phân có một điều kiện đặc biệt là mỗi nút có khả năng có tối đa hai nút con. Một cây nhị phân tận dụng lợi thế của hai kiểu cấu trúc dữ liệu: một mảng đã sắp thứ tự và một danh sách liên kết (Linked List), thế nên việc tìm kiếm sẽ nhanh như trong mảng đã sắp thứ tự và các thực hành các bước chèn và xóa cũng sẽ nhanh bằng trong Linked List.
Cây nhị phân tìm kiếm – Node
Node trong cây tìm kiếm nhị phân có dấu hiệu chung là giá trị bên phải luôn luôn lớn hơn giá trị bên trái. Một node trong cây tìm kiếm nhị phân sẽ bao gồm node trái-phải, key thành quả của node đó trong cây.
class BSNode
var key: T?
var left: BSNode?
var right: BSNode?
public var isLeaf: Bool
return left == nil && right == nil
thuộc tính này để lựa chọn node là leaf hay còn node con nữa.
Bậc của node cây nhị phân tìm kiếm
bậc của một nút biểu diễn số con của một nút. nếu nút gốc có bậc là 0, thì nút con tiếp theo sẽ có bậc là 1, và nút cháu của nó sẽ có bậc là 2, …
public func height() -> Int
if isLeaf
return 0
else
return 1 + max(left?.height() ?? 0, Right?.height() ?? 0)
số công việc căn bản trên cây nhị phân tìm kiếm
Chèn thêm node vào cây
Mỗi khi một phần tử được chèn: Trước tiên con người cần chọn lựa vị trí chuẩn xác của phần tử này. Tiếp tục tìm kiếm từ nút gốc, sau đó nếu như dữ liệu là nhỏ hơn giá trị khóa (key), thì tìm kiếm vị trí còn trống ở cây con bên trái và chèn dữ liệu vào đó; Nếu dữ liệu là nhỏ hơn thì tìm kiếm vị trí còn sống ở cây con bên phải và chèn dữ liệu vào đấy.
Duyệt cây nhị phân tìm kiếm
Khi mà bạn muốn xem tất cả node trong cây nhị phân tìm kiếm, con người sẽ tiến hành duyệt cây, như chẳng hạn như ở trên khi duyệt con người sẽ in ra các thành quả cây từ nhỏ nhất đến lớn nhất tương ứng: 1, 2, 5, 7, 9, 10. Việc duyệt cây nhị phân tìm kiếm sẽ bắt đầu từ ngọn (root) sau đó đi sang phía trái tìm đến thành quả nhỏ nhất rồi lần lượt đi hết sang bên phải
Tìm kiếm trên cây nhị phân
Tìm kiếm trên cây nhị phân được làm theo 3 bước
- Nếu như thành quả lớn hơn thành quả ở gốc thì tìm kiếm bên phải.
- Nếu như gía trị nhỏ hơn thành quả gốc thì tìm kiếm bên trái.
- Nếu thành quả node tiếp theo bằng thành quả tìm kiếm thì trả về node tương ứng còn nếu ko trả về nil
>>>Xem thêm: Những phần mềm viết Code tốt nhất cho lập trình viên hiện nay
Nhận xét
Toàn bộ các thực hành các bước searchNode, insertNode, delNode trên CNPTK đều có độ phức tạp trung bình O(h), với h là chiều cao của cây
Trong trong trường hợp tối ưu, CNPTK có n nút sẽ có độ cao h = log2(n). Tiền bạc tìm kiếm khi đó sẽ tương đương tìm kiếm nhị phân trên mảng có thứ tự.
Tuy nhiên, trong trường hợp không tốt nhất, cây có thể bị suy biến thành 1 DSLK (khi mà mỗi nút đều chỉ có 1 con trừ nút lá). Khi đó các thao tác trên sẽ có độ phức tạp O(n). Vì thế cần có cải tiến cấu trúc của CNPTK để đạt cho được chi phí cho các thực hành các bước là log2(n).
Bài viết trên, mình đã chia sẻ tới các bạn chi tiết cấu trúc dữ liệu và giải thuật – Cây nhị phân tìm kiếm. Cảm ơn các bạn đã theo dõi bài viết.
>>Xem thêm: Thụât toán tìm kiếm nhị phân (Binary Search)
Mỹ Phượng-Tổng hợp
Tham khảo: (viblo, voer,…)
