Tổng quan về giáo trình

Tài liệu bài giảng học phần Cấu trúc dữ liệu và Giải thuật (Data Structures and Algorithms) – cụ thể tại Chương 8: Cây AVL và Cây B (Chapter 8: AVL Trees, B-Trees) – được biên soạn bởi TS. Nguyễn Hứa Phùng (Dr. Nguyen Ho Man Rang) thuộc Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa – Đại học Quốc gia TP.HCM (Faculty of Computer Science and Engineering, University of Technology, VNU-HCM). Trong chương trình đào tạo kỹ sư và cử nhân ngành Khoa học Máy tính, Kỹ thuật Máy tính và Công nghệ Thông tin, học phần này giữ vị trí kiến thức cơ sở ngành bắt buộc, làm nền tảng cho các môn học nâng cao về thuật toán, cơ sở dữ liệu và hệ thống thông tin.

Mục tiêu học tập (Learning Outcomes) của tài liệu được xác định theo chuẩn đầu ra cụ thể:

  • L.1: Mô tả và phân biệt các khái niệm cấu trúc cây: cây nhị phân (binary tree), cây nhị phân hoàn chỉnh (complete binary tree), cây nhị phân cân bằng (balanced binary tree), cây AVL (AVL tree), cây đa phân (multi-way tree) và cây B (B-tree).
  • L.2: Trình bày cấu trúc lưu trữ của các dạng cây bằng mã giả (pseudocode).
  • L.3: Liệt kê và mô tả bằng mã giả các phương thức thao tác cần thiết trên cấu trúc cây.
  • L.4: Xác định tầm quan trọng của tính chất "cân bằng" trong cấu trúc cây và phân tích ví dụ minh họa.
  • L.5: Nhận diện các trường hợp cây AVL và cây B bị mất cân bằng; trình bày phương pháp tái cân bằng từng bước bằng sơ đồ.
  • L.6: Cài đặt cây nhị phân và cây AVL bằng ngôn ngữ lập trình C/C++.
  • L.7: Ứng dụng cây nhị phân và cây AVL để giải quyết các bài toán tìm kiếm trong thực tế.
  • L.8: Phân tích độ phức tạp thuật toán và xây dựng chương trình thực nghiệm đánh giá hiệu năng các phương thức thao tác trên cấu trúc cây.

Tài liệu tiếp cận kiến thức theo hướng quy nạp kết hợp diễn dịch: bắt đầu từ việc chỉ ra hạn chế của cây tìm kiếm nhị phân thông thường (suy biến thành $O(n)$ khi chèn dãy có thứ tự), đưa ra định nghĩa toán học của cây cân bằng AVL (Adel’son-Vel’skii và Landis), chuẩn hóa chỉ số cân bằng (Balance Factor), và xây dựng chi tiết mã giả cho các thao tác chèn (AVL Insert), xóa (AVL Delete) và tái cân bằng thông qua các phép quay (Rotate Left, Rotate Right). Điểm đặc sắc của bài giảng là hệ thống hóa toàn diện 4 trường hợp mất cân bằng đi kèm mã giả thuật toán điều phối cân bằng hoàn chỉnh, trích xuất từ tài liệu chuẩn mực Data Structures - A Pseudocode Approach with C++.

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Nội dung bài giảng được cấu trúc thành 5 chủ đề theo trình tự logic chặt chẽ:

  1. Khái niệm Cây AVL (AVL Tree Concepts): Thiết lập định nghĩa cây AVL do hai nhà toán học G.M. Adel’son-Vel’skii và E.M. Landis đề xuất năm 1962. Một cây nhị phân là cây AVL khi thỏa mãn đồng thời hai điều kiện:

    • Thuộc tính cây tìm kiếm nhị phân (BST Property): Khóa tại mỗi nút lớn hơn tất cả các khóa ở nhánh con trái và nhỏ hơn hoặc bằng các khóa ở nhánh con phải.
    • Thuộc tính cân bằng (Balanced Tree Property): Tại mỗi nút bất kỳ, độ chênh lệch chiều cao giữa cây con trái ($H_L$) và cây con phải ($H_R$) không vượt quá 1 ($|H_L - H_R| \le 1$).

  2. Cân bằng Cây AVL (AVL Balance): Quy định trạng thái cân bằng qua ba hệ số cân bằng (Balance factor):

    • left_higher ($LH$): $H_L = H_R + 1$ (cây con bên trái cao hơn cây con bên phải 1 đơn vị).
    • equal_height ($EH$): $H_L = H_R$ (hai cây con có chiều cao bằng nhau).
    • right_higher ($RH$): $H_R = H_L + 1$ (cây con bên phải cao hơn cây con bên trái 1 đơn vị). Phân loại và xử lý 4 trường hợp mất cân bằng khi thực hiện chèn hoặc xóa nút: Left of Left, Right of Right, Right of Left, và Left of Right.

  3. Thao tác trên Cây AVL (AVL Tree Operations): Xây dựng cấu trúc dữ liệu kiểu bản ghi (record/struct) bao gồm liên kết con trỏ (left, right), trường dữ liệu (data), và trường lưu trạng thái cân bằng (balance). Chi tiết hóa giải thuật đệ quy cho phép chèn (AVLInsert) và xóa (AVLDelete) có tích hợp cơ chế nhận biết sự biến thiên chiều cao (taller, shorter) để kích hoạt các hàm cân bằng nhánh trái (leftBalance, deleteLeftBalance) hoặc nhánh phải (rightBalance, deleteRightBalance).

  4. Cây đa phân (Multiway Trees): Mở rộng khái niệm từ cây nhị phân sang cây đa phân, trong đó mỗi nút có thể chứa nhiều hơn một khóa và nhiều hơn hai cây con trỏ nhánh.

  5. Cây B (B-Trees): Khảo sát cấu trúc dữ liệu cây tìm kiếm đa phân tự cân bằng phục vụ truy xuất dữ liệu trên bộ nhớ ngoài (bộ nhớ thứ cấp).

