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

Tài liệu nghiên cứu Data structure and algorithms cấu trúc dữ liệu và thuật toán chapter 7 avl tree, tổng hợp lý thuyết và thực hành, cung cấp kiến thức chuyên sâu về toán học.

• 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.

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.