Cấu trúc cây (Tree)
C
C
ấ
ấ
u tr
u tr
ú
ú
c cây (Tree)
c cây (Tree)
Chương 6
Cây nhiều nhánh
4
Các khái niệm cơ bản
1
Cây nhị phân tìm kiếm
2
Cây nhị phân cân bằng
3
N
N
ộ
ộ
i dung
i dung
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C

6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Ví dụ: bài toán đưa thư
 Có một bức thư cần chuyển đến địa chỉ
“Nguyễn Văn A, 10 Huỳnh Văn Nghệ, Biên hoà, Đồng
Nai, Việt nam”
 Trên thế giới hiện có khoảng 8 tỷ người
 Làm thế nào để tìm ra người A nhanh nhất?
 Dùng cấu trúc mảng ??
 Dùng danh sách liên kết ??
C
C
á
á
c kh
c kh
á
á
i ni
i ni
ệ
ệ
m cơ b

m cơ b
ả
ả
n
n
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á
c kh
c kh
á
á
i ni
i ni
ệ

ệ
m cơ b
m cơ b
ả
ả
n
n
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Ví dụ: cây thư mục windows
C
C
á
á
c kh
c kh
á
á

i ni
i ni
ệ
ệ
m cơ b
m cơ b
ả
ả
n
n
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Ví dụ: cây biểu thức (a+b)/(c-d)
C
C
á
á
c kh

c kh
á
á
i ni
i ni
ệ
ệ
m cơ b
m cơ b
ả
ả
n
n
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Ví dụ: cây quyết định
C
C

á
á
c kh
c kh
á
á
i ni
i ni
ệ
ệ
m cơ b
m cơ b
ả
ả
n
n
Nhiệt độ
Có
Đau đầu
Bình thường
Cao
Rất cao
Đau đầu
không
không
Có không
có
{e2}
không
{e5}

có
{e3}
không
{e6}
{e1, e4}
{e2, e5}
{e3,e6}
Đau đầu Nhiệt độ Cúm
e1 Có Bình thường Không
e2 Có Cao Có
e3 Có Rất cao Có
e4 Không Bình thường Không
e5 Không Cao Không
e6 Không Rất cao Không
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Định nghĩa
 Một cây <T> (Tree) là:

 Một tập các phần tử, gọi là các nút (Node):
p1,p2,…,pN
 Nếu N=0, cây <T> gọi là cây rỗng (NULL)
 Nếu N>0:
• Tồn tại duy nhất 1 nút pk gọi là gốc của cây
• Các nút còn lại được chia thành m tập không giao nhau: T1,
T2, …, Tm
• Mỗi <Ti> là 1 cây con của cây <T>
C
C
á
á
c kh
c kh
á
á
i ni
i ni
ệ
ệ
m cơ b
m cơ b
ả
ả
n
n
3/11/2010
www.lhu.edu.vn
Chương
Chương

6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Ví dụ: cây nhiều nhánh
C
C
á
á
c kh
c kh
á
á
i ni
i ni
ệ
ệ
m cơ b
m cơ b
ả
ả
n
n
3/11/2010

www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Nút (Node): là 1 phần tử trong cây. Mỗi nút có
thể chứa 1 dữ liệu bất kỳ
 Nhánh (Branch): là đoạn nối giữa 2 nút
 Nút cha (Parent node)
 Nút con (Child node)
 Nút anh em (Sibling nodes): là những nút có
cùng nút cha
C
C
á
á
c kh
c kh
á
á
i ni
i ni

ệ
ệ
m cơ b
m cơ b
ả
ả
n
n
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Bậc của 1 nút pi: là số nút con của pi
 Ví dụ trên : Bậc (a) = 4; Bậc (j) = 3; Bậc (g) = 2;
Bậc (k) = 1; Bậc (c) = 0
 Nút gốc (Root node): nút không có nút cha
 Nút lá (Leaf node, hay nút ngoài – External
node): là nút có bậc = 0 (không có nút con)
 Nút nội (Internal node): là nút có nút cha và có
nút con

 Cây con (Subtree)
C
C
á
á
c kh
c kh
á
á
i ni
i ni
ệ
ệ
m cơ b
m cơ b
ả
ả
n
n
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú

ú
c cây
c cây
 Bậc của cây: là bậc lớn nhất của các nút trong
