NỘI DUNG CHƯƠNG 5
1. Khái niệm cây – Biểu diễn cây
2. Cây nhị phân (Binary Tree)
1. Định nghĩa
2. Biểu diễn và các thao tác
3. Cây nhị phân tìm kiếm (Binary Searching Tree)
3. Cây cân bằng (Balanced Tree)
1. Định nghĩa – Cấu trúc dữ liệu
2. Các thao tác trên cây cân bằng
BÀI TẬP
40 trang |
Chia sẻ: phuongt97 | Lượt xem: 527 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng môn Cấu trúc dữ liệu - Chương 5: Cây (Tree), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 5:
CÂY (TREE)
189
190
NỘI DUNG CHƯƠNG 5
1. Khái niệm cây – Biểu diễn cây
2. Cây nhị phân (Binary Tree)
1. Định nghĩa
2. Biểu diễn và các thao tác
3. Cây nhị phân tìm kiếm (Binary Searching Tree)
3. Cây cân bằng (Balanced Tree)
1. Định nghĩa – Cấu trúc dữ liệu
2. Các thao tác trên cây cân bằng
BÀI TẬP
191
1.Khái niệm cây – Biểu diễn cây
1.1 Định nghĩa cây
1.2. Một số khái niệm liên quan
1.2.a. Bậc của 1 cây
1.2.b. Bậc của 1 nút
1.2.c. Nút gốc
1.2.d. Nút kết thúc
1.2.e. Nút trung gian
1.2.f. Mức của 1 nút
1.2.g. Chiều cao (chiều sâu) của 1 cây
1.2.h. Nút trước, nút sau của 1 nút
1.2.i. Nút cha, nút con của 1 nút
1.2.j. Chiều dài đường đi của 1 nút
1.2.k. Chiều dài đường đi của 1 cây
1.2.l. Rừng
1.Khái niệm cây – Biểu diễn cây
1.1 Định nghĩa cây
• Cây là một tập hợp các phần tử (nút) được tổ chức và có các
đặc điểm
• Hoặc là tập hợp rỗng (cây rỗng)
• Hoặc là tập hợp khác rỗng trong đó có 1 nút duy nhất làm nút gốc
(Root’s Node), các nút còn lại được phân thành các nhóm trong đó mỗi
nhóm là 1 cây con (Sub-Tree)
• Các cây con cũng có thể là tập rỗng hay khác rỗng trong đó
có 1 nút là gốc cây con.
192
193
1.Khái niệm cây – Biểu diễn cây
1.2. Một số khái niệm liên quan
1.2.a. Bậc của 1 nút
• Bậc của 1 nút (node’s degree) là số cây con của nút đó
1.2.b. Bậc của 1 cây
• Bậc của 1 cây (tree’s degree) là bậc lớn nhất của các
nút trong cây
• Cây có bậc N gọi là cây N-phân
1.2.c. Nút gốc
• Nút gốc (root’s tree) là nút không phải là nút gốc cây
con của bất kỳ 1 cây con nào khác trong cây (nút
không làm gốc cây con)
194
1.Khái niệm cây – Biểu diễn cây
1.2.d. Nút kết thúc
Nút kết thúc hay còn gọi nút lá (leaf’s node) là nút có bậc =
0 (nút không có nút cây con)
1.2.e. Nút trung gian
• Nút trung gian hay còn gọi nút giữa (interior’s node) là
nút không phải là nút gốc và cũng không phải nút kết
thúc (nút có bậc khác không và là nút gốc của cây con
nào đó trong cây)
1.2.f. Mức của 1 nút
• Mức của 1 nút (node’s level) bằng mức của nút gốc
cây con chứa nó +1.
• Mức của nút gốc = 1
195
1.Khái niệm cây – Biểu diễn cây
1.2. Một số khái niệm liên quan (tt)
1.2.g. Chiều cao (chiều sâu) của 1 cây
• Chiều cao (chiều sâu) của 1 cây (tree’s height | tree’s
depth) là mức cao nhất của 1 nút trong cây
1.2.h. Nút trước, nút sau của 1 nút
• Nút T được gọi là nút trước của 1 nút (ancestor’s node)
của nút S nếu cây con có gốc là T chứa cây con có gốc
là S. Khi đó S được gọi là nút sau của nút T
(descendant’s node)
1.2.e. Nút trung gian
• Nút trung gian hay còn gọi nút giữa (interior’s node) là
nút không phải là nút gốc và cũng không phải nút kết
thúc (nút có bậc khác không và là nút gốc của cây con
nào đó trong cây)
196
1.Khái niệm cây – Biểu diễn cây
1.2. Một số khái niệm liên quan (tt)
1.2.f. Mức của 1 nút
• Mức của 1 nút (node’s level) bằng mức của nút gốc
cây con chứa nó +1.
• Mức của nút gốc = 1
1.2.g. Chiều cao (chiều sâu) của 1 cây
• Chiều cao (chiều sâu) của 1 cây (tree’s height | tree’s
depth) là mức cao nhất của 1 nút trong cây
1.2.h. Nút trước, nút sau của 1 nút
• Nút T được gọi là nút trước của 1 nút (ancestor’s node)
của nút S nếu cây con có gốc là T chứa cây con có gốc
là S. Khi đó S được gọi là nút sau của nút T
(descendant’s node)
197
1.Khái niệm cây – Biểu diễn cây
1.2. Một số khái niệm liên quan (tt)
1.2.i. Nút cha, nút con của 1 nút
• Nút B được gọi là nút cha (parent’s node) của nút C
nếu nút B là nút trước của nút B và mức của nút C lớn
hơn mức của B là 1 mức. Khi đó nút C được gọi là nút
con (child’s node) của B
1.2.j. Chiều dài đường đi của 1 nút
• Chiều dài đường đi của 1 nút là số đỉnh (số nút) tính từ
nút gốc để đi đến nút đó.
• Chiều dài đường đi của nút gốc luôn = 1, chiều dài
đường đi tới 1 nút bằng chiều dài đường đi tới nút cha
của nó + 1
198
1.Khái niệm cây – Biểu diễn cây
1.2. Một số khái niệm liên quan (tt)
1.2.k. Chiều dài đường đi của 1 cây
• Chiều dài đường đi của 1 cây (path’s length of the tree)
là tổng tất cả các chiều dài đường đi của tất cả các nút
trên cây (chiều dài đường đi trong internal path’s
length).
• Tính chiều dài đường đi ngoài (external path’s length)
bằng cách mở rộng tất cả các nút của cây sao cho các
nút của cây có cùng bậc (thêm vào các nút giả) với bậc
của cây. Chiều dài đường đi ngoài bằng tổng chiều
1.2.l. Rừng.
• Rừng (forest) là tập hợp các cây.
• Khi cây mất gốc rừng
199
1.Khái niệm cây – Biểu diễn cây
1.3. Biểu diễn cây
• Dùng đồ thị, Dùng giản đồ tập hợp, Sử dụng dạng phân
cấp chỉ số
BIỂU DIỄN CÂY TRONG BỘ NHỚ MÁY TÍNH
• Để biểu diễn cây trong bộ nhớ máy tính dùng danh sách
liên kết.
• Để biểu diễn cây N-phân dùng danh sách có N mối liên kết
để quản lý N địa chỉ nút con.
• Cấu trúc dữ liệu của cây N-phân tương tự cấu trúc dữ liệu
đa liên kết.
const int N = 100;
typedef struct NTNode
{ T Key;
NTNode * SubNode[N];
}NTOneNode;
typedef struct NTOneNode * NTType;
Để quản lý cây, chỉ cần quản lý địa chỉ nút gốc NTType NTree;
2. Cây nhị phân (Binary Tree)
2.1. Định nghĩa
• Cây nhị phân là cây có bậc bằng 2 (bậc của nút tối đa bằng
2)
200
201
2. Cây nhị phân (Binary Tree)
2.2. Biểu diễn và các thao tác
• Để biểu diễn cây nhị phân trong bộ nhớ máy tính dùng
danh sách có 2 mối liên kết để quản lý địa chỉ 2 nút con
(cây con trái và cây con phải).
• Như vậy cấu trúc dữ liệu của cây nhị phân tương tự
cấu trúc dữ liệu của danh sách liên kết đôi nhưng cách
thức liên kết khác:
typedef struct BinTNode
{ T Key;
BinTNode * BinTLeft;
BinTNode * BinTRight;
}BinTOneNode;
typedef BinTOneNode * BinTType;
• Để quản lý cây nhị phân chỉ cần quản lý địa chỉ nút gốc
BinTType BinTree;
202
2. Cây nhị phân (Binary Tree)
2.2. Biểu diễn và các thao tác (tt)
Các thao tác trên cây nhị phân bao gồm:
a. Khởi tạo cây nhị phân
b. Tạo mới 1 nút
c. Thêm 1 nút vào cây nhị phân
d. Duyệt qua các nút trên cây nhị phân
e. Tính chiều cao của cây
f. Tính số nút của cây
g. Hủy 1 nút trên cây nhị phân
203
2. Cây nhị phân (Binary Tree)
2.2. a. Khởi tạo cây nhị phân
Khởi tạo cây nhịn phân: cho con trỏ quản lý địa chỉ nút gốc
về con trỏ NULL
BinTType BinTreeInitialize(BinTType & BTree)
{
BTree = NULL
return (BTree );
}
2. Cây nhị phân (Binary Tree)
2.2. b. Tạo mới 1 nút
Thuật toán
B1: BTNode = new BinTOneNode
B2: IF (BTNode == NULL)
Thực hiện BKT
B3: BTNode ->BinTLeft = NULL
B4: BTNode ->BinTRight = NULL
B5: BTNode -> Key = NewData
BKT: Kết thúc
204
205
2. Cây nhị phân (Binary Tree)
2.2. b. Tạo mới 1 nút (tt)
Cài đặt thuật toán trong C++
BinTType BinTreeCreateNode(T NewData)
{
BinTType BTnode = new BinTOneNode;
if (BTnode != NULL)
{
BTnode-> BinTLeft = NULL;
BTnode-> BinTRight = NULL;
BTnode-> Key = NewData;
}
return (BTnode);
}
206
2. Cây nhị phân (Binary Tree)
2.2. c. Thêm 1 nút vào cây nhị phân (Thêm trái nhất) – Thuật toán
B1: NewNode = BinTreeCreateNode(NewData)
B2: IF (NewNode == NULL)
Thực hiện BKT
B3: IF (BinTree == NULL)
B3.1: BinTree = NewNode
B3.2: Thực hiện BKT
B4: Lnode = BinTree
B5: IF (Lnode->BinTLeft == NULL)
B5.1: Lnode-> BinTLeft = NewNode
B5.2: Thực hiện BKT
B6: Lnode = Lnode ->BinTLeft
B7: Lặp lại B5
BKT: Kết thúc
207
2. Cây nhị phân (Binary Tree)
2.2. c. Thêm 1 nút vào cây nhị phân (Thêm trái nhất)
Cài đặt thuật toán bằng C++
BinTType BinTreeAddLeft (BinTType &BTTree, T NewData)
{
BinTType NewNode = BinTreeCreateNode (NewData);
if (NewNode == NULL)
return (NewNode);
if (BTTree == NULL)
BTTree = NewNode;
else
{
BinTType Lnode = BTTree;
while (Lnode->BinTLeft != NULL)
Lnode = Lnode->BinTLeft;
Lnode->BinTLeft = NewNode;
}
return (NewNode);
}
208
2. Cây nhị phân (Binary Tree)
2.2. c. Thêm 1 nút vào cây nhị phân (Thêm phải nhất)-Thuật toán
B1: NewNode = BinTreeCreateNode(NewData)
B2: IF (NewNode == NULL)
Thực hiện BKT
B3: IF (BinTree == NULL)
B3.1: BinTree = NewNode
B3.2: Thực hiện BKT
B4: Rnode = BinTree
B5: IF (Rnode->BinTRight == NULL)
B5.1: Rnode->BinTRight = NewNode
B5.2: Thực hiện BKT
B6: Rnode = Rnode ->BinTRight
B7: Lặp lại B5
BKT: Kết thúc
209
2. Cây nhị phân (Binary Tree)
2.2. c. Thêm 1 nút vào cây nhị phân (Thêm phải nhất)
Cài đặt thuật toán bằng C++
BinTType BinTreeAddRight (BinTType &BTTree, T NewData)
{
BinTType NewNode = BinTreeCreateNode (NewData);
if (NewNode == NULL)
return (NewNode);
if (BTTree == NULL)
BTTree = NewNode;
else
{
BinTType Rnode = BTTree;
while (Rnode->BinTRight != NULL)
Rnode = Rnode->BinTRight;
Rnode->BinTRight = NewNode;
}
return (NewNode);
}
210
2. Cây nhị phân (Binary Tree)
2.2. d. Duyệt qua các nút trên cây nhị phân
• Duyệt theo thứ tự nút gốc trước (Preoder): nút gốc được duyệt
trước, sau đó mới duyệt đến 2 nút con. Có 2 cách:
• Duyệt nút gốc, duyệt cây con bên trái, duyệt cây con bên phải (Root -
Left - Right)
• Duyệt nút gốc, duyệt cây con bên phải, duyệt cây con bên trái (Root -
Right - Left)
• Duyệt theo thứ tự nút gốc giữa (Inoder): duyệt 1 trong 2 cây con
trước rồi duyệt nút gốc sau đó mới duyệt cây con còn lại. Có 2 cách:
• Duyệt cây con bên trái, duyệt nút gốc, duyệt cây con bên phải (Left -
Root - Right)
• Duyệt cây con bên phải, duyệt nút gốc, duyệt cây con bên trái (Right -
Root - Left)
• Duyệt theo thứ tự nút gốc sau (Postoder): Nút gốc sẽ được duyệt
sau cùng sau khi duyệt 2 cây con.
• Duyệt cây con bên trái, duyệt cây con bên phải, duyệt nút gốc(Left –
Right - Root)
• Duyệt cây con bên phải, duyệt cây con bên trái, duyệt nút gốc(Right -
Left- Root )
211
2. Cây nhị phân (Binary Tree)
2.2. d. Duyệt qua các nút trên cây nhị phân – (Left-Root-
Right)
Thuật toán
Hàm duyệt đệ quy: LRootR
B1: CurrNode = BinTree
B2: IF (CurrNode == NULL)
Thực hiện BKT
B3: LRootR(BinTree->BinTLeft)
B4: Process (CurrNode->Key)
B5: LRootR(BinTree->BinTRight)
BKT: Kết thúc
212
2. Cây nhị phân (Binary Tree)
2.2. d. Duyệt qua các nút trên cây nhị phân – (Left-Root-
Right)
Cài đặt thuật toán trong C++
void BinTreeLRootRTravelling(BinTType BTTree)
{
if (BTTree == NULL)
return;
BinTreeLRootRTraveling(BTTree->BinTLeft);
Process (BTTree->Key);
BinTreeLRootRTraveling(BTTree->BinTRight);
return;
}
213
2. Cây nhị phân (Binary Tree)
2.2. e. Tính chiều cao của cây
B1: IF (BinTree == NULL)
B1.1: TH = 0
B1.2: Thực hiện BKT
B2: THL = TH(BinTree->BinTLeft)
B3: THR = TH(BinTree->BinTRight)
B4: IF(THL > THR)
TH = THL + 1
B5: ELSE
TH = THR + 1
BKT: Kết thúc
int BinTreeHeight (BinTType BTree)
{
if (BTree == NULL)
return (0);
int HTL = BinTreeHeight(BTree -> BinTLeft);
int HTR = BinTreeHeight(BTree -> BinTRight);
if (HTL > HTR)
return (HTL +1)
return (HTR +1);
}
214
2. Cây nhị phân (Binary Tree)
2.2. f. Tính số nút của cây
Tính số nút của cây tương tự tính chiều cao của cây, số nút của cây con + 1.
Dùng cách tính đệ quy số nút của cây con
B1: IF (BinTree == NULL)
B1.1: NN = 0
B1.2: Thực hiện BKT
B2: NNL = NN(BinTree->BinTLeft)
B3: NNR = NN(BinTree->BinTRight)
B4: NN = NNR + NNL + 1
BKT: Kết thúc
int BinTreeNumNode (BinTType BTree)
{
if (BTree == NULL)
return (0);
int NNL = BinTreeNumNode(BTree -> BinTLeft);
int NNR = BinTreeNumNode(BTree -> BinTRight);
return (NNL + NNR +1);
}
215
2. Cây nhị phân (Binary Tree)
2.2. g. Hủy 1 nút trên cây nhị phân
• Việc hủy 1 nút trong cây có thể làm cho cây trở thành rừng.
• Nếu tiến hành hủy các nút lá không có vấn đề gì xảy ra.
• Nếu hủy 1 nút không phải là nút lá cần phải chuyển các nút
con của nút cần hủy qua các nút khác rồi mới tiến hành hủy.
• Nếu nút cần hủy chỉ có 1 nút gốc cây con thì chuyển nút gốc
của cây con này thành nút gốc của cây con cha của nút cần
hủy.
• Trong trường hợp nút cần hủy có 2 nút gốc cây con, thì phải
chuyển 2 nút gốc cây con này thành nút gốc cây con của nút
khác. Tuỳ từng trường hợp cụ thể mà đưa ra cách chọn phù
hợp.
216
2. Cây nhị phân (Binary Tree)
2.3. Cây nhị phân tìm kiếm (Binary Searching Tree)
2.3.1. Khái niệm – Cấu trúc dữ liệu
• Cây nhị phân tìm kiếm là cây nhị phân có thành phần khóa của
mọi nút lớn hơn tất cả thành phần khóa của tất cả các nút trong
cây con trái của nó và nhỏ hơn thành phần khóa của tất cả các nút
trong cây con phải của nó.
• Cấu trúc dữ liệu của cây nhị phân tìm kiếm là cấu trúc dữ liệu biểu
diễn cây nhị phân nói chung.
typedef struct BSTNode
{ T Key;
BSTNode * BSTLeft;
BSTNode * BSTRight;
} BSTOneNode;
typedef BSTOneNode * BSTType;
• Để quản lý các cây nhị phân tìm kiếm chúng ta cần quản lý địa chỉ
nút gốc của cây: BSTType BSTree;
217
2. Cây nhị phân (Binary Tree)
2.3. Cây nhị phân tìm kiếm (Binary Searching Tree)
2.3.1. Khái niệm – Cấu trúc dữ liệu (tt)
• Khóa nhận diện của cây tìm kiếm đôi một khác nhau (không
có hiện tượng trùng khóa)
• Nếu cần quản lý các nút có khóa trùng nhau trong cây nhị
phân tìm kiếm thì có thể mở rộng cấu trúc bằng cách thêm
thành phần Count ghi nhận số khóa trùng:
typedef struct BSENode
{ T Key;
int Count;
BSENode * BSELeft;
BSENode * BSERight;
} BSEOneNode;
typedef BSEOneNode * BSEType;
• Nút bên trái nhất là nút có giá trị khóa nhận diện nhỏ nhất và
nút phải nhất là nút có giá trị khóa nhận diện lớn nhất.
• Trong BST, duyệt cây Left-Root-Right là thứ tự duyệt theo sự
tăng dần của khóa nhận diện.
218
2. Cây nhị phân (Binary Tree)
2.3. Cây nhị phân tìm kiếm (Binary Searching Tree)
2.3.2. Các thao tác trên cây nhị phân tìm kiếm
2.3.2.a. Tìm kiếm trên cây
2.3.2.b. Thêm vào một nút trên cây
2.3.2.c. Loại bỏ 1 nút trên cây
2.3.2.d. Hủy toàn bộ cây
219
2. Cây nhị phân (Binary Tree)
2.3.2.a. Tìm kiếm trên cây nhị phân tìm kiếm BST
• Tìm kiếm trong cây có tồn tại nút có khóa (Key) là SearchData
hay không.
• Dùng thuật toán tìm kiếm nhị phân vì do đặc điểm của cây nhị
phân tìm kiếm thì tại 1 nút nểu Key của nút này khác với
SearchData:
• Nếu SearchData > Key của nút tìm ở cây con bên phải
• Nếu SearchData < Key của nút tìm ở cây con bên trái
B1: CurrNode = BSTree
B2: IF (CurrNode == NULL or CurrNode->Key == SearchData)
Thực hiện BKT
B3: IF (CurrNode ->Key > SearchData) // tìm ở cây con bên trái
CurrNode = CurrNode->BSTree->BSTLeft
B4: ELSE // tìm ở cây con bên phải
CurrNode = CurrNode->BSTree->BSTRight
B5: Lặp lại B2
BKT: Kết thúc
220
2. Cây nhị phân (Binary Tree)
2.3.2.a. Tìm kiếm trên cây nhị phân tìm kiếm BST (tt)
Cài đặt thuật toán
BSTType BSTSearching (BSTType BSTree, T SearchData)
{
BSTType CurrNode = BSTree;
while (CurrNode !=NULL & CurrNode->Key != SeachData)
{
if (CurrNode ->Key > SearchData)
CurrNode = CurrNode ->BSTLeft;
else
CurrNode = CurrNode ->BSTRight;
}
return (CurrNode);
}
221
2. Cây nhị phân (Binary Tree)
2.3.2.b. Thêm vào một nút trên cây nhị phân tìm kiếm
• Giả sử thêm vào 1 nút có thành phần dữ liệu là
NewData vào cây nhị phân tìm kiếm sao cho sau khi
thêm, cây vẫn là cây nhị phân tìm kiếm.
• Bao gồm các thao tác tìm kiếm vị trí thêm và thêm nút
vào cây.
• Thao tác chỉ thêm được nếu không có hiện tượng
trùng khóa, do đó nếu NewData trùng với Key của 1
trong các nút trong cây thì không thực hiện thêm.
222
2. Cây nhị phân (Binary Tree)
2.3.2.b. Thêm vào một nút trên cây nhị phân tìm kiếm (tt)
B1: NewNode = BinTreeCreateNode(NewData)
B2: IF(NewNode == NULL)
Thực hiện BKT
B3: IF (BSTree == NULL)
B3.1: BSTree = NewNode
B3.2: Thực hiện BKT
B4: CurrNode = BSTree
B5: IF (CurrNode == NULL)
Thực hiện BKT
B6: IF (CurrNode->Key > NewData)
B6.1: AddLeft = True
B6.2: If (CurrNode->BSTLeft != NULL)
CurrNode = CurrNode->BSTLeft
B7: IF (CurrNode->Key < NewData)
B6.1: AddLeft = False
B6.2: If (CurrNode->BSTRight != NULL)
CurrNode = CurrNode->BSTRight
B8: Lặp lại B5
B9: IF (AddLeft == True)
CurrNode = CurrNode->BSTLeft
B10: ELSE
CurrNode = CurrNode->BSTRight
BKT: Kết thúc
223
2. Cây nhị phân (Binary Tree)
2.3.2.b. Thêm vào một nút trên cây nhị phân tìm kiếm (tt)
BSTType BSTAddNode (BSTType &BSTree, T NewData)
{ BSTType NewNode = BinTreeCreateNode(NewData);
if (NewNode == NULL) return (NewNode);
if (BSTree == NULL) BSTree = NewNode;
else
{ BSTType CurrNode = BSTree;
int AddLeft = 1;
while (CurrNode->Key != NewData) // khong them neu trung Key
{ if (CurrNode->Key > NewData) // them o cay con ben trai
{ AddLeft = 1;
if (CurrNode->BSTLeft != NULL)
CurrNode = CurrNode->BSTLeft;
else break;
}
else // them o cay con ben phai
{ AddLeft = 0;
if (CurrNode->BSTRight != NULL)
CurrNode = CurrNode->BSTRight;
else break;
}
}
if (AddLeft == 1) CurrNode->BSTLeft = NewNode;
else CurrNode->BSTRight = NewNode;
}
return (NewNode)
}
224
2. Cây nhị phân (Binary Tree)
2.3.2.d. Hủy toàn bộ cây
Thao tác chỉ đơn giản là việc thực hiện nhiều lần thao tác hủy một
nút trên cây nhị phân tìm kiếm cho đến khi cây trở thành rỗng.
Hàm thực hiện việc hủy tất cả các nút trong cây nhị phân tìm kiếm
BSTree.
void BSTDelete(BSTType &BSTree)
{
BSTType DelNode = BSTree;
while (BSTDeleteNodeTRS(BSTree, DelNode->Key) == 1)
DelNode = BSTree;
return;
}
225
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.
226
3. Cây cân bằng (Balanced Tree)
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;
227
3. Cây cân bằng (Balanced Tree)
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 <= Bal <= 1 thì cây là cây cân bằng. Phạm vi từ -1
1 là phạm vi cho phép của chỉ số cân bằng Bal
• Nếu Bal = 0: cây con trái & cây con phải đều nhau
• Nếu Bal = -1: cây con trái nhỏ hơn cây con phải (lệch phải)
• Nếu Bal = +1: cây con trái nhỏ lớn cây con phải (lệch trái)
228
BÀI TẬP
Bài tập trang 239, 240, 241 giáo trình “Cấu trúc dữ liệu”
Các file đính kèm theo tài liệu này:
- bai_giang_mon_cau_truc_du_lieu_chuong_5_cay_tree.pdf