Bỏ qua

Tóm tắt

Điểm lại trọng tâm

  • Cây nhị phân (binary tree) là một cấu trúc dữ liệu phi tuyến tính thể hiện logic chia để trị (divide-and-conquer) của việc chia làm hai. Mỗi nút cây nhị phân chứa một giá trị và hai con trỏ, lần lượt trỏ đến các nút con trái và nút con phải của nó.
  • Đối với một nút cụ thể trong cây nhị phân, cây được tạo bởi nút con trái (phải) của nó và tất cả các nút bên dưới được gọi là cây con trái (phải) (left (right) subtree) của nút đó.
  • Các thuật ngữ liên quan đến cây nhị phân bao gồm nút gốc (root node), nút lá (leaf node), mức (level), bậc (degree), cạnh (edge), chiều cao (height) và độ sâu (depth).
  • Các thao tác khởi tạo, chèn nút và xóa nút trên cây nhị phân tương tự như trên danh sách liên kết (linked list).
  • Các loại cây nhị phân phổ biến bao gồm cây nhị phân hoàn hảo (perfect binary tree), cây nhị phân hoàn chỉnh (complete binary tree), cây nhị phân đầy đủ (full binary tree) và cây nhị phân cân bằng (balanced binary tree). Cây nhị phân hoàn hảo là hình thái lý tưởng, trong khi danh sách liên kết đại diện cho trường hợp thoái hóa tồi tệ nhất.
  • Cây nhị phân có thể được biểu diễn bằng mảng bằng cách sắp xếp các giá trị nút và các ô trống theo thứ tự duyệt theo mức, đồng thời hiện thực hóa các liên kết con trỏ dựa trên mối quan hệ ánh xạ chỉ mục giữa nút cha và nút con.
  • Duyệt theo mức (level-order traversal) của cây nhị phân là một phương pháp tìm kiếm theo chiều rộng (breadth-first search) tiến hành theo từng mức một, thường được triển khai bằng hàng đợi (queue).
  • Các phép duyệt tiền thứ tự (preorder), trung thứ tự (inorder) và hậu thứ tự (postorder) đều thuộc về tìm kiếm theo chiều sâu (depth-first search - DFS), tiến hành bằng cách đi sâu nhất có thể trước khi quay lui (backtracking), thường sử dụng đệ quy.
  • Cây tìm kiếm nhị phân (binary search tree) là một cấu trúc dữ liệu hiệu quả để tìm kiếm phần tử, với các thao tác tìm kiếm, chèn và xóa đều có độ phức tạp thời gian là \(O(\log n)\). Khi cây tìm kiếm nhị phân thoái hóa thành danh sách liên kết, tất cả các độ phức tạp thời gian sẽ giảm xuống còn \(O(n)\).
  • Cây AVL (AVL tree), còn được gọi là cây tìm kiếm nhị phân cân bằng (balanced binary search tree), đảm bảo cây vẫn giữ được sự cân bằng sau các thao tác chèn và xóa nút liên tục thông qua các thao tác xoay (rotation operations).
  • Các thao tác xoay trong cây AVL bao gồm xoay phải (right rotation), xoay trái (left rotation), xoay phải rồi xoay trái (right-left rotation) và xoay trái rồi xoay phải (left-right rotation). Sau khi chèn hoặc xóa nút, cây AVL thực hiện các thao tác xoay từ dưới lên trên để khôi phục sự cân bằng.

Q & A

Q: Đối với cây nhị phân chỉ có một nút, chiều cao của cây và độ sâu của nút gốc đều bằng \(0\) phải không?

Đúng vậy, bởi vì chiều cao và độ sâu thường được định nghĩa là số lượng cạnh trên đường đi.

Q: Việc chèn và xóa trên cây nhị phân thường được hoàn thành bằng một loạt các thao tác. "Một loạt các thao tác" ở đây đề cập đến điều gì? Nó có ngụ ý giải phóng tài nguyên của các nút con không?

Lấy cây tìm kiếm nhị phân làm ví dụ, thao tác xóa một nút cần được xử lý trong ba trường hợp khác nhau, mỗi trường hợp yêu cầu nhiều bước thao tác trên nút.

Q: Tại sao duyệt DFS cây nhị phân có ba thứ tự: tiền thứ tự, trung thứ tự và hậu thứ tự, và công dụng của chúng là gì?