cây
 Bậc (<T>) = max {bậc (pi) / pi Î <T>}
 Bậc của cây <T> ?
 Đường đi (Path) giữa nút pi đến nút pj: là dãy
các nút liên tiếp từ pi đến pj sao cho giữa hai nút
kề nhau đều có nhánh
 Path(a, d) ?
C
C
á
á
c kh
c kh
á
á
i ni
i ni
ệ
ệ
m cơ b
m cơ b
ả
ả
n
n
3/11/2010

www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Mức (Level):
 Mức (p) = 0 nếu p = root
 Mức (p) = 1 + Mức (Cha (p)) nếu p!=root
 Chiều cao của cây (Height - hT): đường đi dài
nhất từ nút gốc đến nút lá
 hT = max {Path(root, pi) / pi là nút lá Î <T>}
C
C
á
á
c kh
c kh
á
á
i ni
i ni
ệ

ệ
m cơ b
m cơ b
ả
ả
n
n
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á
c kh
c kh
á
á
i ni

i ni
ệ
ệ
m cơ b
m cơ b
ả
ả
n
n
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á
c kh
c kh
á

á
i ni
i ni
ệ
ệ
m cơ b
m cơ b
ả
ả
n
n
 Cây đầy đủ (Full tree): là 1 cây thoả
• Tất cả các nút lá đều nằm trên cùng 1 mức
• Tất cả những nút khác có cùng bậc với cây
• Mức h của cây đầy đủ bậc d có dh nút
VD. mức h=2 của cây bậc 3 có bao nhiêu nút ?
• h mức đầu tiên của cây đầy đủ bậc d có số nút là:
1 + d + d
2
+ d
3
+ … + d
h-1
= (d
h
- 1)/(d – 1)
3 mức đầu tiên của cây đầy đủ bậc 3 có bao nhiêu nút ?
3/11/2010
www.lhu.edu.vn
Chương

Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á
c kh
c kh
á
á
i ni
i ni
ệ
ệ
m cơ b
m cơ b
ả
ả
n
n
 Cây hoàn chỉnh (Complete tree) với h mức:

là 1 cây thoả các điều kiện
• Những nút từ mức 0 đến mức h-1 đều đầy đủ
• Những nút ở mức h được thêm vào cây từ
trái sang phải
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân
phân
 Cây nhị phân là cây có bậc = 2
 Độ cao của cây nhị phân có N nút:
• hT(max) = N
• hT(min) = [logN] + 1
3/11/2010
www.lhu.edu.vn

Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân
phân
 Cấu trúc lưu trữ dùng mảng
Định nghĩa các cấu trúc dữ liệu
typedef struct NODE
{
int Data;
int Left; // chỉ số nút con trái
int Right; // chỉ số nút con phải
} NODETYPE; // cấu trúc 1 node
// cây nhị phân có N nút
NODETYPE tree[N];
3/11/2010
www.lhu.edu.vn

Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân
phân
 Cấu trúc lưu trữ dùng con trỏ
Định nghĩa các cấu trúc dữ liệu
typedef struct NODE
{ int Data;
NODE *pLeft; // con trỏ đến nút con trái
NODE *pRight; // con trỏ đến nút con phải
} NODETYPE; // binary tree node
typedef struct BIN_TREE
{ int Count; // Số nút trong cây
NODETYPE *pRoot; // con trỏ đến nút gốc
}; // binary tree
3/11/2010

www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân
phân
 Cấu trúc lưu trữ dùng con trỏ
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr

ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân
phân
 Có 3 cách duyệt cây:
• Duyệt gốc trước (Pre-Order) NLR
• Duyệt gốc giữa (In-Order) LNR
• Duyệt gốc sau (Post-Order) LRN
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh

ị
ị
phân
phân
 Duyệt gốc trước (Pre-Order) NLR
void NLR(const NODETYPE *pCurr)
{
if (pCurr==NULL) return;
“Xử lý nút gốc pCurr”
NLR(pCurr->pLeft);
NLR(pCurr->pRight);
}
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị

phân
phân
 Duyệt gốc giữa (In-Order) LNR
void LNR(const NODETYPE *pCurr)
{
if (pCurr==NULL) return;
LNR(pCurr->pLeft);
“Xử lý nút gốc pCurr”
LNR(pCurr->pRight);
}
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân
phân

 Duyệt gốc sau (Post-Order) LRN
