Cây cân bằng

Chia sẻ: Nguyen Ha | Ngày: | Loại File: PDF | Số trang:37

Thêm vào BST

Báo xấu

86
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cấu trúc dữ liệu Cây cân bằng tương đối: Là cây nhị phân thỏa mãn điều kiện là đối với mọi nút của cây thì chiều cao của cây con trái và chiều cao của cây con phải của nút đó hơn kém nhau không quá 1 (theo định nghĩa của Adelson-Velskii và Landis). Cây cân bằng tương đối còn gọi là cây AVL (AVL Tree).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cây cân bằng

3. Cây cân bằng (Balanced Tree) 3.1. Định nghĩa – Cấu trúc dữ liệu  Cây cân bằng tương đối:  Là cây nhị phân thỏa mãn điều kiện là đối với mọi nút của cây thì chiều cao của cây con trái và chiều cao của cây con phải của nút đó hơn kém nhau không quá 1 (theo định nghĩa của Adelson-Velskii và Landis).  Cây cân bằng tương đối còn gọi là cây AVL (AVL Tree).  Cây cân bằng hoàn toàn:  Là cây nhị phân thỏa mãn điều kiện là đối với mọi nút của cây thì số nút của cây con trái và số nút của cây con phải của nút đó hơn kém nhau không quá 1.  Cây nhị phân cân bằng hoàn toàn là cây nhị phân cân bằng tương đối. 1
Ví dụ: AVL Tree AVL Tree 2
3.1. Định nghĩa – Cấu trúc dữ liệu (tt)  Để ghi nhận mức độ cân bằng tại mỗi nút gốc cây con, dùng thêm thành phần Bal trong cấu trúc dữ liệu của mỗi nút. typedef struct BALNode { T Key; int Bal; BALNode *BALLeft; BALNode *BALRight; }BALOneNode; typedef BALOneNode * BALType;  Để quản lý cây cân bằng, chỉ cần quản lý địa chỉ nút gốc của cây BALType BALTree; 3
3.1. Định nghĩa – Cấu trúc dữ liệu (tt)  Giá trị chỉ số cân bằng Bal tại 1 nút gốc của cây con trong cây cân bằng tương đối bằng hiệu số giữa chiều cao cây con trái và chiều cao cây con phải của nút đó.  Giá trị chỉ số cân bằng Bal tại 1 nút gốc của cây con trong cây cân bằng hoàn toàn = hiệu số giữa số nút cây con trái và số nút cây con phải của nút đó.  Nếu tại mọi nút trong cây nhị phân mà thỏa mãn điều kiện -1
3.2. Các thao tác trên cây cân bằng Các thao tác trên cây cân bằng áp dụng cho cây nhị phân tìm kiếm cân bằng tương đối. 3.2.a Thêm 1 nút vào cây cân bằng 3.2.b. Hủy một nút khỏi cây cân bằng 3.2.a Thêm 1 nút vào cây cân bằng  Thêm một nút NewNode có thành phần dữ liệu là NewData vào trong cây cân bằng BALTree sao cho sau khi thêm BALTree vẫn là một cây cân bằng.  Để thực hiện điều này cần tìm kiếm vị trí của nút cần thêm là nút con trái hoặc nút con phải của một nút PrNewNode tương tự như trong cây nhị phân tìm kiếm.  Sau khi thêm NewNode vào cây con trái hoặc cây con phải của PrNewNode thì chỉ số cân bằng của các nút từ PrNewNode trở về các nút trước sẽ bị thay đổi dây chuyền và chúng ta phải lần ngược từ 5
3.2.a Thêm 1 nút vào cây cân bằng  Nếu phát hiện tại một nút AncestorNode có sự thay đổi vượt quá phạm vi cho phép (bằng –2 hoặc +2) thì tiến hành cân bằng lại cây ngay tại nút AncestorNode này.  Việc cân bằng lại cây tại nút AncestorNode được tiến hành cụ thể theo các trường hợp như sau: Trường hợp 1: Nếu AncestorNode->Bal = -2:  AncRL có chiều cao là h và AncRR có chiều cao là h+1 (AncR->Bal = -1)  AncRL và AncRR đều có chiều cao là h+1 (AncR->Bal = 0)  AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->Bal = 1) 6
3.2.a Thêm 1 nút vào cây cân bằng  Nếu phát hiện tại một nút AncestorNode có sự thay đổi vượt quá phạm vi cho phép (bằng –2 hoặc +2) thì chúng ta tiến hành cân bằng lại cây ngay tại nút AncestorNode này.  Việc cân bằng lại cây tại nút AncestorNode được tiến hành cụ thể theo các trường hợp như sau: Trường hợp 1: Nếu AncestorNode->Bal = -2:  AncRL có chiều cao là h và AncRR có chiều cao là h+1 (AncR->Bal = -1)  AncRL và AncRR đều có chiều cao là h+1 (AncR->Bal = 0)  AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->Bal = 1) 7
3.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2: (lệch phải) Gọi: AncL = AncestorNode->BAL_Left AncR = AncestorNode->BAL_Right =>AncL có chiều cao là h và AncR có chiều cao là h+2 (h 0) =>Có ít nhất 1 cây con của AncR có chiều cao là h+1 Gọi: AncRL = AncR->BAL_Left AncRR = AncR->BAL_Right 8
3.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2: a1) AncRL có chiều cao là h và AncRR có chiều cao là h+1 (AncR->Bal = -1) Để cân bằng lại AncestorNode, thực hiện việc  quay đơn cây con phải AncR của nút này lên thành nút gốc;  chuyển AncestorNode thành nút con trái của nút gốc và AncestorNode có hai cây con là AncL và AncRL (BAL_Right Rotation). Cây con AncestorNode sau khi quay cây con phải AncR sẽ là một cây cân bằng. 9
3.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2: a1) AncRL có chiều cao là h và AncRR có chiều cao là h+1 (AncR->Bal = -1) 10
Ví dụ: Việc thêm nút có Key = 50 vào cây nhị phân tìm kiếm cân bằng sau đây sẽ làm cho cây mất cân bằng và chúng ta phải cân bằng lại theo trường hợp này: trở thành nút gốc trở thành nút phải của 19 11
 Thực hiện quay cây con phải của BALTree, cây nhị phân tìm kiếm sau khi quay trở thành cây nhị phân tìm kiếm cân bằng như sau: 12
