Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Posted on by adminChuyên mục:Kiến thức Internet
Trong bài này mình sẽ ra mắt những bạn một trong những cấu trúc tài liệu tiếp theo đó chính là cấu trúc tài liệu dạng cây. Đây là một dạng cấu trúc được sử dụng rất nhiều trong tìm kiếm, nó được tối ưu nhất trong những cấu trúc tài liệu mà mình đã trình làng .

test php

banquyen png

Bài viết này được đăng tại

freetuts.net

, không được copy dưới mọi hình thức.

Chúng ta sẽ cùng nhau khám phá về cấu trúc tài liệu cây là gì ? Có những loại cấu trúc tài liệu cây nào và phương pháp hoạt động giải trí của nó .

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

Cấu trúc tài liệu cây là một cấu trúc màn biểu diễn những Node dưới dạng cây. Như những bạn đã học ở môn lập trình C / C + + thì khi tất cả chúng ta muốn lưu những thành phần, ta hoàn toàn có thể lưu chúng dưới dạng mảng một chiều. Hoặc hoàn toàn có thể lưu dưới dạng một list link. Tương tự như vậy những bạn cũng hoàn toàn có thể lưu dưới dạng cây nhị phân .
Ưu điểm của cấy trúc dữ liệu cây so với những cấu trúc khác là :Bài viết này được đăng tại [ không tính tiền tuts. net ]

  • Phân cấp dữ liệu.
  • Tìm kiếm dễ dàng hơn.
  • Thao tác trên các danh sách dữ liệu đã sắp xếp.

Trong cấu trúc tài liệu cây, có hai cấu trúc chính đó là cấu trúc cây nhị phân và cấu trúc cây nhị phân tìm kiếm. Sau đây tất cả chúng ta sẽ khám phá qua về hai cấu trúc tài liệu này nhé .

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

Cây nhị phân là một cấu trúc dữ liệu được sử dụng cho mục đích lưu trữ dữ liệu. Một cây nhị phân bao gồm các Node và mỗi Node bao gồm 3 thành phần:

  • Data: Giá trị của một phần tử
  • Left pointer: Con trỏ trỏ đến cây nhị phân bên trái Node.
  • Right pointer: Con trỏ trỏ đến cây nhị phân bên phải Node.

binary tree jpg

Các thành phần cơ bản của cây nhị phân gồm có :

  • Root: Được gọi là Node gốc của cây (là một Node cha), một cây chỉ có một Node gốc duy nhất và nó không có Node cha nào.
  • Parent Node: Là Node cha của một Node cụ thể nào đó.
  • Child Node: Là Node con của một Node cụ thể nào đó.
  • Sub-tree: Là cây con biểu diển các con của một Node.
  • LeafNode: Là Node không có Node con.
  • Siblings: Các Node có cùng một cha.
  • Internal Node: Node có ít nhất một Node con.
  • External Node: Node không có Node con nào.

3. Cây nhị phân tìm kiếm (Binary search tree)

Cây nhị phân tìm kiếm là một dạng đặc biệt quan trọng của cây nhị phân. Về cơ bản nó có đủ tổng thể những thành phần của cây nhị phân. Nhưng toàn bộ những Node của nó đều có chung một đặc thù sau :

  • Cây con bên trái của một Node luôn luôn có giá trị nhỏ hơn hoặc bằng giá trị của Node cha phía trên nó.
  • Cây con bên phải của một Node luôn luôn có giá trị lớn hơn hoặc bằng giá trị của Node cha phía trên nó.

Biểu diễn cây nhị phân tìm kiếm

Cây nhị phân tìm kiếm là một tập hợp những Node được sắp xếp và tàng trữ theo một quy tắc nhất định. Dựa vào quy tắc đó tất cả chúng ta hoàn toàn có thể duy trì và thực thi những thao tác trên cây nhị phân tìm kiếm. Các bạn hãy xem hình dưới đây để hiểu rõ hơn về quy tắc của nó :

binary search tree jpg

Giả sử ta có những phần tử số nguyên như sau : 27, 14, 35, 10, 19, 31, 32. Quá trình tàng trữ những thành phần này theo cấu trúc cây nhị phân tìm kiếm được thực thi như sau :

  1. Số 27 sẽ được lưu trữ vào cây đầu tiên và nó được lấy làm key để so sánh.
  2. Số 14 được so sánh với số 27 (key), vì 14 < 27 nên sẽ được lưu trữ vào bên trái số 27 (key).
  3. Số 35 > 27 vì vậy sẽ được lưu trữ vào bên phải số 27.
  4. Tiếp tục số 10 < 27 và 10 < 14 vì vậy nó sẽ nằm bên trái số 14.
  5. Số 19 < 27 và 19 > 14 vì vậy nó sẽ nằm bên phải số 14.
  6. Số 31 > 27 và 31 < 35 vì vậy nó sẽ nằm bên trái số 35.
  7. Cuối cùng số 42 > 27 và 42 > 35 vị vậy nó sẽ nằm bên phải số 35.

Sau khi thực hiện lưu trữ các phần tử số nguyên trên vào cây ta được một cây như trong hình.

Các thao tác trên cây nhị phân tìm kiếm

Trong cây nhị phân tìm kiếm ta hoàn toàn có thể thực thi những thao tác sau :

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

Trên đây là những thao tác thường được sử dụng nhiều trong cây. Đặc biệt là tìm kiếm thành phần trong cây, như cái tên của nó là cây nhị phân tìm kiếm. Đây là một cấu trúc tài liệu được sử dụng trong những bài toán tìm kiếm rất nhiều, bởi tính đúng chuẩn và vận tốc của nó .

4. Kết luận

Như vậy là tất cả chúng ta đã khám phá xong về cấu trúc tài liệu cây là gì. Và những hai cấu trúc tài liệu cây nhị phân và nhị phân tìm kiếm. Các bạn hãy sử dụng những cấu trúc tài liệu thật linh động nhé, bởi mỗi cấu trúc tài liệu đều có những ưu điểm nhất định. Ở bài tiếp theo mình sẽ hướng dẫn những cấu trúc tài liệu của cây và cách thêm Node vào cây, hãy quan tâm theo dõi nhé ! ! !

admin