void LRN(const NODETYPE *pCurr)
{
if (pCurr==NULL) return;
LRN(pCurr->pLeft);
LRN(pCurr->pRight);
“Xử lý nút gốc pCurr”
}
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân t
phân t
ì
ì

m ki
m ki
ế
ế
m
m
 Cây nhị phân tìm kiếm là:
• Một cây nhị phân
• Mỗi nút p của cây đều thỏa:
 Tất cả các nút thuộc cây con trái (p->pLeft) đều có
giá trị nhỏ hơn giá trị của p:
q  p->pLeft: q->Data < p->Data
 Tất cả các nút thuộc cây con phải (p->pRight) đều
có giá trị lớn hơn giá trị của p :
q  p->pRight: q->Data > p->Data
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh

Cây nh
ị
ị
phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á

á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
 Khởi tạo cây rỗng
void BSTCreate(BIN_TREE &t)
{
t.Count = 0; // Số nút trong cây
t.pRoot = NULL; // Con trỏ đến nút gốc
}
 Kiểm tra cây rỗng
int BSTIsEmpty(const BIN_TREE &t)
{
if (t.pRoot==NULL) return 1;
return 0;

}
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì

ì
m ki
m ki
ế
ế
m
m
 Tìm kiếm một phần tử
NODETYPE *BSTSearch(const NODETYPE *pCurr, int Key)
{
if (pCurr==NULL) return NULL; // Không tìm thấy
if (pCurr->Data==Key) return pCurr; // Tìm thấy
else if (pCurr->Data > Key) // Tìm trên cây con trái
return BSTSearch(pCurr->pLeft, Key);
else // Tìm trong cây con phải
return BSTSearch(pCurr->pRight, Key);
}
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây

c cây
C
C
á
á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ

ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
3/11/2010

www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì
ì
m ki

m ki
ế
ế
m
m
 Xoá một phần tử
• Thao tác xóa 1 phần tử:
 Áp dụng giải thuật tìm kiếm để xác định nút chứa
phần tử cần xóa
 Nếu tìm thấy, xóa phần tử đó khỏi cây
• Các trường hợp xảy ra:
 Xóa 1 nút không có nút con
 Xóa 1 nút có 1 nút con
 Xóa 1 nút có 2 nút con
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C

á
á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
 Xoá một nút không có nút con
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr

u tr
ú
ú
c cây
c cây
C
C
á
á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
 Xoá một nút có một nút con
3/11/2010
www.lhu.edu.vn

Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì
ì
m ki
m ki

ế
ế
m
m
 Xoá một nút có một nút con
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị

ị
phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
 Xoá một nút có hai nút con
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á

c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
 Xoá một nút có hai nút con
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú

ú
c cây
c cây
C
C
á
á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
 Thao tác
• Xóa 1 phần tử pCurr có 2 nút con:
• Thay vì xóa trực tiếp nút pCurr…ta tìm 1 phần
tử thay thế p,
 là phần tử lớn nhất trong cây con bên trái;

hoặc
 là phần tử nhỏ nhất trong cây con bên phải
• Copy nội dung của p sang pCurr
• Xóa nút p.
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị

phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
int BSTDelete(NODETYPE *&pCurr, int Key)
{
if (pCurr==NULL) return 0; // Không tìm thấy
if (pCurr->Data > Key) // Xóa trên cây con trái
return BSTDelete(pCurr->pLeft, Key);
else if (pCurr->Data < Key) //Xóa trên cây phải
return BSTDelete(pCurr->pRight, Key);
// Tìm thấy nút cần xóa pCurr Xóa !
_Delete(pCurr);
return 1;
}
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr

u tr
ú
ú
c cây
c cây
C
C
á
á
c thao t
c thao t
á
á
c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
void _Delete(NODETYPE *&pCurr)
{
NODETYPE *pTemp = pCurr;

if (pCurr->pRight==NULL) //có 1 nút con trái
pCurr = pCurr->pLeft; // Lưu lại nhánh con trái
else if (pCurr->pLeft==NULL)
pCurr = pCurr->pRight; // Lưu lại nhánh phải
else // Có 2 nhánh con
pTemp = _SearchStandFor(pCurr->pLeft, pCurr);
delete pTemp;
}
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
C
C
á
á
c thao t
c thao t
á
á

