Cây nhị phân và tìm kiếm cây nhị phân

Cây nhị phân và tìm kiếm cây nhị phân

Cây nhị phân là gì?

Cây nhị phân là một cấu trúc dữ liệu phân cấp trong đó mỗi nút có nhiều nhất hai nút con thường được gọi là nút con trái và nút con phải.

Mỗi nút chứa ba thành phần:

  1. Con trỏ sang cây con bên trái
  2. Con trỏ sang cây con bên phải
  3. Phần tử dữ liệu

Nút trên cùng của cây được gọi là gốc. Một cây trống được biểu diễn bằng con trỏ NULL .

Một đại diện của cây nhị phân được hiển thị:

Cây nhị phân và tìm kiếm cây nhị phân

Cây nhị phân: 

Các thuật ngữ chung

  • Gốc: Nút trên cùng của cây.
  • Cha: Mọi nút (không bao gồm gốc) trong cây được kết nối bằng một cạnh có hướng từ chính xác một nút khác. Nút này được gọi là nút cha.
  • Con: Một nút kết nối trực tiếp với một nút khác khi di chuyển ra khỏi gốc.
  • Nút lá / nút ngoài: Nút không có nút con.
  • Nút bên trong: Nút có ít nhất một nút con.
  • Độ sâu của một nút: Số cạnh từ gốc đến nút.
  • Chiều cao của một nút: Số cạnh từ nút đến lá sâu nhất. Chiều cao của cây là chiều cao của gốc.
Cây nhị phân và tìm kiếm cây nhị phân

Trong cây nhị phân trên chúng ta thấy rằng nút gốc là Một . Cây có 10 nút với 5 nút nội bộ, tức là A, B, C, E, G và 5 nút bên ngoài, ví dụ, D, F, H, I, J . Chiều cao của cây là 3. B là công ty mẹ của D và E khi D và E là con của B .

Ưu điểm của cây:

Cây rất hữu ích và được sử dụng thường xuyên, bởi vì chúng có một số ưu điểm rất nghiêm trọng:

  • Cây phản ánh mối quan hệ cấu trúc trong dữ liệu.
  • Cây được sử dụng để đại diện cho các thứ bậc.
  • Cây cung cấp một hiệu quả cho chèn và tìm kiếm.
  • Cây là dữ liệu rất linh hoạt, cho phép di chuyển các cây con xung quanh với nỗ lực tối thiểu.

Các loại cây nhị phân (Dựa trên cấu trúc)

Cây nhị phân có gốc: Nó có một nút gốc và mỗi nút có ít nhất hai nút con.

Cây nhị phân đầy đủ: Là cây trong đó mỗi nút trong cây có 0 hoặc 2 nút con.

  • Số nút, n , trong một cây nhị phân đầy đủ ít nhất là n = 2h – 1, và tối đa là n = 2 h + 1 – 1 , trong đó h là chiều cao của cây.
  • Số nút lá l , trong cây nhị phân đầy đủ là số, L của các nút bên trong + 1, tức là, l = L + 1 .
Cây nhị phân và tìm kiếm cây nhị phân

Cây nhị phân hoàn hảo: Là cây nhị phân trong đó tất cả các nút bên trong có hai nút con và tất cả các lá có cùng độ sâu hoặc cùng mức.

  • Một cây nhị phân hoàn hảo với l lá có n = 2l-1 nút.
  • Trong cây nhị phân hoàn hảo, l = 2h và n = 2h + 1 – 1 trong đó, n là số nút, h là chiều cao của cây và l là số nút lá
Cây nhị phân và tìm kiếm cây nhị phân

Cây nhị phân hoàn chỉnh: Là cây nhị phân trong đó mọi cấp, ngoại trừ cấp cuối cùng, được lấp đầy hoàn toàn và tất cả các nút ở bên trái càng xa càng tốt.

Cây nhị phân và tìm kiếm cây nhị phân

Số nút bên trong trong một cây nhị phân hoàn chỉnh gồm n nút là tầng (n / 2) .

Cây nhị phân cân bằng: Cây nhị phân có chiều cao cân bằng nếu nó thỏa mãn các ràng buộc sau:

  • Chiều cao của cây con bên trái và bên phải chỉ khác nhau nhiều nhất là một, VÀ
  • Cây con bên trái là cân bằng, VÀ
  • Cây con bên phải được cân bằng
  • Một cây trống có chiều cao cân đối.
  • Chiều cao của cây nhị phân cân bằng là O ( Log n ) với n là số nút.