Kiến thức nền tảng được xây dựng

  • Lý thuyết nền tảng về Cây tìm kiếm nhị phân và Cây suy biến: Phân tích hiện tượng suy biến của BST. Khi các phần tử được chèn theo thứ tự tăng dần (ví dụ: $1, 2, 3, \dots$), BST suy biến thành danh sách liên kết tuyến tính (degenerate tree), làm độ phức tạp thao tác tìm kiếm tăng vọt lên $O(n)$. Cây AVL khắc phục triệt để nhược điểm này bằng cách duy trì độ cao cây luôn ở mức xấp xỉ $\log_2 n$, đảm bảo thời gian tìm kiếm đạt $O(\log_2 n)$.
  • Nguyên lý tái cân bằng thông qua phép quay (Tree Rotations):
    • Phép quay phải (rotateRight): Hoán đổi con trỏ giữa nút gốc hiện tại và nút con trái nhằm giảm chiều cao nhánh trái.
    • Phép quay trái (rotateLeft): Hoán đổi con trỏ giữa nút gốc hiện tại và nút con phải nhằm giảm chiều cao nhánh phải.
    • Phép quay kép: Kết hợp quay trái nhánh con rồi quay phải nút gốc (áp dụng cho trường hợp Right of Left), hoặc quay phải nhánh con rồi quay trái nút gốc (áp dụng cho trường hợp Left of Right).
  • Mô hình cấu trúc dữ liệu con trỏ: Giáo trình khẳng định rõ: "Array is not suitable for AVL Tree" (Cấu trúc mảng không phù hợp cho cây AVL). Cấu trúc cây AVL bắt buộc phải được tổ chức dưới dạng danh sách liên kết động sử dụng con trỏ:
node
    data <dataType>
    left <pointer>
    right <pointer>
    balance <balance_factor>
end node

avlTree
    root <pointer>
end avlTree

dataType
    key <keyType>
    field1 <...>
end dataType

Kỹ năng phát triển

  • Kỹ năng kỹ thuật (Technical skills): Cài đặt hoàn chỉnh cấu trúc cây AVL bằng ngôn ngữ C/C++; quản lý bộ nhớ động qua các thao tác cấp phát con trỏ, hoán đổi liên kết khi quay cây và thu hồi bộ nhớ (recycle(deleteNode)).
  • Kỹ năng phân tích thuật toán (Analytical skills): Sử dụng ký hiệu Big-O để đánh giá độ phức tạp thuật toán qua các cấu trúc điều khiển tuần tự (sequence), rẽ nhánh (branching) và lặp (iteration); phân tích vết đệ quy và trạng thái biến đổi của cây theo từng bước.
  • Kỹ năng ứng dụng thực tế (Practical competencies): Ứng dụng cấu trúc cây nhị phân cân bằng để tối ưu hóa hiệu suất tìm kiếm và quản lý tập dữ liệu có tần suất tra cứu lớn trong các hệ thống phần mềm.

Phương pháp giảng dạy và học tập

Tiếp cận sư phạm (Pedagogical Approach)