c trên cây nh
c trên cây nh
ị
ị
phân t
phân t
ì
ì
m ki
m ki
ế
ế
m
m
// Tìm phần tử thay thế: “Phần tử lớn nhất trong cây
//con bên trái”
NODETYPE * _SearchStandFor(NODETYPE *&p, NODETYPE *pCurr)
{
if (p->pRight != NULL)
return _SearchStandFor(p->pRight, pCurr);
// Tìm thấy phần tử thay thế…
pCurr->Data = p->Data; // Copy dữ liệu
NODETYPE *pTemp = p;
p = p->pLeft; // Lưu lại nhánh con trái
return pTemp; // Xóa phần tử thay thế
}
3/11/2010
www.lhu.edu.vn
Chương
Chương

6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân cân b
phân cân b
ằ
ằ
ng
ng
 Cây nhị phân tìm kiếm đạt hiệu quả cao nhất khi
nó có chiều cao thấp nhất (cây đạt trạng thái cân
bằng), khi đó thời gian tìm kiếm sẽ là O(log
2
n)
 Tuy nhiên khi thực hiện các thao tác thêm hoặc
xoá các nút sẽ làm cho cây mất trạng thái cân
bằng và có thể trở thành suy biến  hiệu suất
tìm kiếm giảm
 Vì thế để cây nhị phân tìm kiếm đạt hiệu quả tối

đa thì phải giữ cho cây luôn trong trạng thái cân
bằng
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân cân b
phân cân b
ằ
ằ
ng
ng
C:\My Data\Downloads\bo oks\GiaoTrinh \CauTruc DuLieu1\Htm\images\hinh13.2.gif
3/11/2010
www.lhu.edu.vn
Chương

Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân cân b
phân cân b
ằ
ằ
ng
ng
20
20
5
5
30
30
10
10
15

15
13
13
5
5
30
30
20
20
15
15
10
10
30
30
5
5
10
10
20
20
15
15
Cây mất cân bằng
Cây bị suy biến
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C

6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân cân b
phân cân b
ằ
ằ
ng
ng
 Cây nhị phân tìm kiếm cân bằng (còn gọi là cây
AVL), được các tác giả người Nga Adelson-
Velskii và Landis đưa ra năm 1962.
 Cây nhị phân cân bằng là cây nhị phân tìm kiếm
mà tại mỗi nút của nó chiều cao của cây con trái
và cây con phải lệch nhau không quá 1 đơn vị.
 Cây AVL có chiều cao log
2
n +1, với n là số nút
trên cây.
3/11/2010

www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân cân b
phân cân b
ằ
ằ
ng
ng
 Cấu trúc lưu trữ
Ta định nghĩa các hằng số chỉ trạng thái cân bằng của nút
//Cây con trái cao hơn
#define LH -1
//Hai cây con bằng nhau
#define EH -0
//Cây con phải cao hơn

#define RH 1
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cây nh
Cây nh
ị
ị
phân cân b
phân cân b
ằ
ằ
ng
ng
 Khai báo cấu trúc một nút
typedef struct Node
{
int Key;//Du lieu trong nut
struct Node *pLeft;//Con tro den cay con trai

struct Node *pRight;//Con tro den cay con phai
char Balance;//Trang thai can bang
int Count;//So nut trong cac cay con
}AVL_Node;
 Khai báo con trỏ đến nút gốc của cây
typedef AVL_Node *AVLTree;
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cân b
Cân b
ằ
ằ
ng l
ng l
ạ
ạ
i cây
i cây

 Trường hợp 1
• Nút P bị mất cân bằng về bên trái
• Nhánh con trái P1 của P bị lệch trái
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Cài đặt
void RotateRight(AVLTree &P) //Xoay nút P sang bên phải
{
if(P!=NULL)
{
AVL_Node *P1;
P1 = P->pLeft; //Q la con trai' cua P
P->pLeft = P1->pRight; //Lien ket pLeft cua P tro
//toi con phai cua P1
P1->pRight = P;//Lien ket pRight cua Q tro toi P
P = P1; //ghi nhan dia chi moi cua P
}
}

