Aa tree

Báo Cáo Đề Tài:
AA TREE
Lớp: Tin 4 LA – KG
GVHD : Cô. Trần Thị Thủy Tiên

Nhóm thực hiện:
Nguyễn Thanh Ngân
Thái Lâm Ngọc Thi
Trần Thị Huỳnh Lê
Nguyễn Thị Thanh Hương
Nguyễn Minh Thư
Nội dung:
Định nghĩa
Các khái niệm cơ bản
1
2
3
Các thao tác cơ bản
4
Ví dụ minh họa
5
Đánh giá
1. Định nghĩa
A . Giới thiệu chung:
AA Tree được đưa ra bởi Arne Andersson và lấy theo tên ông.
AA Tree là một biến dạng của cây đỏ đen. Nó cũng là một cây nhị phân tìm kiếm nhưng khác với cây đỏ đen là nó chỉ cho phép có con phải màu đỏ.
Ngoài ra các nút sẽ được gắn một cấp độ(mức) xác định thay vì màu như cây đỏ đen.
Để đảm bảo cây cân bằng thì các nút phải tuân theo các quy tắc được đặt ra.
1. Định nghĩa:
AA tree là một cây nhị phân tìm kiếm (BST tuân thủ các quy tắc sau:
Liên kết ngang luôn hướng về bên phải.
Không có 2 liên kết ngang liên tiếp nhau.
Mọi nút có mức > 1 sẽ có 2 nút con.
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.
1. Định nghĩa:

Các quy tắc của AA Tree:
Các nút lá có mức bằng 1.
Mức của nút con trái luôn nhỏ hơn mức của nút cha.
Nút con phải có mức nhỏ hơn hoặc bằng nút cha.
Nút cháu phải có mức nhỏ hơn nút ông.
Mọi nút có mức lớn hơn 1 phải có 2 con.
1. Định nghĩa:
B. Minh họa:
30
70
85
50
60
90
80
65
55
35
40
15
5
10
20
Liên kết ngang
Liên kết con phải
Liên kết con phải
50
60
50
55
60
50
65
55
60
50
35
65
55
60
50
35
65
55
60
50
35
65
55
60
50
35
65
55
60
50
2. Các khái niệm cơ bản:
a.Mức của một nút
b.Liên kết ngang
c.Xoay phải (Skew)
d.Xoay trái(Split)
2. Các khái niệm cơ bản:
a. Mức của một nút:
Là số liên kết trái từ nút đó đến NULL
Mức của nút NULL là 0
Mức của nút lá là 1

Mức 0
Mức 1
C
E
D
B
A
B
B
D
B
E
D
B
E
D
B
E
D
B
C
E
D
C
E
D
2. Các khái niệm cơ bản:
b.Liên kết ngang:
Là liên kết giữa một nút con của nút đó
ở cùng một mức


C
E
D
B
A
Node con ở cùng mức
Node cha
2. Các khái niệm cơ bản:
c. Xoay Phải (Skew)




L là con trái của T nhưng cùng mức với T nên vi phạm quy tắc mức của nút con trái luôn nhỏ hơn nút cha.
Sau khi skew thì T trở thành con phải của L, cùng mức với L và các quy tắc được đảm bảo.
2. Các khái niệm cơ bản:
d. Xoay trái (Split):
X là cháu phải của nút T. X cùng mức với T nên vi phạm quy tắc nút cháu phải có mức nhỏ hơn nút ông.
Sau khi split thì T trở thành con trái của R, vẫn cùng mức cũ với X nhưng T và X là anh em nên các quy tắc vẫn được đảm bảo.
Chỉ có nút R là được tăng lên một mức.
2. Các khái niệm cơ bản:
Tính chất của AA tree:
* Mức của nút con trái luôn nhỏ hơn mức của nút cha 1 đơn vị
* Mức của nút con phải nhỏ hơn hay bằng mức của nút cha (nhưng không quá 1 đơn vị)
* Thêm một nút luôn thực hiện ở nút có mức bằng 1
3. Các thao tác cơ bản:
Việc tìm kiếm được thực hiện tuần tự giống như trong cây nhị phân tìm kiếm:
- Bắt đầu từ gốc.
- Duyệt cây theo kiểu top- down, nếu mức đó có nút con theo liên kết ngang bên phải thì duyệt theo liên kết ngang trước rồi đến các nút con ở mức thấp hơn.
a.Tìm một nút :
3. Các thao tác cơ bản:

Việc thêm một nút mới thực hiện như cây nhị phân.
Khi tìm được vị trí chèn ở nút NULL thì ta tạo một nút mới ở đó.
Sau đó kiểm tra trên đường đi xuống bắt đầu từ cha của nút đã chèn rồi đi ngược lên đến nút gốc:
Nếu nút cha cùng mức với nút con trái, thì skew.
Nếu nút đó có nút cháu phải cùng mức , thì split.
Lệnh skew luôn được thực hiện trước lệnh split.
b.Thêm một nút :
3. Các thao tác cơ bản:
Nút thêm vào bên trái sẽ tạo ra một liên kết ngang bên trái, khi đó sẽ vi phạm Skew.
b.Thêm một nút :
A
B
C
Nút thêm vào
B
A
A
B
C
C
Skew
Split
3. Các thao tác cơ bản:
Nút thêm vào bên phải nếu tạo ra 2 liên kết ngang bên phải liên tiếp thì thực hiện Split.
b.Thêm một nút :
A
B
C
B
C
A
Split
3. Các thao tác cơ bản:
Việc tìm vị trí nút xóa được thực hiện như cây nhị phân.
Tuy nhiên việc xóa sẽ đơn giản hơn vì nút xóa sẽ không thể xảy ra trường hợp chỉ có con trái.
Do đó ta chỉ cần xét trường hợp nút xóa không có con và có con bên phải (bao gồm cả TH có 2 con).
Nếu không có con thì xóa bình thường.
Nếu có con bên phải thì tìm phần tử thế mạng nhỏ nhất bên phải để xóa(phần tử này không có con trái nên nó là nút lá).
Như vậy, nút thực sự bị xóa đi luôn là nút lá.
c. Xóa một nút :
4. Ví dụ minh họa :
Tìm một nút.
Thêm một nút.
Xóa một nút.
4. Ví dụ minh họa :
70
85
50
60
90
80
65
55
35
40
15
5
10
20
45
Tìm 55
30
70
50
60
55
30
30
70
50
60
55
a.Tìm một nút :
4. Ví dụ minh họa :
30
70
85
50
60
90
80
65
55
35
40
15
5
10
20
45
Split
b.Thêm một nút :
4. Ví dụ minh họa :
30
70
85
50
60
90
80
65
55
15
5
10
20
30
40
35
45
Skew
b.Thêm một nút :
4. Ví dụ minh họa :
70
85
50
60
90
80
65
55
15
5
10
20
30
40
35
45
Skew
Split
50
50
Thêm 45 thành công
b.Thêm một nút :
4. Ví dụ minh họa :
4
10
1
6
8
12
2
5
3
7
9
11
13
Xóa 1
Giảm mức
2
Sau khi giảm mức tại 2
Giảm mức
4
10
c. Xóa một nút :
4. Ví dụ minh họa :
4
10
6
8
12
2
5
3
7
9
11
13
Skew
Sau khi giảm mức tại 4 và 10
6
c. Xóa một nút :
4. Ví dụ minh họa :
4
10
6
8
12
2
5
3
7
9
11
13
Skew
Sau khi Skew tại 10 lần 1
8
12
c. Xóa một nút :
4. Ví dụ minh họa :
4
10
6
8
12
2
5
3
7
9
11
13
Sau khi Skew tại 10 lần 2
Split
6
c. Xóa một nút :
4. Ví dụ minh họa :
4
10
6
8
12
2
5
3
7
9
11
13
Split
Sau khi Split tại 4
10
Xóa 1 thành công
c. Xóa một nút :
5. Đánh giá:
Độ phức tạp O(log2N)
Không cần lưu con trỏ đến nút cha.
Cài đặt đơn giản hơn Red – Black Tree