Tài liệu áp dụng phương pháp sư phạm cấu trúc hình thức và trực quan hóa:

  • Tiếp cận từng bước (Step-by-step): Định nghĩa thuộc tính hình học của cây $\rightarrow$ Thiết lập công thức toán học cho hệ số cân bằng $\rightarrow$ Phân tích các ca vi phạm $\rightarrow$ Trình bày thuật toán tái cân bằng bằng mã giả hoàn chỉnh.
  • Minh họa bằng hình vẽ và phản ví dụ (Examples & Non-AVL Trees): Bài giảng cung cấp song song các mô hình cây đạt chuẩn AVL và các cấu trúc cây không đạt chuẩn AVL (Non-AVL Trees) với các giá trị nút cụ thể (như các cây có gốc khóa 8, 5, 10, 3, 6, 9, 12, 15) nhằm rèn luyện khả năng nhận diện trực quan cho người học.
Ví dụ Cây AVL (Hệ số cân bằng hợp lệ):
          8 (EH)
        /        \
     5 (EH)      10 (RH)
    /      \            \
  3 (EH)   6 (EH)       12 (EH)

Ví dụ Cây Không Phải AVL (Vi phạm cân bằng):
          8 (LH)
        /        \
     5 (LH)      10 (RH)
    /                   \
  3 (LH)                12 (RH)
  /                            \
 1                              15  --> Độ chênh lệch chiều cao nhánh > 1

Bài tập, trường hợp nghiên cứu và đánh giá

  • Phân tích 4 trường hợp mất cân bằng (Case Studies):
    1. Left of Left: Nhánh trái của một cây đang lệch trái tiếp tục bị lệch trái $\rightarrow$ Xử lý bằng 1 phép quay phải tại nút mất cân bằng (rotateRight).
    2. Right of Right: Nhánh phải của một cây đang lệch phải tiếp tục bị lệch phải $\rightarrow$ Xử lý bằng 1 phép quay trái tại nút mất cân bằng (rotateLeft).
    3. Right of Left: Nhánh phải của một cây đang lệch trái bị tăng chiều cao $\rightarrow$ Xử lý bằng quay kép: quay trái cây con trái (rotateLeft), sau đó quay phải nút gốc (rotateRight).
    4. Left of Right: Nhánh trái của một cây đang lệch phải bị tăng chiều cao $\rightarrow$ Xử lý bằng quay kép: quay phải cây con phải (rotateRight), sau đó quay trái nút gốc (rotateLeft).
  • Hình thức đánh giá: Đo lường thông qua bài tập viết mã giả, bài tập theo dõi từng bước (trace) sự thay đổi cấu trúc cây khi chèn/xóa chuỗi khóa, và bài thực hành lập trình kiểm thử trên C/C++.
  • Hướng dẫn tự học: Người học cần tự vẽ cây qua từng thao tác chèn khóa ngẫu nhiên, xác định hệ số cân bằng ($LH, EH, RH$) tại từng nút cha sau mỗi bước đệ quy quay lui (backtracking), và kiểm chứng tính đúng đắn của giải thuật.

Điểm nổi bật và tính học thuật của tài liệu

Tiêu chí Nội dung thể hiện trong tài liệu
Nguồn trích dẫn học thuật chuẩn Thuật toán mã giả và mô hình cân bằng được trích dẫn trực tiếp từ giáo trình kinh điển: Data Structures - A Pseudocode Approach with C++ (Behrouz A. Forouzan & Richard F. Gilberg).
Tính đầy đủ của thuật toán Cung cấp toàn diện mã giả cho cả hai thao tác phức tạp: Chèn (AVLInsert, leftBalance, rightBalance) và Xóa (AVLDelete, deleteLeftBalance, deleteRightBalance).
Kỹ thuật xử lý đệ quy chính xác Sử dụng các biến cờ trạng thái kiểu Boolean (taller, shorter, success) truyền theo tham chiếu (ref) để kiểm soát sự thay đổi chiều cao của cây con khi quay lui đệ quy.
Giải quyết bài toán nút 2 con khi xóa Thuật toán AVLDelete mô tả giải pháp tìm phần tử cực phải của cây con trái (hoặc phần tử thay thế exchPtr) để hoán đổi dữ liệu trước khi xóa nút thực tế.

Tài liệu kết hợp giữa phân tích lý thuyết toán học (định nghĩa cây của Adel’son-Vel’skii & Landis) và tư duy lập trình thực tế, giúp người học chuyển hóa trực tiếp từ ý niệm trừu tượng sang mã lệnh thực thi trong ngôn ngữ C/C++.

