Data structure and algorithms [CO2003]: Chapter 7 - Cây AVL (AVL Tree)

Trong lĩnh vực cấu trúc dữ liệu và thuật toán, việc tối ưu hóa thời gian tìm kiếm là một mục tiêu cốt lõi. 82 trang.

• Trường học: Trường Đại Học
• Chuyên ngành: Cấu Trúc Dữ Liệu Và Thuật Toán
• Đề tài: Cấu Trúc Dữ Liệu Và Thuật Toán Chapter 7 AVL Tree
• Loại tài liệu: Tài Liệu

Mục lục chi tiết

• CHUẨN ĐẦU RA
• 7. CHƯƠNG 7: CÂY AVL
• 7.1. Khái niệm cây AVL
• 7.1.1. Định nghĩa cây AVL
• 7.1.2. Hệ số cân bằng
• 7.1.3. Lý do sử dụng cây AVL
• 7.1.4. Cân bằng cây AVL
• 7.1.4.1. Các trường hợp cây mất cân bằng
• 7.1.4.2. Phép quay phải
• 7.1.4.3. Phép quay trái
• 7.1.4.4. Trường hợp 1: Trái của Trái (Left of Left)
• 7.1.4.5. Trường hợp 2: Phải của Phải (Right of Right)
• 7.1.4.6. Trường hợp 3: Phải của Trái (Right of Left)
• 7.1.4.7. Trường hợp 4: Trái của Phải (Left of Right)
• 7.2. Các thao tác trên cây AVL
• 7.2.1. Cấu trúc dữ liệu cây AVL
• 7.2.2. Thao tác chèn vào cây AVL
• 7.2.2.1. Thuật toán chèn cây AVL
• 7.2.2.2. Thuật toán cân bằng trái (leftBalance)
• 7.2.2.3. Thuật toán cân bằng phải (rightBalance)
• 7.2.3. Thao tác xóa khỏi cây AVL
• 7.2.3.1. Thuật toán xóa nút cây AVL
• 7.2.3.2. Thuật toán cân bằng phải khi xóa (deleteRightBalance)
• 7.2.3.3. Thuật toán cân bằng trái khi xóa (deleteLeftBalance)
• 7.3. Cây B (B-Trees)

Tóm tắt

I. Tổng quan cây AVL trong cấu trúc dữ liệu và thuật toán

Trong lĩnh vực cấu trúc dữ liệu và thuật toán, việc tối ưu hóa thời gian tìm kiếm là một mục tiêu cốt lõi. Cây AVL, được đặt tên theo hai nhà phát minh Adelson-Velsky và Landis, ra đời như một giải pháp xuất sắc cho bài toán này. Về bản chất, cây AVL là một dạng cải tiến của cây tìm kiếm nhị phân (Binary Search Tree - BST). Điểm khác biệt mấu chốt nằm ở tính năng 'tự cân bằng'. Một cây AVL không chỉ duy trì thuộc tính sắp xếp của BST mà còn đảm bảo rằng tại mọi nút, chênh lệch chiều cao giữa cây con trái và cây con phải không bao giờ vượt quá 1. Yếu tố này, được gọi là hệ số cân bằng, là chìa khóa để ngăn chặn kịch bản tồi tệ nhất của BST, nơi cây bị 'suy biến' thành một danh sách liên kết, khiến độ phức tạp tìm kiếm tăng vọt lên O(n). Bằng cách duy trì trạng thái gần như cân bằng hoàn hảo, cây AVL đảm bảo rằng các thao tác cơ bản như tìm kiếm, chèn và xóa luôn đạt được độ phức tạp trung bình và tệ nhất là O(log n). Điều này biến nó thành một cấu trúc dữ liệu cực kỳ hiệu quả cho các ứng dụng yêu cầu hiệu năng truy xuất dữ liệu cao và ổn định, chẳng hạn như trong các hệ thống cơ sở dữ liệu hoặc các tác vụ lập chỉ mục. Việc tìm hiểu sâu về cây AVL là nền tảng quan trọng cho bất kỳ lập trình viên hay kỹ sư phần mềm nào muốn nắm vững các thuật toán tối ưu.

1.1. Định nghĩa cây AVL Cây tìm kiếm nhị phân tự cân bằng

Một cây được xác định là cây AVL nếu nó thỏa mãn đồng thời hai thuộc tính quan trọng. Thứ nhất, nó phải là một cây tìm kiếm nhị phân hợp lệ. Điều này có nghĩa là với mọi nút trong cây, tất cả các khóa (key) ở cây con bên trái đều nhỏ hơn khóa của nút đó, và tất cả các khóa ở cây con bên phải đều lớn hơn hoặc bằng khóa của nút đó. Thuộc tính này đảm bảo dữ liệu luôn được sắp xếp. Thứ hai, cây phải thỏa mãn điều kiện cân bằng. Cụ thể, tại mỗi nút, chiều cao của cây con trái và chiều cao của cây con phải chỉ được chênh lệch tối đa là 1. Sự chênh lệch này được đo lường bằng hệ số cân bằng (Balance Factor), được tính bằng chiều_cao(cây_con_phải) - chiều_cao(cây_con_trái). Hệ số này chỉ có thể nhận một trong ba giá trị: -1 (Lệch trái - Left High), 0 (Cân bằng - Equal Height), hoặc +1 (Lệch phải - Right High). Bất kỳ giá trị nào khác (-2 hoặc +2) đều cho thấy cây đã mất cân bằng tại nút đó và cần được điều chỉnh lại.

1.2. Hệ số cân bằng và đặc tính cốt lõi của một cây AVL