Tương tự như việc duyệt xuôi và duyệt ngược mảng, duyệt tiền thứ tự, trung thứ tự và hậu thứ tự là ba phương pháp duyệt cây nhị phân cho phép chúng ta thu được kết quả duyệt theo một thứ tự cụ thể. Ví dụ, trong cây tìm kiếm nhị phân, vì các nút thỏa mãn quan hệ giá trị nút con trái < giá trị nút gốc < giá trị nút con phải, chúng ta chỉ cần duyệt cây với độ ưu tiên "trái \(\rightarrow\) gốc \(\rightarrow\) phải" là có thể thu được một chuỗi nút có thứ tự.

Q: Trong thao tác xoay phải xử lý mối quan hệ giữa các nút mất cân bằng node, child và grand_child, chẳng phải liên kết giữa node và nút cha của nó sẽ bị mất sau khi xoay phải sao?

Chúng ta cần xem xét vấn đề này dưới góc nhìn đệ quy. Thao tác xoay phải right_rotate(root) nhận vào nút gốc của cây con và cuối cùng trả về nút gốc của cây con sau khi xoay bằng câu lệnh return child. Liên kết giữa nút gốc của cây con và nút cha của nó được thiết lập sau khi hàm trả về, điều này không nằm trong phạm vi xử lý của bản thân thao tác xoay phải.

Q: Trong C++, các hàm được chia thành các phần private và public. Có những cân nhắc gì cho việc này? Tại sao hàm height() và hàm updateHeight() lần lượt được đặt trong public và private?

Điều này chủ yếu phụ thuộc vào phạm vi sử dụng của phương thức. Nếu một phương thức chỉ được sử dụng bên trong lớp, nó sẽ được thiết kế là private. Ví dụ, việc người dùng gọi riêng lẻ hàm updateHeight() là vô nghĩa, vì nó chỉ là một bước trong các thao tác chèn hoặc xóa. Ngược lại, height() được sử dụng để truy cập chiều cao của nút, tương tự như vector.size(), nên nó được đặt ở chế độ public để thuận tiện cho việc sử dụng.

Q: Làm thế nào để xây dựng một cây tìm kiếm nhị phân từ một tập dữ liệu đầu vào? Việc lựa chọn nút gốc có quan trọng không?

Có, phương pháp xây dựng cây được cung cấp trong phương thức build_tree() ở phần mã nguồn của cây tìm kiếm nhị phân. Về việc lựa chọn nút gốc, thông thường chúng ta sẽ sắp xếp dữ liệu đầu vào, sau đó chọn phần tử ở giữa làm nút gốc, rồi xây dựng đệ quy các cây con trái và phải. Cách tiếp cận này giúp tối đa hóa sự cân bằng của cây.

Q: Trong Java, có phải lúc nào cũng phải sử dụng phương thức equals() để so sánh chuỗi không?

Trong Java, đối với các kiểu dữ liệu nguyên thủy (primitive data types), == được sử dụng để so sánh xem giá trị của hai biến có bằng nhau hay không. Đối với các kiểu tham chiếu (reference types), nguyên lý hoạt động của hai ký hiệu này là khác nhau.

  • ==: Được sử dụng để so sánh xem hai biến có cùng trỏ tới một đối tượng hay không, tức là vị trí của chúng trong bộ nhớ có giống nhau hay không.
  • equals(): Được sử dụng để so sánh xem giá trị của hai đối tượng có bằng nhau hay không.

Do đó, nếu muốn so sánh giá trị, chúng ta nên sử dụng equals(). Tuy nhiên, các chuỗi được khởi tạo qua String a = "hi"; String b = "hi"; được lưu trữ trong vùng lưu trữ hằng số chuỗi (string constant pool) và cùng trỏ tới một đối tượng, vì vậy a == b cũng có thể được dùng để so sánh nội dung của hai chuỗi.

Q: Trước khi chạm tới mức đáy, số lượng nút trong hàng đợi có phải là \(2^h\) trong quá trình duyệt theo chiều rộng không?

Đúng vậy, ví dụ một cây nhị phân đầy đủ có chiều cao \(h = 2\) có tổng cộng \(n = 7\) nút, khi đó mức đáy sẽ có \(4 = 2^h = (n + 1) / 2\) nút.