Xoay đơn sang ph
Xoay đơn sang ph
ả
ả
i
i
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cân b
Cân b
ằ
ằ
ng l
ng l
ạ
ạ
i cây
i cây

 Trường hợp 2
• Nút P bị mất cân bằng về bên trái
• Nhánh con trái P1 của P bị lệch phải
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Cài đặt
void DLRR(AVLTree &p)
{
if(p!=NULL)
{
AVL_Node *p1;
p1 = p->pLeft;
RotateLeft(p1);
p->pLeft = p1;
RotateRight(p);
}
}
Xoay k

Xoay k
é
é
p Left
p Left
-
-
Right
Right
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Cân b
Cân b
ằ
ằ
ng l
ng l
ạ

ạ
i cây
i cây
 Trường hợp 3
• Nút P bị mất cân bằng về bên phải
• Nhánh con trái P1 của P bị lệch phải
P
A
B
P
1
C
h
h
h + 1
RL
Áp dụng xoay đơn phải – trái (Right-Left)
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây

c cây
 Cài đặt
void RotateLeft(AVLTree &P) //Xoay nut P sang ben trai
{
if(P!=NULL)
{
AVL_Node *P1;
P1 =P->pRight; //q tro vao con trai' cua p
P->pRight = P1->pLeft; //lien ket Right cua p tro
//toi con trai' cua q
P1->pLeft = P; //lien ket Left cua Q tro toi P -
//dua P xuong ben trai
P = P1; //xac nhan lai dia chi moi cua P
}
}
Xoay đơn sang tr
Xoay đơn sang tr
á
á
i
i
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr

u tr
ú
ú
c cây
c cây
Cân b
Cân b
ằ
ằ
ng l
ng l
ạ
ạ
i cây
i cây
 Trường hợp 4
• Nút P bị mất cân bằng về bên phải
• Nhánh con trái P1 của P bị lệch trái
P2
P1
P
A
D
C
B
h
h
P
P1
P2

A
D
B
C
h
h
h
h
1
2
(b) : áp dụng xoay kép Phải – Trái (DRL_Double Right Left)
DRL
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Cài đặt
void DRLR(AVLTree &p)
{
if(p!=NULL)

{
AVL_Node *p1;
P1 = p->pRight;
RotateRight(p1);
p->pRight = p1;
RotateLeft(p);
}
}
Xoay k
Xoay k
é
é
p Right
p Right
-
-
Left
Left
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú

c cây
c cây
 Thêm phần tử mới vào cây
Việc thêm một phần tử vào cây AVL diễn ra
tương tự như trên CNPTK. Tuy nhiên, sau khi
thêm xong, nếu chiều cao của cây thay đổi, từ
vị trí thêm vào, ta phải lần ngược lên gốc để
kiểm tra xem có nút nào bị mất cân bằng
không. Nếu có, ta phải cân bằng lại ở nút này.
Cây nh
Cây nh
ị
ị
phân cân b
phân cân b
ằ
ằ
ng
ng
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú

ú
c cây
c cây
Thêm ph
Thêm ph
ầ
ầ
n t
n t
ử
ử
v
v
à
à
o cây
o cây
int insertNode(AVLTree &T, DataType X)
{ int res;
if(T) {
if(T->key == X) return 0; //đã có
if(T->key > X)
{
res = insertNode(T->pLeft, X);
if(res < 2) return res;
switch(T->Balance)
{
case RH: T->Balance = EH;
return 1;
case EH: T->Balance = LH;

return 2;
case LH: balanceLeft (T);
return 1;
}
}
else
{
res = insertNode(T-> pRight, X);
if(res < 2) return res;
switch(T->Balance)
{
case LH: T->Balance = EH;
return 1;
case EH: T->Balance = RH;
return 2;
case RH: balanceRight(T); return 1;
}
}
}
T = new AVL_Node;
if(T == NULL) return -1; //thiếu bộ nhớ
T->key = X; T->Balance = EH;
T->pLeft = T->pRight = NULL;
return 2; // thành công, chiều cao tăng
}
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C

6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
 Huỷ phần tử trên cây