Hệ số cân bằng (Balance Factor) là khái niệm trung tâm của cấu trúc dữ liệu AVL. Nó định lượng mức độ cân bằng tại mỗi nút và là yếu tố kích hoạt các thuật toán tái cân bằng. Trong tài liệu của Dr. Duc Dung Nguyen, các trạng thái được định nghĩa rõ: 'left_higher' (LH) khi cây con trái cao hơn 1, 'equal_height' (EH) khi hai cây con bằng nhau, và 'right_higher' (RH) khi cây con phải cao hơn 1. Việc duy trì hệ số cân bằng trong phạm vi cho phép [-1, 0, 1] là đặc tính cốt lõi đảm bảo hiệu suất O(log n) của cây. Mỗi khi một thao tác chèn hoặc xóa được thực hiện, thuật toán sẽ cập nhật lại chiều cao và kiểm tra lại hệ số cân bằng của các nút trên đường đi từ nút bị thay đổi lên đến nút gốc. Nếu phát hiện một nút bị mất cân bằng, các phép xoay (rotation) sẽ được áp dụng ngay lập tức để khôi phục lại thuộc tính AVL, đảm bảo cây luôn ở trạng thái tối ưu cho các thao tác tìm kiếm sau này.

II. Thách thức của cây BST và sự cần thiết của cây AVL

Mặc dù cây tìm kiếm nhị phân (BST) là một cấu trúc dữ liệu mạnh mẽ trên lý thuyết, hiệu suất của nó trong thực tế lại phụ thuộc rất nhiều vào thứ tự dữ liệu được chèn vào. Thách thức lớn nhất của BST là nguy cơ bị suy biến. Khi các phần tử được chèn theo thứ tự đã được sắp xếp (tăng dần hoặc giảm dần), cây sẽ mất đi hình dạng phân nhánh vốn có và trở thành một cấu trúc tuyến tính giống như danh sách liên kết. Trong trường hợp này, chiều cao của cây sẽ là n (với n là số lượng nút), và thuật toán tìm kiếm sẽ mất hiệu quả, với độ phức tạp thời gian trong trường hợp xấu nhất là O(n). Điều này làm mất đi ưu thế vốn có của cấu trúc cây. Cây AVL được phát triển để giải quyết trực tiếp vấn đề này. Bằng cách áp đặt một điều kiện cân bằng nghiêm ngặt và tự động thực hiện các phép xoay để duy trì nó, cấu trúc dữ liệu và thuật toán liên quan đến cây AVL đảm bảo rằng chiều cao của cây không bao giờ vượt quá một ngưỡng logarit của số lượng nút (cụ thể là khoảng 1.44 * log2(n)). Điều này đảm bảo độ phức tạp O(log n) cho các thao tác tìm kiếm, chèn, và xóa ngay cả trong những trường hợp xấu nhất, mang lại hiệu suất ổn định và có thể dự đoán được.

2.1. Phân tích trường hợp cây tìm kiếm nhị phân bị suy biến

Một cây tìm kiếm nhị phân bị suy biến (degenerate tree) xảy ra khi mỗi nút cha chỉ có một nút con. Ví dụ, nếu chèn các số 1, 2, 3, 4, 5 theo thứ tự, nút 2 sẽ là con phải của 1, nút 3 là con phải của 2, và cứ thế tiếp tục. Kết quả là một cây chỉ có các nhánh phải, trông giống hệt một danh sách liên kết. Khi cần tìm kiếm một phần tử, thuật toán phải duyệt qua từng nút một từ gốc, tương tự như duyệt một mảng. Hiệu suất tìm kiếm giảm từ O(log n) xuống O(n). Tình trạng này không chỉ xảy ra với dữ liệu được sắp xếp hoàn hảo mà còn có thể xuất hiện sau một chuỗi các thao tác chèn và xóa không ngẫu nhiên. Theo tài liệu giảng dạy, đây là lý do chính cho sự ra đời của các cây cân bằng như cây AVL, nhằm đảm bảo hiệu quả tìm kiếm không bị suy giảm trong các ứng dụng thực tế.

2.2. Tại sao O log n là mục tiêu quan trọng trong thuật toán

Trong phân tích thuật toán, độ phức tạp O(log n) (logarit) được coi là cực kỳ hiệu quả. Nó mô tả một thuật toán mà thời gian thực thi tăng rất chậm khi kích thước đầu vào (n) tăng lên. Ví dụ, nếu một tập dữ liệu tăng từ 1.000 phần tử lên 1.000.000 phần tử (tăng 1.000 lần), một thuật toán O(log n) chỉ cần tăng thời gian thực thi thêm một hằng số nhỏ (ví dụ, từ 10 bước lên 20 bước). Ngược lại, một thuật toán O(n) sẽ có thời gian thực thi tăng tương ứng 1.000 lần. Việc cây AVL đảm bảo được độ phức tạp O(log n) có ý nghĩa sống còn đối với các hệ thống xử lý lượng dữ liệu lớn. Nó cho phép ứng dụng duy trì tốc độ phản hồi nhanh chóng và khả năng mở rộng tốt, một yếu tố then chốt trong thiết kế các cấu trúc dữ liệu và thuật toán hiện đại.

III. Phương pháp xoay cây Bí quyết cân bằng cấu trúc cây AVL

Cơ chế cốt lõi giúp cây AVL duy trì trạng thái cân bằng chính là các phép xoay (rotations). Đây là những thao tác cục bộ, thay đổi cấu trúc của một vài nút để khôi phục lại hệ số cân bằng mà không làm mất đi thuộc tính của cây tìm kiếm nhị phân. Khi một thao tác chèn hoặc xóa làm cho một nút bị mất cân bằng (hệ số cân bằng là -2 hoặc +2), cây sẽ xác định một trong bốn trường hợp mất cân bằng để áp dụng phép xoay phù hợp. Có hai loại xoay cơ bản: xoay đơn (Single Rotation) và xoay kép (Double Rotation). Xoay đơn, bao gồm xoay trái (Rotate Left) và xoay phải (Rotate Right), được sử dụng cho các trường hợp 'Lệch trái-trái' và 'Lệch phải-phải'. Xoay kép, thực chất là sự kết hợp của một phép xoay trái và một phép xoay phải (hoặc ngược lại), được dùng để xử lý các trường hợp phức tạp hơn là 'Lệch trái-phải' và 'Lệch phải-trái'. Việc thực hiện chính xác các phép xoay này là trọng tâm của thuật toán chèn và xóa trong cây AVL, đảm bảo cấu trúc dữ liệu luôn được tối ưu hóa cho hiệu suất tìm kiếm.

