tailieunhanh - Bài giảng Cấu trúc dữ liệu và giải thuật: Cây AA (AA tree) - ĐH KHTN TPHCM

Cây AA được đặt tên theo tác giả Arne Anderson (Thụy Điển). Trong chương này chúng ta sẽ tìm hiểu về cây AA thông qua một số nội dung cơ bản sau: Mức của node, liên kết ngang, tính chất cây AA, các phép biến đổi cây, các thao tác trên cây,. . | 73 AA tree Cấu trúc dữ liệu và giải thuật - HCMUS 2011 74 Được đặt tên theo tác giả Arne Anderson (Thụy Điển). Công trình được công bố năm 1993 (Balanced Search Trees Made Simple). Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 1 75 Mức của node Liên kết ngang Cấu trúc dữ liệu và giải thuật - HCMUS 2011 76 Mức của node: Số liên kết trái từ node đó đến node NULL. Mức của NULL là 0. Mức của node lá là 1. 15 Mức 2 Mức 1 5 10 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 2 77 Liên kết ngang: Liên kết giữa node cha và node con có cùng mức. 15 5 10 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 78 Cây AA là cây nhị phân tìm kiếm thỏa mãn các tính chất sau: [1] Mức của node con trái bắt buộc phải nhỏ hơn mức của node cha. [2] Mức của node con bên phải nhỏ hơn hoặc bằng mức của node cha. Liên kết ngang bắt buộc hướng sang phải. [3] Mức của node cháu bên phải bắt buộc nhỏ hơn mức của node ông. Không tồn tại 2 liên kết ngang liên tiếp. [4] Mọi node có mức lớn hơn 1 phải có 2 node con. [5] Nếu một node không có liên kết ngang phải thì cả hai node con của nó phải cùng mức. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 3 79 70 30 15 5 10 50 35 20 40 60 55 85 65 80 90 Mức của các node? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 80 70 30 15 5 10 50 20 35 40 60 55 85 65 80 90 So sánh mức của node con trái với mức của node cha trực tiếp của nó? Các cặp node: 15 và 30, 5 và 15, 50 và 70, 35 và 50, 55 và 60, 80 và 85 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 4 81 70 30 15 5 10 50 35 20 40 60 55 85 65 80 90 Các liên kết ngang? Hướng của liên kết ngang? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 82 70 30 15 5 10 50 20 35 40 60 55 85 65 80 90 Có tồn tại 2 liên kết ngang liên tiếp? Cấu trúc dữ liệu và giải thuật - HCMUS .