Đối tượng sử dụng giáo trình

  1. Sinh viên đại học chuyên ngành:
    • Sinh viên năm thứ hai thuộc các ngành Khoa học Máy tính, Kỹ thuật Máy tính, Công nghệ Thông tin, Kỹ thuật Phần mềm và Hệ thống Thông tin.
    • Học viên chương trình văn bằng 2 hoặc chuyển tiếp cần bổ túc kiến thức cấu trúc dữ liệu và giải thuật.
  2. Yêu cầu tiên quyết (Prerequisites):
    • Đã hoàn thành học phần Nhập môn Lập trình và Kỹ thuật Lập trình (nắm vững con trỏ, cấp phát bộ nhớ động, struct/class, hàm đệ quy trong C/C++).
    • Đã học các cấu trúc dữ liệu tuyến tính cơ bản (danh sách liên kết - list, ngăn xếp - stack, hàng đợi - queue) và cây tìm kiếm nhị phân (BST) cơ bản.
    • Hiểu biết về ký pháp độ phức tạp thuật toán Big-O.
  3. Giảng viên và nhà nghiên cứu:
    • Sử dụng làm khung bài giảng chuẩn cho học phần Cấu trúc dữ liệu và Giải thuật.
    • Làm tài liệu quy chiếu cho việc biên soạn đề thi, bài tập lớn và bài thực hành trong phòng máy.
  4. Tự học và tra cứu:
    • Tài liệu tham khảo cho lập trình viên cần tra cứu thuật toán tự cân bằng cây và tối ưu hóa cấu trúc dữ liệu lưu trữ trong bộ nhớ.

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai?

Tài liệu phù hợp cho sinh viên bậc đại học ngành Khoa học và Kỹ thuật Máy tính đang học môn Cấu trúc dữ liệu và Giải thuật, cũng như các kỹ sư phần mềm cần chuẩn hóa kiến thức nền tảng về cấu trúc cây tìm kiếm tự cân bằng.

2. Cần kiến thức nền nào để tiếp thu tốt chương học này?

Người học cần nắm vững kỹ thuật lập trình C/C++ (đặc biệt là con trỏ và đệ quy), kiến thức về cây tìm kiếm nhị phân (BST), và phương pháp phân tích độ phức tạp thời gian bằng ký pháp Big-O.

3. Điểm khác biệt giữa cây AVL và cây tìm kiếm nhị phân (BST) thông thường là gì?

Cây BST thông thường có thể bị mất cân bằng và suy biến thành cấu trúc có chiều cao $O(n)$ khi dữ liệu đầu vào có thứ tự, khiến tốc độ tìm kiếm suy giảm về $O(n)$. Cây AVL luôn duy trì độ lệch chiều cao giữa hai cây con không quá 1, đảm bảo độ phức tạp cho các thao tác tìm kiếm, chèn và xóa luôn ở mức $O(\log_2 n)$.

4. Tại sao mảng (Array) không phù hợp để cài đặt Cây AVL?

Cây AVL liên tục thay đổi cấu trúc hình học thông qua các phép quay đơn và quay kép sau mỗi thao tác chèn hoặc xóa. Việc sử dụng mảng sẽ dẫn đến chi phí dịch chuyển phần tử cực kỳ tốn kém và khó quản lý các chỉ số nút cha - con khi cây xoay, do đó cấu trúc liên kết động dùng con trỏ (pointer) là giải pháp bắt buộc.

5. Có tài liệu bổ trợ nào được nêu kèm theo bài giảng?

Bài giảng trích dẫn trực tiếp cấu trúc và hình vẽ từ cuốn sách chuẩn học thuật Data Structures - A Pseudocode Approach with C++. Người học có thể tham khảo thêm cuốn sách này cùng các tài liệu về Cấu trúc dữ liệu và Giải thuật của Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM để đối chiếu chi tiết cài đặt.

Kết luận

Bài giảng Chương 8: AVL Trees, B-Trees của TS. Nguyễn Hứa Phùng cung cấp hệ thống kiến thức hoàn chỉnh và chuẩn mực về cấu trúc cây tìm kiếm nhị phân tự cân bằng. Tài liệu giải quyết triệt để bài toán hiệu năng của cây tìm kiếm thông qua các định nghĩa toán học rõ ràng, cơ chế hệ số cân bằng chi tiết và bộ mã giả thuật toán chính xác cho toàn bộ các thao tác quay cây, chèn và xóa.

Lộ trình học tập kiến nghị:

  1. Nắm vững định nghĩa cây AVL và cách tính hệ số cân bằng ($LH, EH, RH$).
  2. Thực hành phân loại và vẽ tay 4 trường hợp mất cân bằng (Left of Left, Right of Right, Right of Left, Left of Right).
  3. Đọc hiểu và lần vết (trace) mã giả của các hàm quay (rotateLeft, rotateRight) và cân bằng (leftBalance, rightBalance, deleteLeftBalance, deleteRightBalance).
  4. Cài đặt toàn bộ mã giả thành chương trình chạy được trên C/C++ và mở rộng nghiên cứu sang phần Cây đa phân (Multiway Trees) và Cây B (B-Trees).