3.1. Kỹ thuật xoay đơn Xoay trái Rotate Left và Xoay phải

Phép xoay phải (Rotate Right) được áp dụng khi một nút bị mất cân bằng do cây con bên trái của nó quá cao (trường hợp Lệch trái-trái). Giả sử nút mất cân bằng là A và con trái của nó là B. Phép xoay sẽ đưa B lên làm gốc mới, A trở thành con phải của B. Cây con phải cũ của B (nếu có) sẽ được gắn làm cây con trái mới của A. Thao tác này bảo toàn thứ tự của các khóa và giảm chiều cao của nhánh bị lệch. Ngược lại, phép xoay trái (Rotate Left) là hình ảnh phản chiếu, được dùng cho trường hợp Lệch phải-phải. Các thuật toán này, như được mô tả trong giả mã rotateRight và rotateLeft, chỉ đơn thuần là việc hoán đổi các con trỏ, do đó có độ phức tạp thời gian là O(1), cực kỳ nhanh chóng và hiệu quả.

3.2. Tìm hiểu về 4 trường hợp mất cân bằng phổ biến trong cây

Tài liệu của Dr. Duc Dung Nguyen xác định bốn trường hợp mất cân bằng cần xử lý trong cây AVL:

1. Lệch trái-trái (Left of Left): Cây con của một nút 'Lệch trái' (Left High) tiếp tục cao lên ở nhánh trái. Trường hợp này được giải quyết bằng một phép xoay phải duy nhất tại nút mất cân bằng.
2. Lệch phải-phải (Right of Right): Tương tự, cây con của một nút 'Lệch phải' (Right High) tiếp tục cao lên ở nhánh phải. Giải pháp là một phép xoay trái duy nhất.
3. Lệch phải-trái (Right of Left): Cây con của một nút 'Lệch trái' bị cao lên ở nhánh phải. Trường hợp này cần một phép xoay kép: đầu tiên là xoay trái tại cây con, sau đó là xoay phải tại nút gốc mất cân bằng.
4. Lệch trái-phải (Left of Right): Cây con của một nút 'Lệch phải' bị cao lên ở nhánh trái. Tương tự, cần xoay phải tại cây con rồi xoay trái tại nút gốc. Việc nhận diện và xử lý đúng bốn trường hợp này là chìa khóa để triển khai thành công thuật toán AVL.

IV. Hướng dẫn các thao tác chính trên cấu trúc dữ liệu AVL

Các thao tác chính trên một cây AVL bao gồm tìm kiếm, chèn và xóa. Thao tác tìm kiếm hoàn toàn giống với trên một cây tìm kiếm nhị phân thông thường, tận dụng thuộc tính sắp xếp để nhanh chóng loại bỏ một nửa cây ở mỗi bước. Tuy nhiên, các thao tác chèn và xóa trong cây AVL phức tạp hơn đáng kể vì chúng có thể làm thay đổi chiều cao của cây và gây mất cân bằng. Do đó, sau mỗi lần chèn hoặc xóa, thuật toán phải thực hiện thêm một bước quan trọng: đi ngược từ vị trí thay đổi lên đến gốc, cập nhật lại hệ số cân bằng của các nút trên đường đi. Nếu phát hiện một nút có hệ số cân bằng là -2 hoặc +2, các phép xoay tương ứng sẽ được kích hoạt để tái cân bằng cây. Quá trình này đảm bảo rằng sau mỗi thao tác, cây vẫn duy trì được thuộc tính AVL. Mặc dù có thêm bước cân bằng, nhưng vì chiều cao cây luôn là O(log n) và mỗi phép xoay chỉ tốn O(1), tổng độ phức tạp của các thao tác chèn và xóa vẫn được duy trì ở mức O(log n), một sự đánh đổi xứng đáng để có được hiệu suất tìm kiếm ổn định.

4.1. Thuật toán chèn một nút mới và quá trình tái cân bằng

Thuật toán AVLInsert, thường được cài đặt đệ quy, hoạt động theo các bước sau. Đầu tiên, nó tìm vị trí thích hợp để chèn nút mới, tương tự như trong một BST. Sau khi chèn, khi quay trở lại từ các lời gọi đệ quy, thuật toán sẽ kiểm tra và cập nhật hệ số cân bằng cho các nút cha. Một biến boolean, chẳng hạn taller, được sử dụng để cho biết liệu việc chèn có làm tăng chiều cao của cây con hay không. Nếu một cây con trở nên cao hơn và làm cho nút cha bị mất cân bằng (ví dụ, từ 'Equal Height' thành 'Left High'), quá trình tiếp tục. Nếu nút cha đã ở trạng thái 'Left High' và cây con trái lại cao thêm, nó sẽ mất cân bằng. Lúc này, các hàm cân bằng như leftBalance sẽ được gọi để thực hiện các phép xoay cần thiết (xoay đơn hoặc xoay kép) và khôi phục lại cấu trúc cây AVL.

4.2. Quy trình xóa một nút khỏi cây và các bước cân bằng lại

