Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AA cung cấp cho người đọc các kiến thức về cây AA, cấu trúc dữ liệu cho một nút của cây AA, các biến đổi hiệu chỉnh cây AA, . | CẤU TRÚC DỮ LIỆU CÂY AA Bùi Tiến Lên 01 01 2017 https tailieudientucntt Cây AA 30 70 15 50 60 85 5 10 20 35 40 55 65 80 90 Hình 1 Cây có liên kết ngang Spring 2017 Data structure amp Algorithm https tailieudientucntt 2 Cây AA cont. Định nghĩa 1 I Liên kết thông thường link là liên kết giữa một nút cha và một nút con có mức nhỏ hơn một đơn vị I Liên kết ngang horizontal link là liên kết giữa một nút con cha và một nút ở cùng một mức Spring 2017 Data structure amp Algorithm https tailieudientucntt 3 Cây AA cont. Định nghĩa 2 I Mức Level của nút lá là 1 I Mức Level của nút không có con trái là 1 I Mức Level của nút có con trái là là mức của con trái cộng với một Lưu ý I Mức của một nút trong cây AA không phải là mức của cây tổng quát. Đây là một định nghĩa mới. I Về mặt thể hiện bằng hình vẽ các nút có cùng một mức sẽ cùng một hàng khi vẽ ra. I Các mũi tên hướng qua trái chỉ đến nút con trái I Các mũi tên hướng qua phải chỉ đến nút con phải Spring 2017 Data structure amp Algorithm https tailieudientucntt 4 Cây AA cont. Định nghĩa 3 Cây AA Arne Andersson Tree là một cây nhị phân tìm kiếm trong đó I Chỉ có liên kết ngang phải I Không có hai liên kết ngang phải liên tiếp nhau I Mọi nút có mức lớn hơn 1 sẽ có 2 nút con I Nếu một nút không có liên kết ngang phải thì 2 nút con của nó ở cùng mức Spring 2017 Data structure amp Algorithm https tailieudientucntt 5 Cây AA cont. Nhận xét Từ định nghĩa về cây AA ta thấy cây AA sẽ có những tính chất sau I Mức của nút con trái luôn nhỏ hơn mức của nút cha một đơn vị I Mức của nút con phải bằng hay nhỏ hơn mức của cha một đơn vị I Cây AA chính là một trường hợp đặc biệt của cây đỏ đen Spring 2017 Data structure amp Algorithm https tailieudientucntt 6 Cấu trúc dữ liệu cho một nút của cây AA Cấu trúc lưu trữ cho một nút của cây AA 1 template 2 struct AANode 3 4 T data 5
