Cây nhị phân (Binary tree)

Binary tree là sản phẩm hoàn hảo của việc ứng dụng đệ qui  kết hợp với con trỏ, nó ra đời để cải tiến nhược điểm của cấu trúc tiền nhiệm "danh sách liên kết", vậy nhược điểm của danh sách liên kết là gì? tại sao cần cải tiến?
để rõ hơn hãy xem bài toán sau:

Bài toán tìm kiếm:

Đề bài: "Viết chương trình để tìm kiếm toàn bộ thông tin về một người bất kỳ trên thế giới thông qua ID của họ, giả sử mỗi người có một ID khác nhau, được đánh số bắt đầu từ 0 và tăng dần".

Lời giải:

Trước khi biết đến Binary tree, danh sách liên kết là khái niệm đầu tiên mà bạn có thế nghĩ đến để giải quyết bài toán này, bạn sẽ phải tạo ra một danh sách liên kết mà mỗi node sẽ chứa toàn bộ thông tin và ID tương ứng của một người cụ thể, khi đó, nếu muốn tìm kiếm thông tin về một người việc của bạn chỉ là duyệt tuần tự qua tất cả các node và so sánh ID cho đến khi tìm ra node có ID trùng khớp. Xong!

Nhưng:

Hiện nay thế giới có khoảng 6 tỷ người, tức là danh sách liên kết của bạn sẽ có xấp xỉ 6 tỷ node, giả sử thời gian để bạn so sánh ID của một người là 1s, nếu may mắn thông tin của người cần tìm ở node thứ 100 thì bạn chỉ mất gần 2 phút để tìm ra, khá lâu nhưng cũng chấp nhận được, còn giả sử thông tin đó ở node thứ 4 tỷ, vậy bạn mất 4 tỷ giây tương đương 125 năm để tìm ra thông tin về người đó, đây chính là nhược điểm không thể chấp nhận được của danh sách liên kết.

Yêu cầu:

"Phải tìm ra kết quả trong khoảng thời gian nhỏ hơn 1 phút (<60s)".
Yêu sách này là bất khả thi với danh sách liên kết, nhưng Binary tree thì không, thậm chí nó còn có thể làm tốt hơn.

Binary tree là gì?

Giống như tên của nó, mỗi node trong cây nhị phân sẽ trỏ đến hai node tiếp theo, giống như 2 cành rẽ ra từ một thân cây. Hình 1 mô tả một Binary tree đơn giản nhất, trong đó node_0 là parent node của toàn bộ cây, node_1 và node_2 là children node của node_0.

Hình 1: Binary tree đơn giản nhất

Chú ý: Các node phải phân bố theo qui tắc children node bên trái có giá trị nhỏ hơn parent node, children node bên phải có giá trị lớn hơn parent node.

Hình 2: Blance binary tree

Trong Hình 2, node_2 vừa đóng vai trò là children node của node_0 và là parent node của node_5 và node_6, tổ hợp node_2, node_5, node_6 được gọi là một sub-tree, mỗi sub-tree đề có đầu đủ tính năng giống như một Binary tree hoàn chỉnh, hay nói cách khác "một Binary tree là tập hợp của nhiều Binary tree". Điều đó khiến ta liên tưởng đến tính đệ qui "Một hàm gọi chính nó nhiều lần", nhưng giờ vẫn quá sớm, chúng ta sẽ nhắc tới vấn đề này sau ^^.

Giải quyết bài toán tìm kiếm

Balance binary tree - Hình 2 là một binary tree lý tưởng, nghĩa là số lượng node bên trái bằng số lượng node bên phải và parent node của toàn bộ binary tree sẽ có giá trị chính giữa khoảng giá trị của tất cả các node (Hình 2 mô tả ba tầng trên của một balance binary tree có 6 tỷ node, parent node của toàn bộ binary tree có giá trị là 3 tỷ). 

Quay lại với bài toán ban đầu: Bạn sẽ bắt đầu tìm kiếm tại parent node của toàn bộ binary tree, đầu tiên bạn sẽ so sánh ID cần tìm với ID của parent node đầu tiên đó, bạn thấy 4 tỷ > 3 tỷ do đó ngay lập tức bạn loại bỏ được sub-tree bên trái vì sub-tree bên tái chỉ chứa các ID nhỏ hơn 3 tỷ, giờ bạn chỉ quan tam sub-tree bên phải mà thôi.

Tiếp theo bạn sẽ tiếp tục so sánh với ID của parent node đầu tiên của sub-tree bên phải (children node bên phải của parent node toàn bộ binary tree), vì 4 tỷ < 4.5 tỷ do đó bạn tiếp tục loại bỏ được 1.5 tỷ trường hợp tiếp theo.
Cứ như vậy, sau mỗi lần so sánh bạn sẽ loại bỏ được một nữa số trường hợp không đúng, đo đó sẽ rất nhanh chóng để bạn tìm ra kết quả.

Số lần thực hiện so sánh tối đa để tìm ra kết quả là log2(6000000000) = 32, tức bạn phải mất tối đa 32s để tìm thông tin bất kỳ về một người nào.
Kết quả thât ấn tượng, trong trường hợp này nó hoàn toàn thỏa mãn yêu cầu < 60s.