Thao tác xóa trong cây AVL (AVLDelete) cũng tuân theo logic của BST, nhưng kèm theo việc tái cân bằng. Sau khi tìm và xóa nút, cây có thể trở nên ngắn hơn tại nhánh đó. Tương tự như khi chèn, thuật toán sẽ đi ngược lên gốc và cập nhật hệ số cân bằng. Một biến shorter được sử dụng để theo dõi sự thay đổi chiều cao. Nếu việc xóa làm một nhánh ngắn đi và khiến nút cha mất cân bằng, các hàm cân bằng như deleteRightBalance hoặc deleteLeftBalance sẽ được gọi. Ví dụ, nếu một nút đang ở trạng thái 'Left High' và cây con bên phải của nó (vốn đã thấp hơn) bị xóa đi một nút và trở nên ngắn hơn nữa, nút đó sẽ mất cân bằng. Các phép xoay sẽ được áp dụng để điều chỉnh lại cấu trúc, đảm bảo cây AVL vẫn tuân thủ các quy tắc về chiều cao.

V. Ứng dụng và đánh giá hiệu năng của cấu trúc cây AVL

Cấu trúc dữ liệu và thuật toán liên quan đến cây AVL có nhiều ứng dụng quan trọng trong thực tế, đặc biệt là trong các hệ thống đòi hỏi thời gian truy xuất dữ liệu nhanh và có thể dự đoán được. Do đảm bảo độ phức tạp tìm kiếm, chèn, xóa luôn là O(log n), cây AVL là lựa chọn lý tưởng cho việc triển khai các cấu trúc dữ liệu như từ điển, tập hợp (set), hoặc các hệ thống lập chỉ mục trong cơ sở dữ liệu. Ví dụ, các công cụ tìm kiếm trong hệ điều hành hoặc các hệ quản trị cơ sở dữ liệu có thể sử dụng cây AVL hoặc các biến thể của nó để quản lý các chỉ mục, giúp tăng tốc độ truy vấn một cách đáng kể. Khi so sánh với cây tìm kiếm nhị phân thông thường, cây AVL vượt trội hơn hẳn về hiệu suất trong trường hợp xấu nhất và trường hợp trung bình, mặc dù phải trả giá bằng sự phức tạp trong việc cài đặt và một chút chi phí hiệu năng cho các thao tác chèn/xóa do phải tái cân bằng. Tuy nhiên, sự ổn định này làm cho cây AVL trở thành một công cụ đáng tin cậy trong các ứng dụng quan trọng.

5.1. Vai trò của cây AVL trong các hệ thống cơ sở dữ liệu

Trong các hệ thống cơ sở dữ liệu, việc lập chỉ mục (indexing) là rất quan trọng để tăng tốc độ truy vấn. Một chỉ mục về cơ bản là một cấu trúc dữ liệu cho phép tìm kiếm nhanh các bản ghi dựa trên giá trị của một cột nào đó. Cây AVL và các cây cân bằng khác như B-Trees là những lựa chọn hàng đầu để xây dựng các chỉ mục này. Bằng cách lưu trữ các giá trị khóa của cột được lập chỉ mục trong một cây AVL, hệ thống có thể nhanh chóng xác định vị trí của bản ghi mong muốn với độ phức tạp O(log n). Điều này hiệu quả hơn rất nhiều so với việc quét toàn bộ bảng (full table scan), một thao tác có độ phức tạp O(n). Mặc dù B-Trees thường được ưa chuộng hơn cho lưu trữ trên đĩa, khái niệm cân bằng của cây AVL vẫn là nền tảng lý thuyết quan trọng.

5.2. So sánh hiệu năng giữa cây AVL và cây tìm kiếm nhị phân

Hiệu năng là điểm khác biệt lớn nhất giữa cây AVL và cây tìm kiếm nhị phân (BST). Đối với BST, hiệu năng tìm kiếm có thể dao động từ rất tốt, O(log n) trong trường hợp cây cân bằng, đến rất tệ, O(n) trong trường hợp cây suy biến. Sự không ổn định này làm cho BST trở nên rủi ro trong các ứng dụng thực tế. Ngược lại, cây AVL luôn đảm bảo hiệu năng tìm kiếm là O(log n) bất kể thứ tự chèn dữ liệu. Tuy nhiên, sự đảm bảo này có một chi phí: các thao tác chèn và xóa trên cây AVL chậm hơn một chút so với BST (trong trường hợp tốt nhất) do phải thực hiện thêm các bước kiểm tra và phép xoay để tái cân bằng. Do đó, nếu dữ liệu đầu vào được đảm bảo là ngẫu nhiên và các thao tác ghi nhiều hơn đọc, BST có thể là lựa chọn tốt. Nhưng đối với các ứng dụng ưu tiên tốc độ đọc và sự ổn định, cây AVL là lựa chọn vượt trội.

Nội dung chính

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

Tài liệu bài giảng thuộc học phần Cấu trúc Dữ liệu và Giải thuật (Data Structure and Algorithms - mã môn CO2003), được biên soạn bởi TS. Nguyễn Đức Dũng (Duc Dung Nguyen, PhD. - [e-mail]) thuộc Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa – ĐHQG TP.HCM. Trong chương trình đào tạo kỹ sư Công nghệ Thông tin và Khoa học Máy tính, đây là môn học cơ sở ngành bắt buộc, cung cấp các nguyên lý tổ chức dữ liệu bộ nhớ và thiết kế giải thuật tối ưu.

Tài liệu tập trung vào Chương 7: Cây AVL (Chapter 7 - AVL Tree) với quy mô 76 slide, được xây dựng nhằm đáp ứng các chuẩn đầu ra (Learning Outcomes) từ L.1 đến L.8 của môn học. Cụ thể, bài giảng trang bị cho người học khả năng:

• L.1: Mô tả các khái niệm 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).
• L.2 & L.3: Mô tả cấu trúc lưu trữ và các phương thức cần thiết cho cấu trúc cây bằng mã giả (pseudocode).
• L.4: Xác định tầm quan trọng của đặc tính cân bằng trong cây và đưa ra ví dụ chứng minh.
• L.5: Nhận diện các trường hợp mất cân bằng của cây AVL và B-Tree, trình bày phương pháp tái cân bằng từng bước bằng sơ đồ.
• L.6 & L.7: Cài đặt cây nhị phân và cây AVL bằng ngôn ngữ C/C++; ứng dụng cấu trúc cây để giải quyết bài toán tìm kiếm 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ử nghiệm đánh giá hiệu năng.