Cây nhị phân và tìm kiếm cây nhị phân

Degenarate tree: Là cây mà mỗi nút cha chỉ có một nút con. Nó hoạt động giống như một danh sách được liên kết.

Cây nhị phân và tìm kiếm cây nhị phân

Cây tìm kiếm nhị phân

  1. Cây tìm kiếm nhị phân là một cấu trúc dữ liệu hữu ích để bổ sung và xóa dữ liệu nhanh chóng.
  2. Nó bao gồm các nút, nơi lưu trữ dữ liệu và cũng liên kết với tối đa hai nút con khác. Đó là mối quan hệ giữa các lá được liên kết với và lá liên kết, còn được gọi là nút cha, làm cho cây nhị phân trở thành một cấu trúc dữ liệu hiệu quả.
  3. Đối với cây nhị phân là cây tìm kiếm nhị phân, dữ liệu của tất cả các nút trong cây con bên trái của nút gốc phải nhỏ hơn dữ liệu của nút gốc. Dữ liệu của tất cả các nút trong cây con bên phải của nút gốc phải lớn hơn dữ liệu của nút gốc. Kết quả là các lá ở xa nhất bên trái của cây có giá trị thấp nhất, trong khi các lá ở bên phải của cây có giá trị lớn nhất.
  4. Biểu diễn cây tìm kiếm nhị phân trông giống như sau:
Cây nhị phân và tìm kiếm cây nhị phân

Xét nút gốc 20. Tất cả các phần tử ở bên trái của cây con (10, 5) nhỏ hơn 20 và tất cả các phần tử ở bên phải của cây con (25, 30, 35) đều lớn hơn 20.

Thực hiện BST

Đầu tiên, xác định một cấu trúc là tree_node. Nó sẽ lưu trữ dữ liệu và con trỏ tới cây con trái và phải.

Cây nhị phân và tìm kiếm cây nhị phân

Bản thân nút rất giống với nút trong danh sách liên kết. Kiến thức cơ bản về mã cho danh sách liên kết sẽ rất hữu ích trong việc hiểu các kỹ thuật của cây nhị phân.

Hợp lý nhất là tạo một lớp cây tìm kiếm nhị phân để đóng gói các hoạt động của cây vào một khu vực duy nhất và cũng làm cho nó có thể tái sử dụng. Lớp sẽ chứa các hàm để chèn dữ liệu vào cây, tìm kiếm xem dữ liệu có tồn tại hay không và các phương thức để duyệt qua cây.

Cây nhị phân và tìm kiếm cây nhị phân

Cần khởi tạo root thành NULL để các hàm sau này có thể nhận biết nó không tồn tại.

Tất cả các thành viên công khai của lớp được thiết kế để cho phép người dùng của lớp sử dụng lớp mà không cần xử lý thiết kế bên dưới. Các hàm sẽ được gọi đệ quy là những hàm riêng tư, cho phép chúng di chuyển xuống dưới dạng cây.

Chèn trong một BST

Để chèn dữ liệu vào cây nhị phân bao gồm một hàm tìm kiếm một nút không sử dụng ở vị trí thích hợp trong cây để chèn giá trị khóa. Hàm chèn nói chung là một hàm đệ quy tiếp tục di chuyển xuống các cấp của cây nhị phân cho đến khi có một lá chưa sử dụng ở một vị trí tuân theo các quy tắc đặt các nút sau đây.

  • So sánh dữ liệu của nút gốc và phần tử sẽ được chèn.
  • Nếu dữ liệu của nút gốc lớn hơn và nếu tồn tại cây con bên trái, thì lặp lại bước 1 với root = gốc của cây con bên trái . Khác,
  • Chèn phần tử làm con bên trái của gốc hiện tại.
  • Nếu dữ liệu của nút gốc lớn hơn và nếu tồn tại cây con bên phải, thì hãy lặp lại bước 1 với root = gốc của cây con bên phải .
  • Ngược lại, chèn phần tử vào bên phải của phần tử gốc hiện tại.
Cây nhị phân và tìm kiếm cây nhị phân
Cây nhị phân và tìm kiếm cây nhị phân

Vì nút gốc là một thành viên riêng tư, chúng tôi cũng viết một hàm thành viên công khai có sẵn cho những người không phải là thành viên của lớp. Nó gọi hàm đệ quy riêng để chèn một phần tử và cũng xử lý trường hợp khi nút gốc là NULL.