Cũng giống như thao tác thêm một nút, việc hủy
một phần tử X ra khỏi cây AVL thực hiện
giống như trên CNPTK.
Chỉ sau khi hủy, ta phải lần ngược lên gốc để
kiểm tra xem có nút nào bị mất cân bằng
không, nếu có ta sẽ thực hiện việc cân bằng
lại
Cây nh
Cây nh
ị
ị
phân cân b
phân cân b
ằ
ằ
ng
ng
3/11/2010
www.lhu.edu.vn
Chương

Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Hu
Hu
ỷ
ỷ
ph
ph
ầ
ầ
n t
n t
ử
ử
trên cây
trên cây
int delNode(AVLTree &T, DataType X)
{ int res;
if(T==NULL) return 0;
if(T->key > X) {
res = delNode (T->pLeft, X);

if(res < 2) return res;
switch(T->Balance) {
case LH: T->Balance = EH;
return 2;
case EH: T->Balance = RH;
return 1;
case RH: return balanceRight(T);
}
}
if(T->key < X) {
res = delNode (T->pRight, X);
if(res < 2) return res;
switch(T->Balance) {
case RH: T->Balance = EH;
return 2;
case EH: T->Balance = LH;
return 1;
case LH: return balanceLeft(T);
}
}else { //T->key == X
AVLNode* p = T;
if(T->pLeft == NULL) {
T = T->pRight; res = 2;
}else if(T->pRight == NULL) {
T = T->pLeft; res = 2;
}else { //T có cả 2 con
res=searchStandFor(p,T->pRight);
if(res < 2) return res;
switch(T->Balance) {
case RH: T->Balance = EH;

return 2;
case EH: T->Balance = LH;
return 1;
case LH: return balanceLeft(T);
}
}
delete p;
return res;
}
}
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Hu
Hu
ỷ
ỷ
ph
ph

ầ
ầ
n t
n t
ử
ử
trên cây
trên cây
//Tìm phần tử thế mạng
int searchStandFor(AVLTree &p, AVLTree &q)
{ int res;
if(q->pLeft) {
res = searchStandFor(p, q->pLeft);
if(res < 2) return res;
switch(q->Balance) {
case LH: q->Balance = EH;return 2;
case EH: q->Balance = RH;return 1;
case RH: return balanceRight(T);
}
}else {
p->key = q->key;
p = q;
q = q->pRight;
return 2;
}
}
3/11/2010
www.lhu.edu.vn
Chương
Chương

6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Hu
Hu
ỷ
ỷ
ph
ph
ầ
ầ
n t
n t
ử
ử
trên cây
trên cây
void BalanceRight(Tree &P)
{
AVL_Node *Q, *R;
Q = P->pRight; //q tro vao cay con
phai
switch(Q->Balance)

{
case 1: //Single Rotation
P->Balance = 0;
Q->Balance = 0;
RotateLeft(P);
break;
case -1:
//cay lech trai >Double Rotation
R = Q->pLeft;
switch(R->Balance)
{
case 0:
P->Balance = 0;
Q->Balance = 0;
break;
case -1:
P->Balance = 0;
Q->Balance = 1;
break;
case 1:
P->Balance = -1;
Q->Balance = 0;
break;
}
R->Balance = 0;
/*Double Right-Left Rotation*/
DRLR(P);
break;
}
}

Cân bằng lại cây con bên phải của node P trong trường hợp P lệch phải
3/11/2010
www.lhu.edu.vn
Chương
Chương
6 C
6 C
ấ
ấ
u tr
u tr
ú
ú
c cây
c cây
Hu
Hu
ỷ
ỷ
ph
ph
ầ
ầ
n t
n t
ử
ử
trên cây
trên cây
void BalanceLeft(Tree &P)

{
AVL_Node *Q, *R;
Q = P->pLeft; //q tro vao cay con
trai
switch(Q->Balance)
{
case -1: //Single Rotation
P->Balance = 0;
Q->Balance = 0;
RotateRight(P);
break;
case 1: //Double Rotation
R = Q->pRight;
switch(R->Balance)
{
case 0:
P->Balance = 0;
Q->Balance = 0;
break;
case -1:
P->Balance = -1;
Q->Balance = 0;
break;
case 1:
P->Balance = 0;
Q->Balance = -1;
break;
}
R->Balance = 0;
/*Double pLeft-pRight Rotation*/

DLRR(P);
break;
}
}
Cân bằng lại cây con bên trái của node P trong trường hợp P lệch trái