Tài liệu tiếp cận kiến thức theo phương pháp quy nạp: bắt đầu từ phân tích giới hạn của Cây tìm kiếm nhị phân thông thường (BST), định nghĩa toán học về độ cân bằng, chuẩn hóa 4 trường hợp mất cân bằng, đến xây dựng mã giả hoàn chỉnh cho các thao tác chèn, xóa và tái cân bằng. Nguồn tư liệu thuật toán và hình ảnh minh họa được trích xuất từ giáo trình quốc tế Data Structures - A Pseudocode Approach with C++ (Richard F. Gilberg & Behrouz A. Forouzan).

---

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

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

Cấu trúc bài giảng Chương 7 phân định thành các khối chủ đề theo tiến trình logic chặt chẽ:

1. Khái niệm Cây AVL (AVL Tree Concepts):

   • Định nghĩa: Cây AVL (được đặt tên theo hai nhà toán học G.M. Adel'son-Vel'skii và E.M. Landis) là một cây tìm kiếm nhị phân (Binary Search Tree - BST) thỏa mãn đồng thời hai điều kiện:
     1. Đặc tính BST: Khóa tại mỗi nút lớn hơn tất cả các khóa ở cây con bên trái và nhỏ hơn hoặc bằng các khóa ở cây con bên phải.
     2. Đặc tính cân bằng: Hiệu số chiều cao giữa cây con trái ($H_L$) và cây con phải ($H_R$) của nút đó không vượt quá 1 ($|H_L - H_R| \le 1$), và các cây con cũng là cây AVL.
   • Hệ số cân bằng (Balance Factor): Được phân loại thành 3 trạng thái cụ thể:
     • left_higher (LH): $H_L = H_R + 1$
     • equal_height (EH): $H_L = H_R$
     • right_higher (RH): $H_R = H_L + 1$
   • Phân loại cây AVL và Non-AVL: Minh họa qua các cây dữ liệu mẫu (ví dụ cây chứa các khóa 8, 5, 10, 3, 6, 9, 12, 1, 4, 7 là cây AVL; các cây có nhánh lệch tạo chênh lệch chiều cao lớn hơn 1 được xác định là Non-AVL).

2. Lý do sử dụng Cây AVL và Các trường hợp mất cân bằng (Why AVL Trees & Balancing Trees):

   • Nguyên nhân suy biến: Khi dữ liệu được chèn vào BST theo thứ tự sắp xếp ($1, 2, 3, \dots$), BST sẽ suy biến thành danh sách liên kết, đẩy độ phức tạp tìm kiếm lên mức $O(n)$. Cây AVL đảm bảo cấu trúc luôn cân bằng, duy trì độ phức tạp tìm kiếm ở mức tối ưu $O(\log_2 n)$.
   • 4 trường hợp mất cân bằng:
     • Left of Left (LL): Cây con trái của một cây đang ở trạng thái lệch trái (LH) tiếp tục bị lệch trái. Khắc phục bằng một phép quay đơn sang phải (rotateRight).
     • Right of Right (RR): Cây con phải của một cây đang ở trạng thái lệch phải (RH) tiếp tục bị lệch phải. Khắc phục bằng một phép quay đơn sang trái (rotateLeft).
     • Right of Left (RL - theo slide định nghĩa là cây con phải của một cây lệch trái): Khắc phục bằng phép quay kép: quay trái cây con bên trái, sau đó quay phải nút gốc.
     • Left of Right (LR - theo slide định nghĩa là cây con trái của một cây lệch phải): Khắc phục bằng phép quay kép: quay phải cây con bên phải, sau đó quay trái nút gốc.

3. Cấu trúc lưu trữ và Thao tác giải thuật (AVL Tree Operations):

   • Cấu trúc dữ liệu: Khai báo cấu trúc dạng nút động liên kết con trỏ (dataType gồm key, field1; node gồm data, con trỏ left, right, trường balance; avlTree quản lý con trỏ root). Tài liệu lưu ý cấu trúc mảng (Array) không phù hợp để biểu diễn cây AVL.
   • Giải thuật phép quay cơ bản:
     • rotateRight(ref root): Đổi con trỏ chuyển nút con trái lên làm gốc mới, cây con phải của con trái thành con trái của gốc cũ.
     • rotateLeft(ref root): Đổi con trỏ chuyển nút con phải lên làm gốc mới, cây con trái của con phải thành con phải của gốc cũ.
   • Giải thuật chèn (AVLInsert): Cài đặt đệ quy sử dụng biến cờ taller (kiểu Boolean) để ghi nhận sự gia tăng chiều cao cây con khi quay lui (back out). Tùy thuộc vào trạng thái cân bằng của gốc (LH, EH, RH), hàm kích hoạt leftBalance hoặc rightBalance để tái lập cân bằng.
   • Giải thuật xóa (AVLDelete): Cài đặt đệ quy kết hợp tìm nút thay thế (nút cực phải của cây con trái), giải phóng bộ nhớ (recycle), sử dụng biến cờ shorter để kích hoạt tái cân bằng thông qua deleteRightBalance hoặc deleteLeftBalance.

4. Cây đa phân (B-Trees):

   • Mở rộng khái niệm cây tìm kiếm sang cấu trúc cây nhiều nhánh (multi-way search tree), phục vụ tổ chức và truy xuất dữ liệu trên bộ nhớ ngoài.

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