Cây nhị phân và tìm kiếm cây nhị phân

Tìm kiếm trong BST

Chức năng tìm kiếm hoạt động theo cách tương tự như chèn. Nó sẽ kiểm tra xem giá trị khóa của nút hiện tại có phải là giá trị cần tìm hay không. Nếu không, cần kiểm tra xem giá trị cần tìm có nhỏ hơn giá trị của nút hay không, trong trường hợp đó nó sẽ được gọi đệ quy trên nút con bên trái hoặc nếu nó lớn hơn giá trị của nút, nó phải được gọi đệ quy trên nút con bên phải.

  • So sánh dữ liệu của nút gốc và giá trị cần tìm.
  • Nếu dữ liệu của nút gốc lớn hơn và nếu tồn tại cây con bên trái, thì lặp lại bước 1 với root = gốc của cây con bên trái . Khác,
  • Nếu dữ liệu của nút gốc lớn hơn và nếu tồn tại cây con bên phải, thì hãy lặp lại bước 1 với root = gốc của cây con bên phải . Khác,
  • Nếu giá trị được tìm kiếm bằng với dữ liệu của nút gốc, trả về true.
  • Khác, trả về false.
Cây nhị phân và tìm kiếm cây nhị phân

Vì nút gốc là một thành viên riêng tư, chúng tôi cũng viết một hàm thành viên công khai có sẵn cho những người không phải là thành viên của lớp. Nó gọi hàm đệ quy riêng để tìm kiếm một phần tử và cũng xử lý trường hợp khi nút gốc là NULL.

Cây nhị phân và tìm kiếm cây nhị phân

Duyệt qua một BST

Chủ yếu có ba kiểu truyền cây:

Duyệt tiền thứ tự Pre-order (NLR):

Trong kỹ thuật này, chúng tôi làm như sau:

  • Xử lý dữ liệu của nút gốc.
  • Đầu tiên, đi qua cây con bên trái hoàn toàn.
  • Sau đó, đi qua cây con bên phải.
Cây nhị phân và tìm kiếm cây nhị phân

Duyệt hậu thứ tự – Post-order Traversal (NLR):

Trong kỹ thuật truyền tải này, chúng tôi thực hiện như sau:

  • Cây con đầu tiên đi ngang bên trái hoàn toàn.
  • Sau đó, đi qua cây con bên phải hoàn toàn.
  • Sau đó, xử lý dữ liệu của nút.
Cây nhị phân và tìm kiếm cây nhị phân

Duyệt trung thứ tự – In-order Traversal (LNR)

Để duyệt theo thứ tự, chúng tôi thực hiện như sau:

  • Cây con bên trái quy trình đầu tiên.
  • Sau đó, xử lý nút gốc hiện tại.
  • Sau đó, xử lý cây con bên phải.
Cây nhị phân và tìm kiếm cây nhị phân

Việc duyệt theo thứ tự của cây tìm kiếm nhị phân cung cấp thứ tự được sắp xếp của các phần tử dữ liệu có trong cây tìm kiếm nhị phân. Đây là một thuộc tính quan trọng của cây tìm kiếm nhị phân.

Vì nút gốc là một thành viên riêng, chúng tôi cũng viết các hàm thành viên công cộng có sẵn cho những người không phải là thành viên của lớp. Nó gọi hàm đệ quy riêng để duyệt qua cây và cũng xử lý trường hợp khi nút gốc là NULL.

Cây nhị phân và tìm kiếm cây nhị phân

Phân tích độ phức tạp

Cây nhị phân và tìm kiếm cây nhị phân

Độ phức tạp về thời gian của việc tìm kiếm và chèn phụ thuộc vào chiều cao của cây. Trung bình, cây tìm kiếm nhị phân có n nút có chiều cao là O (log n) . Tuy nhiên trong trường hợp xấu nhất, cây có thể có chiều cao là O (n) khi cây không cân bằng giống như một danh sách liên kết. Ví dụ trong trường hợp này:

Cây nhị phân và tìm kiếm cây nhị phân

Truyền tải yêu cầu O (n) thời gian, vì mọi nút đều phải được truy cập.

Quý khách có thể tham khảo hơn ở các dịch vụ do websitehcm.com cung cấp như: dịch vụ seo, dịch vụ viết content , dịch vụ chăm sóc website, dịch vụ thiết kế website 

Leave a Reply