3.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2: b1) AncRL và AncRR đều có chiều cao là h+1 (AncR->Bal = 0) 13
 Vd 1.b: 40 25 25 44 19 40 19 32 50 35 44 35 32 50 14
3.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2: c1) AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->Bal = 1) Để cân bằng lại AncestorNode thực hiện việc quay kép: quay cây con trái AncRL và quay cây con phải AncR (Double Rotation). Việc quay được tiến hành: Gọi: AncRLL = AncRL->BAL_Left AncRLR = AncRL->BAL_Right => AncRLL và AncRLR có chiều cao tối đa là h => Cây con có nút gốc AncestorNode có thể ở vào một trong ba dạng:  AncRLL có chiều cao là h và AncRLR có chiều cao là h-1 (AncRL->Bal =1; h >= 1)  AncRLL có chiều cao là h-1 và AncRLR có chiều cao là h (AncRL->Bal =-1; h >= 1)  Cả AncRLL và AncRLR đều có chiều cao là h (AncRL->Bal =0; h >= 0) 15
3.2.a (tt) Trường hợp 1: Nếu AncestorNode->Bal = -2: c1) AncRL có chiều cao là h+1 và AncRR có chiều cao là h (AncR->Bal = 1)  AncRLL có chiều cao là h và AncRLR có chiều cao là h-1 (AncRL->Bal =1; h >=1) 16
Ví dụ: Thêm nút có Key = 27 vào cây nhị phân tìm kiếm cân bằng, thực hiện cân bằng lại như 17
 Thực hiện quay đơn cây con trái của BALTree->BAL_Right cây nhị phân tìm kiếm sau khi quay trở thành cây nhị phân tìm kiếm như sau: 18
 Thực hiện quay đơn cây con phải của BALTree cây nhị phân tìm kiếm sau khi quay trở thành cây nhị phân tìm kiếm cân bằng như sau: 19
3.2.a Thêm 1 nút vào cây cân bằng Trường hợp 2: Nếu AncestorNode->Bal = 2:  Cũng tương tự như trường hợp 1, thực hiện quay đơn hoặc quay kép các nhánh phía ngược lại Gọi: AncL = AncestorNode->BAL_Left AncR = AncestorNode->BAL_Right => AncL có chiều cao là h+2 và AncR có chiều cao là h (h 0) =>Có ít nhất 1 cây con của AncL có chiều cao là h+1 Gọi: AncLL = AncL->BAL_Left AncLR = AncL->BAL_Right Cây con có nút gốc AncestorNode có thể ở vào một trong ba dạng sau:  AncLL có chiều cao là h+1 và AncLR có chiều cao là h (AncL- >Bal = 1)  AncLL và AncLR đều có chiều cao là h+1 (AncL->Bal = 0)  AncLL có chiều cao là h và AncLR có chiều cao là h+1 (AncL- >Bal = -1) 20