• Nguyên lý cân bằng chiều cao: Khái niệm hiệu số chiều cao giữa hai cây con và cách lượng hóa trạng thái cân bằng qua biến số balance factor tại từng nút.
• Biến đổi cấu trúc bằng phép quay cục bộ: Kỹ thuật điều chỉnh liên kết con trỏ không làm thay đổi tính chất thứ tự của cây tìm kiếm nhị phân (in-order traversal order invariant).
• Cơ chế lan truyền trạng thái trong đệ quy: Kỹ thuật truyền tham chiếu cờ trạng thái (taller, shorter) ngược từ điểm chèn/xóa tại lá lên gốc để quyết định điểm xoay cục bộ.

Kỹ năng phát triển

• Kỹ năng thiết kế và đọc hiểu mã giả: Đọc hiểu và chuyển thể các thuật toán mã giả chuẩn (AVLInsert, AVLDelete, rotateLeft, rotateRight) thành chương trình thực thi.
• Kỹ năng cài đặt C/C++: Hiện thực hóa cấu trúc dữ liệu nút động, quản lý bộ nhớ thông qua con trỏ (pointer, recycle).
• Kỹ năng phân tích độ phức tạp: Đánh giá chi phí tính toán qua ký hiệu Big-O, chứng minh cấu trúc AVL chặn được trường hợp suy biến xấu nhất ($O(n)$ của BST) về mức $O(\log_2 n)$.

---

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

Bài giảng CO2003 sử dụng phương pháp sư phạm cấu trúc hóa, phối hợp giữa lý thuyết hình thức, mô hình hóa giải thuật và mã giả:

1. Phương pháp sư phạm trực quan: Mỗi trường hợp mất cân bằng (LL, RR, RL, LR) đều được minh họa bằng sơ đồ cây cụ thể trước và sau khi thực hiện phép quay. Việc này giúp sinh viên hiểu rõ bản chất chuyển dịch con trỏ trước khi tiếp cận mã giả.
2. Hệ thống mã giả chuẩn hóa: Toàn bộ thuật toán được mô tả qua các hợp đồng hàm rõ ràng gồm các mục Pre (điều kiện tiên quyết), Post (kết quả sau xử lý), Return (giá trị trả về) và các tham số truyền theo tham chiếu (ref root, ref taller, ref shorter, ref success).
3. Phân tích ca (Case Analysis) chi tiết: Trong các hàm cân bằng như leftBalance, rightBalance, deleteRightBalance, deleteLeftBalance, bài giảng bóc tách từng nhánh rẽ dựa trên giá trị hệ số cân bằng của cây con (LH, EH, RH), giúp sinh viên bao quát toàn bộ các trường hợp biên của thuật toán.
4. Phương pháp đánh giá: Đánh giá năng lực của người học thông qua:
   • Bài tập vẽ và mô phỏng từng bước tái cân bằng cây khi chèn/xóa dãy khóa.
   • Cài đặt hoàn chỉnh chương trình trên C/C++.
   • Phát triển chương trình thử nghiệm (experiment/program) nhằm đo lường và đánh giá thực nghiệm thời gian thực thi của các thao tác trên cây (theo chuẩn đầu ra L.8).

---

Điểm nổi bật và cập nhật

• Tính học thuật chuẩn mực: Nội dung bài giảng bám sát tài liệu tham khảo chuyên ngành Data Structures - A Pseudocode Approach with C++, bảo đảm tính chính xác trong định nghĩa và chuẩn hóa cú pháp giải thuật.
• Trình bày toàn diện giải thuật xóa (AVL Delete): Khác với nhiều tài liệu chỉ tập trung vào thao tác chèn, bài giảng này cung cấp đầy đủ chi tiết thuật toán xóa nút (AVLDelete) và cả 2 hàm tái cân bằng phức tạp sau khi xóa (deleteRightBalance và deleteLeftBalance), phân tích rõ ràng trường hợp cây con giảm độ cao và cách cập nhật lại hệ số cân bằng.
• Tối ưu hóa logic đệ quy: Giải thuật cân bằng được tích hợp trực tiếp vào pha thoái lui của hàm đệ quy (back out of the tree), giúp quá trình kiểm tra và tái cân bằng diễn ra tự động dọc theo đường dẫn từ nút lá về gốc mà không cần duyệt lại toàn bộ cây.
• Tính định hướng ứng dụng: Nêu rõ lý do kỹ thuật vì sao cấu trúc mảng không phù hợp với cây AVL, đồng thời định hướng sinh viên sử dụng cây AVL trong các bài toán tìm kiếm hiệu năng cao và mở rộng sang B-Tree cho các hệ thống lưu trữ khối lượng lớn.

---

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

• Sinh viên đại học: Sinh viên năm thứ 2 hoặc năm thứ 3 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, Hệ thống Thông tin đang theo học học phần Cấu trúc Dữ liệu và Giải thuật (CO2003).
• Yêu cầu kiến thức tiên quyết (Prerequisites):
  • Nắm vững kỹ thuật lập trình C/C++, đặc biệt là con trỏ (pointers), cấp phát/giải phóng bộ nhớ động.
  • Hiểu rõ kỹ thuật lập trình đệ quy.
  • Đã học qua cấu trúc dữ liệu danh sách liên kết (Linked List) và Cây tìm kiếm nhị phân cơ bản (BST).
• Giảng viên: Sử dụng làm tài liệu khung để giảng dạy bài học Cây AVL trên lớp, hướng dẫn sinh viên làm bài tập lập trình lớn (assignment), và xây dựng câu hỏi thi đánh giá chuẩn đầu ra.
• Người tự học và nghiên cứu: Lập trình viên cần nghiên cứu cấu trúc dữ liệu nâng cao để tối ưu hóa giải thuật tìm kiếm hoặc chuẩn bị cho các kỳ thi đánh giá năng lực thuật toán.

