Cây nhị phân (Binary tree) là gì? Cơ chế hoạt động của nó

Trong bài viết này, codehow sẽ giới thiệu đến các bạn một dạng cấu trúc dữ liệu mới đó là cấu trúc cây nhị phân. Chúng ta sẽ tìm hiểu cây nhị phân là gì? cơ chế hoạt động của nó.

Tới bây giờ thì mình đã giới thiệu cho các bạn cấu trúc dữ liệu để lưu trữ như: mảng một chiều, mảng hai chiều, DSLK đơn, DSLK đôi. Tuy nhiên cấu trúc cây mà đặc biệt là cây nhị phân là một dạng cấu trúc lưu trữ tối ưu nhất.

Ví dụ: Trong máy tính các bạn đang lưu trữ thư mục dưới dạng cây. Nghĩa là bên trong thư mục mẹ có thể lưu trữ thêm các thư mục con. Điều này giúp chúng ta phân lớp và dễ dàng tìm kiếm, lưu trữ.

Vậy cấu trúc cây nhị phân là gì? cơ chế hoạt động của nó như thế nào thì ngay bây giờ hãy bắt đầu tìm hiểu cùng mình thôi nhé.

Cấu trúc dữ liệu dạng cây là gì?

Khác với các dạng lưu trữ khác như mảng, DSLK đơn hay DSLK đôi. Cấu trúc dạng cây được xem là cấu trúc dữ liệu lưu trữ tối ưu nhất trong các dạng lưu trữ mình đã đưa ra. Vì sao mình lại nói như vậy thì các bạn hãy xem một số ưu điểm của nó dưới đây:

• Phân cấp dữ liệu, thuận tiện cho việc quản lý.
• Tìm kiếm dễ dàng hơn.
• Thao tác trên danh sách dữ liệu đã được sắp xếp.

Đối với cấu trúc dạng cây ta có hai cấu trúc chính đó là:

• Cấu trúc cây nhị phân (Binary Tree).
• Cấu trúc cây nhị phân tìm kiếm (Binary Search Tree).

Bây giờ chúng ta sẽ tìm hiểu từng loại cấu trúc một nhé, đầu tiên sẽ là cấu trúc cây nhị phân.

Cây nhị phân là gì? Cơ chế hoạt động của nó

Cây nhị phân là một cấu trúc dữ liệu được dùng với mục đích lưu trữ dữ liệu, cũng giống như các loại cấu trúc khác mà thôi. Tuy nhiên về cấu trúc của nó thì khác hoàn toán so với các cấu trúc lưu trữ dữ liệu khác.

Một cây nhị phân được cấu tạo thành từ các node và mỗi node bao gồm ba thành phần sau đây:

• Data: Giá trị của node.
• Left point: Con trỏ trỏ đến cây bên trái.
• Right point: Con trỏ trỏ đến cây bên phải.

Các thành phần của một cây nhị phân bao gồm:

• Root: Node gốc của cây, chỉ có một node Root duy nhất trong cây.
• Parent Node: Là node cha của một node nào đó.
• Child Node: Là node con của một node nào đó.
• Sub-Tree: Là cây con biểu diễn các node con của một node nào đó.
• LeafNode: Là node không có node con.
• Siblings: Là các node có cùng một node cha.
• Internal Node: Node có ít nhất một node con.
• External Node: Node không có node con nào.

Cây nhị phân tìm kiếm là gì? cơ chế hoạt động của nó

Cây nhị phân tìm kiếm là một dạng đặc biệt của cây nhị phân. Vì nó là dạng đặc biệt vậy nên về cơ bản thì nó có đầy đủ các tính chất và thành phần của một cây nhị phân. Tuy nhiên, các node của cây nhị phân tìm kiếm tuân theo một quy luật như sau:

1. Các node ở cây con bên trái luôn luôn có giá trị nhỏ hơn hoặc bằng node cha ngay phía trên nó.
2. Các node ở cây con bên phải luôn luôn có giá trị lớn hơn hoặc bằng node cha ngay phía trên nó.

Sau đây mình sẽ lấy một ví dụ để biểu diễn cho cơ chế hoạt động của cây nhị phân tìm kiếm. Trước tiên các bạn hãy xem hình dưới đây, sau đó mình sẽ giải thích ngay bên dưới nhé.

Cơ chế hoạt động:

Giả sử mình có một danh sách các số nguyên bao gồm {27, 14, 35, 10, 19, 31, 43}, bây giờ mình sẽ giải thích từng bước mà các số trên được lưu vào cây nhị phân tìm kiếm nhé.

Bước 1: Lưu số 27, đây là node đầu tiên của cây. Và nó chính là node Root, nó được sử dụng để so sánh với các node phía sau.

Bước 2: Lưu số 14, vì 14 nhỏ hơn 27 vậy nên nó sẽ được lưu vào cây con phía bên trái 27.

Bước 3: Lưu số 35, vì nó lớn hơn 27 nên nó sẽ được lưu vào cây con phía bên phải 27.

Bước 4: Lưu số 10, vì nó nhỏ hơn cả 27 và 14, nên sẽ được lưu trữ vào cây con bên trái 14.

Bước 5: Lưu số 19, vì nó nhỏ hơn 27 và lớn hơn 14 nên sẽ được lưu vào bên phải 14.

Bước 6: Lưu số 31, vì nó lớn hơn 27 và nhỏ hơn 35 nên sẽ được lưu vào bên trái 35.

Bước 7: Lưu số 42, vì nó lớn hơn cả 27 và 35 nên sẽ được lưu vào phên phải 35.

Nếu có thêm các phần tử khác thì cứ tiếp tục so sánh và lưu vào cấu trúc cây nhị phân. Rất đơn giản đúng không ạ, chỉ cần nắm được quy luật của nó thì việc thực hiện rất dễ dàng.

Các bạn hãy thử luyện tập bàng cách lấy một danh sách nào đó xong lưu trữ bằng tay nhé, việc này giúp các bạn hiểu rất nhanh.

Các thao tác với cây nhị phân tìm kiếm:

• Chèn node vào cây nhị phân tìm kiếm.
• Duyệt cây nhị phân tìm kiếm.
• Đo chiều cao của cây nhị phân tìm kiếm.
• Tìm phần tử trong cây nhị phân tìm kiếm.

Đối với cây nhị phân tìm kiếm chúng ta không cần phải sắp xếp, vì khi lưu trữ, nó đã được sắp xếp theo thứ tự rồi nhé.

Kết luận

Như vậy là chúng ta đã cùng nhau tìm hiểu về cây nhị phân là gì? Cơ chế hoạt đông của nó. Ở bài viết tiếp theo, mình sẽ hướng dẫn các bạn cách thêm node vào cây nhị phân tìm kiếm, hãy chú ý theo dõi nhé !!!