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,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Cây AA (AA tree) - ĐH KHTN TPHCM73AA treeCấu trúc dữ liệu và giải thuật - HCMUS 201174Đượ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 (BalancedSearch Trees Made Simple).Cấu trúc dữ liệu và giải thuật - HCMUS 2011©FIT-HCMUS175Mức của nodeLiên kết ngangCấu trúc dữ liệu và giải thuật - HCMUS 201176Mức của node: Sốliên kết trái từ node đó đến node NULL. Mứccủa NULL là 0. Mức của node lá là 1.15Mức 2Mức 151020Cấu trúc dữ liệu và giải thuật - HCMUS 2011©FIT-HCMUS277Liên kết ngang: Liênkết giữa node cha và node con có cùng mức.1551020Cấu trúc dữ liệu và giải thuật - HCMUS 201178Cây AA là cây nhị phân tìm kiếm thỏa mãn các tính chấtsau:[1] Mức của node con trái bắt buộc phải nhỏ hơn mức của nodecha.[2] Mức của node con bên phải nhỏ hơn hoặc bằng mức của nodecha.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 concủa nó phải cùng mức.Cấu trúc dữ liệu và giải thuật - HCMUS 2011©FIT-HCMUS37970301551050352040605585658090Mức của các node?Cấu trúc dữ liệu và giải thuật - HCMUS 20118070301551050203540605585658090So 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à 85Cấu trúc dữ liệu và giải thuật - HCMUS 2011©FIT-HCMUS48170301551050352040605585658090Cá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 20118270301551050203540605585658090Có 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 2011©FIT-HCMUS5