---

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 được thiết kế cho sinh viên ngành Khoa học và Kỹ thuật Máy tính thuộc Trường Đại học Bách Khoa – ĐHQG TP.HCM đang học môn CO2003, cũng như người học cần tài liệu chuẩn hóa về mã giả và giải thuật cây tự cân bằng.

2. Cần kiến thức nền nào để học chương Cây AVL?

Người học cần có kiến thức vững về ngôn ngữ C/C++ (thao tác con trỏ và quản lý bộ nhớ động), hiểu rõ cơ chế đệ quy, nắm vững đặc tính của Cây tìm kiếm nhị phân (BST) và phương pháp đánh giá độ phức tạp thuật toán bằng ký hiệu Big-O.

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

Cây BST thông thường có thể bị suy biến thành dạng danh sách tuyến tính với độ phức tạp tìm kiếm $O(n)$ khi các phần tử được chèn theo thứ tự tăng hoặc giảm dần. Cây AVL bổ sung điều kiện cân bằng chiều cao ($|H_L - H_R| \le 1$), tự động cân bằng lại qua các phép quay, đả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. Làm sao để tự học và nắm vững các giải thuật trong bài giảng?

Người học nên thực hiện theo quy trình 4 bước:

1. Hiểu rõ định nghĩa và 3 trạng thái của hệ số cân bằng (LH, EH, RH).
2. Tự vẽ mô phỏng 4 trường hợp mất cân bằng (LL, RR, RL, LR) trên giấy và thực hiện các phép quay tương ứng.
3. Phân tích luồng biến cờ taller/shorter trong mã giả AVLInsert/AVLDelete.
4. Chuyển đổi mã giả sang mã nguồn C/C++ hoàn chỉnh và chạy kiểm thử với các bộ dữ liệu khác nhau.

5. Tài liệu tham khảo chính của bài giảng là gì?

Tài liệu trích xuất cấu trúc thuật toán, mã giả và sơ đồ minh họa từ cuốn giáo trình Data Structures - A Pseudocode Approach with C++ của hai tác giả Richard F. Gilberg và Behrouz A. Forouzan.

---

Kết luận

Bài giảng Chapter 7 - AVL Tree thuộc học phần Data Structure and Algorithms [CO2003] của Trường Đại học Bách Khoa – ĐHQG TP.HCM cung cấp hệ thống kiến thức hoàn chỉnh về cây tìm kiếm nhị phân tự cân bằng. Tài liệu kết hợp chặt chẽ giữa định nghĩa toán học, sơ đồ biến đổi trực quan và hệ thống mã giả chi tiết cho các thao tác phức tạp như AVLInsert, AVLDelete cùng các thuật toán quay cân bằng. Để tiếp thu môn học hiệu quả, người học nên tuân thủ lộ trình từ đọc hiểu mã giả, phân tích độ phức tạp Big-O đến thực hành cài đặt hoàn chỉnh bằng C/C++ kết hợp tham khảo giáo trình chuẩn Data Structures - A Pseudocode Approach with C++.

Trích đoạn nội dung tài liệu

Data Structure and Algorithms [CO2003] Chapter 7 - AVL Tree Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Faculty of Computer Science and Engineering Hochiminh city University of Technology Contents 1. AVL Tree Concepts 2. AVL Tree Operations 4.

B-Trees Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 1 / 76 Outcomes • L.1 - Depict the following concepts: binary tree, complete binary tree, balanced binary tree, AVL tree, multi-way tree, etc.2 - Describe the strorage structure for tree structures using pseudocode.3 - List necessary methods supplied for tree structures, and describe them using pseudocode.4 - Identify the importance of “blanced” feature in tree structures and give examples to demonstate it.5 - Identiy cases in which AVL tree and B-tree are unblanced, and demonstrate methods to resolve all the cases step-by-step using figures. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 2 / 76 Outcomes • L.6 - Implement binary tree and AVL tree using C/C++.7 - Use binary tree and AVL tree to solve problems in real-life, especially related to searching techniques.8 - Analyze the complexity and develop experiment (program) to evaluate methods supplied for tree structures.4 - Develop recursive implementations for methods supplied for the following structures: list, tree, heap, searching, and graphs.2 - Analyze algorithms and use Big-O notation to characterize the computational complexity of algorithms composed by using the following control structures: sequence, branching, and iteration (not recursion).

Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 3 / 76 AVL Tree Concepts AVL Tree Definition AVL Tree is: • A Binary Search Tree, • in which the heights of the left and right subtrees of the root differ by at most 1, and • the left and right subtrees are again AVL trees.Adel’son-Vel’skii and E. AVL Tree is a Binary Search Tree that is balanced tree. Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 4 / 76 AVL Tree A binary tree is an AVL Tree if • Each node satisfies BST property: key of the node is greater than the key of each node in its left subtree and is smaller than or equals to the key of each node in its right subtree. • Each node satisfies balanced tree property: the difference between the heights of the left subtree and right subtree of the node does not exceed one. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 5 / 76 AVL Tree Balance factor • left_higher (LH): HL = HR + 1 • equal_height (EH): HL = HR • right_higher (RH): HR = HL + 1 (HL , HR : the heights of left and right subtrees) Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 6 / 76 AVL Trees 8 8 8 8 5 5 10 5 10 9 3 6 12 8 5 10 3 6 9 1 4 5 7 Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 7 / 76 Non-AVL Trees 8 8 5 10 3 9 12 8 8 5 10 5 10 12 3 12 15 1 15 Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 8 / 76 Why AVL Trees? • When data elements are inserted in a BST in sorted order: 1, 2, 3,. BST becomes a degenerate tree.

