Binary Tree trong Java là gì? Cơ bản về Binary Tree trong Java

4119
Binary Tree trong Java là gì

Các lập trình viên Java có lẽ đã từng nghe qua về Binary Tree, hay cây tìm kiếm nhị phân. Vậy Binary Tree trong Java là gì, cấu trúc của Binary Tree và các hoạt động cơ bản trên nó là gì…

Chúng ta hãy cùng tìm hiểu qua bài viết này nhé!

  Gitignore là gì ? Tại sao nó lại rất quan trọng trong teamwork
  Cryptography - Nó là gì và hoạt động như thế nào?

Binary Tree trong Java là gì? 

Binary Tree là một cấu trúc lưu trữ dữ liệu phân cấp (kiểu cây) thường được sử dụng trong các bài toán tìm kiếm hay các xử lý liên quan đến phân cấp dữ liệu.

Binary Tree trong Java là gì

Một cây nhị phân là một tập hợp bao gồm các nút được sắp xếp theo cách để chúng có thể duy trì hoặc tuân theo các đặc điểm 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ị liên kết với nó. Trong khi tìm kiếm, khóa cần tìm được so sánh với các khóa trong cây tìm kiếm nhị phân (BST) và khi tìm thấy, giá trị liên kết sẽ được thu nhận.

Trong một cây nhị phân thường có

  • Nút trên đỉnh được gọi là nút gốc ( root ) của cây.
  • Những phần từ nằm bên dưới một phần tử khác gọi là các nút con (children nodes).
  • Ngược lại những phần tử nằm trên các phần tử khác gọi là các nút cha (parent nodes).
  • Cuối cùng, đối với những phần tử mà không có nút con thì ta gọi chúng là các nút lá (leaves nodes).

Dưới đây là một ví dụ về một cây nhị phân với “j” là root của cây nhị phân, “f” là nút cha của “a”, ngược lại “a” là nút con của “f” và “a”, “h”, “z” là các nút lá.

Binary Tree trong Java là gì

Một cây nhị phân có cách sắp xếp như sau

  • Mỗi nút sẽ chỉ tồn tại tối đa 2 nút con.
  • Nút con bên trái của một nút sẽ có khóa (key) nhỏ hơn hoặc bằng giá trị khóa của nút cha (của cây con này).
  • Nút 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).

Vì cách phân chia như vậy, nên trong một cây nhị phân sẽ luôn có một hệ thống nhánh với các nút bên phải luôn có giá trị khóa k lớn hơn nút cha của chúng, và các nút bên trái có giá trị khóa k bé hơn giá trị khóa k của cha chúng.

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

Tính chất của cấu trúc tree

  • Cấu túc cây thường được sử dụng trong các cấu trúc dữ liệu tồn tại một cách phân cấp chẳng hạn như các file trong hệ thống máy tính.
  • Cung cấp các truy cập hay tìm kiếm một cách trung bình (nhanh hơn mảng và chậm hơn linked list) tương tự với thêm và xóa.
  • Không giống như mảng hay linked List, cấu trúc cây không có giới hạn về số lượng các nút vì các nút được liên kết với nhau thông qua con trỏ.

Một số hoạt động cơ bản trên cây tìm kiếm nhị phân

Chèn phần tử vào cây nhị phân

Một giá trị mới sẽ luôn được chèn vào vị trí lá của cây nhị phân. Chúng ta sẽ bắt đầu tìm trên cây nhị phân cho đến khi gặp nút lá.

Một khi nút lá được tìm thấy chúng ta sẽ thêm giá trị mới vào với vai trò là một nút con của nút lá.

Đầu tiên chúng ta sẽ tạo một lớp đặt tên là Node.Giống như tên gọi nó sẽ bao gồm các thuộc tính là giá trị của nút đó (khóa K) và các nút left, right.

Cũng trong đó chúng ta sẽ khởi tạo hàm dựng với mục đích thêm giá trị cho nút(mặc định ban đầu nút đó sẽ không có nút con).

Sau đó chúng ta tạo một class mới đặt tên là BinarySearchTree.Tiếp theo chúng ta sẽ khởi tạo Node root và gán giá trị null cho nó.

Tiếp theo đây sẽ là hàm insert giá trị.

Nếu giá trị root bằng null nghĩa là cây chưa có giá trị cho root hoặc vị trí đó là các nút con của các nút lá (mặc định bằng null), khi thêm giá trị mới vào chúng ta sẽ gán giá trị đó vào giá trị khóa k của node đồng nghĩa với việc thêm nút mới.

Ngược lại khi root đã tồn tại, ta sẽ bắt đầu duyệt từ root xuống các nút liên tục so sánh. Nếu giá trị mới bé hơn giá trị nút đang xét thì ta bắt đầu so sánh tiếp với giá trị nút con nằm bên trái của nút đó và ngược lại.

Việc tìm kiếm dọc cây nhị phân này sẽ được thực hiện bằng hàm đệ qui.

Cuối cùng chúng ta sẽ return root trả về cây nhị phân đã được thêm giá trị mới.

Duyệt cây nhị phân

Để có thể hiển thị cây nhị phân theo thứ tự chúng ta phải thực hiện duyệt câu nhị phân.

Việc duyệt cây nhị phân sẽ bắt đầu từ node gốc và in lần lượt các giá trị của nhánh bên trái và bên phải lặp lại với nhánh bên trái và bên phải liên tục cho đến khi không còn giá trị nào tương ứng với node lá.

Giống như chèn phần tử vào cây nhị phân, việc này cũng làm với một hàm đệ qui.

Tìm kiếm vị trí trên cây nhị phân

Để tìm kiếm trên cây nhị phân, đầu tiên chúng ta sẽ so sánh giá trị với root, nếu bằng thì giá trị này đại diện cho node gốc, còn không thì chúng ta tiếp tục so sánh. Nếu giá trị lớn hơn giá trị của root chúng ta chuyển sang nhánh phải và ngược lại chúng ta chuyển sang nhánh trái.

Việc này tương đồng với duyệt cây nhị phân.

Xóa trên cây nhị phân

Có 3 trường hợp xảy ra khi xóa một phần từ trên cây nhị phân.

  • Khi phần tử là node lá: Khi đó chúng ta chỉ đơn giản xóa phần từ khỏi cây.
  • Nếu phần tử là node với duy nhất 1 node con: Khi đó chúng ta copy node con đến node đó và xóa node con.
  • Trong trường hợp phần tử là node có cả 2 node con: Khi đó chúng ta có thể tìm kiếm phần tử nhỏ nhất nằm ở bên phải của node hoặc phần tử lớn nhất nằm ở bên trái của node, thay thế phần tử tìm được với phần tử cần xóa và sau đó xóa phần tử đã tìm được đi.

Dưới đây sẽ là phần code mô tả toàn bộ 3 phương thức vừa trình bày.

Kết quả thu được như sau :

Kết luận

Hy vọng qua bài viết này, các bạn lập trình Java sẽ hiểu được Binary Tree trong Java là gì, ý nghĩa của Binary Tree, các thành phần cơ bản cũng như một số hoạt động chính của Binary Tree.

Đừng bỏ lỡ những bài viết hay về:

Xem thêm việc làm Java Developers mới nhất tại TopDev

TopDev via viblo

  JSON Web Token (JWT) là gì ?
  WebAssembly là gì? - Sử dụng WebAssembly chỉ với 14 dòng code
SHARE