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,. nội dung chi tiết. | 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 - Bùi Tiến Lên CẤU TRÚC DỮ LIỆU CÂY AA Bùi Tiến Lên 01/01/2017 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 & Algorithm 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 & Algorithm 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 & Algorithm 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 & Algorithm 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