Search operation takes O(n), which is inefficient. • It is possible that after a number of insert and delete operations, a binary tree may become unbalanced and inscrease in height. • AVL trees ensure that the complexity of search is O(log2 n). Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 9 / 76 AVL Balance Balancing Trees • When we insert a node into a tree or delete a node from a tree, the resulting tree may be unbalanced. → rebalance the tree. • Four unbalanced tree cases: • left of left: a subtree of a tree that is left high has also become left high; • right of right: a subtree of a tree that is right high has also become right high; • right of left: a subtree of a tree that is left high has become right high; • left of right: a subtree of a tree that is right high has become left high; Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 10 / 76 Unbalanced tree cases (Source: Data Structures - A Pseudocode Approach with C++) Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 11 / 76 Unbalanced tree cases (Source: Data Structures - A Pseudocode Approach with C++) Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 12 / 76 Rotate Right Algorithm rotateRight(ref root <pointer>) Exchanges pointers to rotate the tree right. Pre: root is pointer to tree to be rotated Post: node rotated and root updated tempPtr = root->left root->left = tempPtr->right tempPtr->right = root Return tempPtr End rotateRight Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 13 / 76 Rotate Right (Source: Data Structures - A Pseudocode Approach with C++) Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 14 / 76 Rotate Left Algorithm rotateLeft(ref root <pointer>) Exchanges pointers to rotate the tree left. Pre: root is pointer to tree to be rotated Post: node rotated and root updated tempPtr = root->right root->right = tempPtr->left tempPtr->left = root Return tempPtr End rotateLeft Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 15 / 76 Balancing Trees - Case 1: Left of Left Out of balance condition created by a left high subtree of a left high tree → balance the tree by rotating the out of balance node to the right. (Source: Data Structures - A Pseudocode Approach with C++) Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 16 / 76 Balancing Trees - Case 1: Left of Left (Source: Data Structures - A Pseudocode Approach with C++) Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 17 / 76 Balancing Trees - Case 2: Right of Right Out of balance condition created by a right high subtree of a right high tree → balance the tree by rotating the out of balance node to the left. (Source: Data Structures - A Pseudocode Approach with C++) Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 18 / 76 Balancing Trees - Case 2: Right of Right (Source: Data Structures - A Pseudocode Approach with C++) Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 19 / 76 Balancing Trees - Case 3: Right of Left Out of balance condition created by a right high subtree of a left high tree → balance the tree by two steps: 1. rotating the left subtree to the left; 2. rotating the root to the right. (Source: Data Structures - A Pseudocode Approach with C++) Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 20 / 76 Balancing Trees - Case 3: Right of Left Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 21 / 76 Balancing Trees - Case 4: Left of Right Out of balance condition created by a left high subtree of a right high tree → balance the tree by two steps: 1. rotating the right subtree to the right; 2. rotating the root to the left.

(Source: Data Structures - A Pseudocode Approach with C++) Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 22 / 76 Balancing Trees - Case 4: Left of Right Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 23 / 76 AVL Tree Operations AVL Tree Structure node // G e n e r a l dataTye : d a t a <dataType> dataType l e f t <p o i n t e r > k e y <keyType> r i g h t <p o i n t e r > f i e l d 1 <. > avlTree end dataType r o o t <p o i n t e r > end a v l T r e e Note: Array is not suitable for AVL Tree.

Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 24 / 76 AVL Tree Operations • Search and retrieval are the same for any binary tree. • AVL Insert • AVL Delete Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 25 / 76 AVL Insert • Insert can make an out of balance condition.

• Otherwise, some inserts can make an automatic balancing. Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 26 / 76 AVL Insert Algorithm Algorithm AVLInsert(ref root <pointer>, val newPtr <pointer>, ref taller <boolean>) Using recursion, insert a node into an AVL tree. Pre: root is a pointer to first node in AVL tree/subtree newPtr is a pointer to new node to be inserted Post: taller is a Boolean: true indicating the subtree height has increased, false indicating same height Return root returned recursively up the tree Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 27 / 76 AVL Insert Algorithm // Insert at root if root null then root = newPtr taller = true return root end Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 28 / 76 AVL Insert Algorithm if newPtr->data.key < root->data.key then root->left = AVLInsert(root->left, newPtr, taller) // Left subtree is taller if taller then if root is LH then root = leftBalance(root, taller) else if root is EH then root->balance = LH else root->balance = EH taller = false end end Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 29 / 76 AVL Insert Algorithm else root->right = AVLInsert(root->right, newPtr, taller) // Right subtree is taller if taller then if root is LH then root->balance = EH taller = false else if root is EH then root->balance = RH else root = rightBalance(root, taller) end end end return root End Lecturer: Duc AVLInsert Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 30 / 76 AVL Left Balance Algorithm Algorithm leftBalance(ref root <pointer>, ref taller <boolean>) This algorithm is entered when the left subtree is higher than the right subtree.

Pre: root is a pointer to the root of the [sub]tree taller is true Post: root has been updated (if necessary) taller has been updated Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 31 / 76 AVL Left Balance Algorithm leftTree = root->left // Case 1: Left of left. Single rotation right. if leftTree is LH then root = rotateRight(root) root->balance = EH leftTree->balance = EH taller = false Lecturer: Duc Dung Nguyen, PhD.

Contact: [e-mail] Data Structure and Algorithms [CO2003] 32 / 76 AVL Left Balance Algorithm else rightTree = leftTree->right if rightTree->balance = LH then root->balance = RH leftTree->balance = EH else if rightTree->balance = EH then leftTree->balance = EH else root->balance = EH leftTree->balance = LH end rightTree->balance = EH root->left = rotateLeft(leftTree) root = rotateRight(root), taller = false end return root Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 33 / 76 AVL Right Balance Algorithm Algorithm rightBalance(ref root <pointer>, ref taller <boolean>) This algorithm is entered when the right subtree is higher than the left subtree. Pre: root is a pointer to the root of the [sub]tree taller is true Post: root has been updated (if necessary) taller has been updated Lecturer: Duc Dung Nguyen, PhD. Contact: [e-mail] Data Structure and Algorithms [CO2003] 34 / 76 AVL Right Balance Algorithm rightTree = root->right // Case 1: Right of right.

Single rotation left.