Cây AA (AA tree) là dạng cây cân bằng lưu trữ và truy xuất dữ liệu có thứ tự hiệu quả. Là biến thể của cây đỏ-đen (red-black tree), một cây tìm kiếm nhị phân hỗ trợ thêm/xóa hiệu quả. Khác với cây đỏ-đen, nút đỏ trên cây AA chỉ được thêm làm con phải (right subchild), không phải con trái. Điều này mô phỏng cây 2-3 thay vì 2-3-4, đơn giản hóa bảo trì.
Thuật toán bảo trì cây đỏ-đen cần xét 7 hình dạng khác nhau để cân bằng:
Cây AA chỉ cần xét 2 hình dạng nhờ quy tắc chặt: chỉ liên kết phải mới được đỏ:
Quay cân bằng (Balancing rotations)
Cây đỏ-đen cần 1 bit metadata/nút (màu), cây AA cần O(log(log(N))) bit metadata/nút dạng integer "level". Các bất biến cây AA:
- Mức (level) mọi nút lá = 1.
- Mức con trái = mức cha - 1.
- Mức con phải = mức cha hoặc mức cha - 1.
- Mức cháu phải < mức ông/bà.
- Mọi nút mức > 1 có 2 con.
Cân bằng lại cây AA đơn giản hơn cây đỏ-đen nhiều. Chỉ cần 2 thao tác: "skew" và "split". Skew: quay phải thay liên kết ngang trái bằng liên kết ngang phải. Split: quay trái + tăng level, thay 2+ liên kết ngang phải liên tiếp bằng ít hơn 2.
Hàm skew
input: nút t biểu diễn cây AA cần cân bằng
output: nút biểu diễn cây AA đã cân bằng
if nil(t) return nil
else if nil(left(t)) return t
else if level(left(t)) == level(t) then
// đổi con trỏ liên kết ngang trái
l = left(t)
left(t) := right(l)
right(l) := t
return l
else return t
Hàm split
input: nút t
output: nút cây AA đã cân bằng
if nil(t) return nil
else if nil(right(t)) or nil(right(right(t))) return t
else if level(t) == level(right(right(t))) then
// có 2 liên kết ngang phải. Nút giữa nâng cấp, trả về.
r = right(t)
right(t) := left(r)
left(r) := t
level(r) := level(r) + 1
return r
else return t
