Chapter 6: Cấu trúc cây ( tree)

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

(cid:67)(cid:104)(cid:432)(cid:417)(cid:110)(cid:103) (cid:54)

CCáác khc kháái ni i niệệm cơ b m cơ bảảnn

(cid:99)(cid:32)(cid:99)(cid:226)(cid:121)(cid:32)(cid:40)(cid:84)(cid:114)(cid:101)(cid:101)(cid:41) (cid:67)(cid:67)ấấ(cid:117)(cid:32)(cid:116)(cid:114)(cid:117)(cid:32)(cid:116)(cid:114)(cid:250)(cid:250)(cid:99)(cid:32)(cid:99)(cid:226)(cid:121)(cid:32)(cid:40)(cid:84)(cid:114)(cid:101)(cid:101)(cid:41) (cid:67)ấ(cid:117)(cid:32)(cid:116)(cid:114)(cid:250)(cid:99)(cid:32)(cid:99)(cid:226)(cid:121)(cid:32)(cid:40)(cid:84)(cid:114)(cid:101)(cid:101)(cid:41)

(cid:61607) Ví dụ: bài toán đưa thư

i dung NNộội dung (cid:61607) 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” 1 Các khái niệm cơ bản

2 Cây nhị phân tìm kiếm

3 Cây nhị phân cân bằng (cid:61607) Trên thế giới hiện có khoảng 8 tỷ người (cid:61607) Làm thế nào để tìm ra người A nhanh nhất? (cid:61607) Dùng cấu trúc mảng ?? (cid:61607) Dùng danh sách liên kết ??

3/11/2010

www.lhu.edu.vn

4 Cây nhiều nhánh

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

CCáác khc kháái ni i niệệm cơ b m cơ bảảnn CCáác khc kháái ni i niệệm cơ b m cơ bảảnn

(cid:61607) Ví dụ: cây thư mục windows

3/11/2010

www.lhu.edu.vn

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

CCáác khc kháái ni i niệệm cơ b m cơ bảảnn CCáác khc kháái ni i niệệm cơ b m cơ bảảnn

(cid:61607) Ví dụ: cây biểu thức (a+b)/(c-d)

(cid:61607) Ví dụ: cây quyết định

Nhiệt độ

Bình thường

Đau đầu Nhiệt độ

Cúm

Rất cao

(cid:123)(cid:101)(cid:51)(cid:44)(cid:101)(cid:54)(cid:125)

(cid:123)(cid:101)(cid:49)(cid:44)(cid:32)(cid:101)(cid:52)(cid:125)

Cao (cid:123)(cid:101)(cid:50)(cid:44)(cid:32)(cid:101)(cid:53)(cid:125)

Bình thường Không

Có

không

Có

Cao

Có

Đau đầu

Có

Rất cao

Có

không

có

{e6}

có {e2}

{e3}

không {e5}

Không

Bình thường Không

Có

không

Có

không

Không

Cao

Không

Rất cao

Không

3/11/2010

www.lhu.edu.vn

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

CCáác khc kháái ni i niệệm cơ b m cơ bảảnn CCáác khc kháái ni i niệệm cơ b m cơ bảảnn

(cid:61607) Định nghĩa

(cid:61607) Ví dụ: cây nhiều nhánh

(cid:61607) Một cây (Tree) là: (cid:61607) Một tập các phần tử, gọi là các nút (Node): p1,p2,…,pN

• 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 là 1 cây con của cây

3/11/2010

www.lhu.edu.vn

(cid:61607) Nếu N=0, cây gọi là cây rỗng (NULL) (cid:61607) Nếu N>0:

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

CCáác khc kháái ni i niệệm cơ b m cơ bảảnn CCáác khc kháái ni i niệệm cơ b m cơ bảảnn

(cid:61607) 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ỳ

(cid:61607) Bậc của 1 nút pi: là số nút con của pi (cid:61607) Ví dụ trên : Bậc (a) = 4; Bậc (j) = 3; Bậc (g) = 2;

Bậc (k) = 1; Bậc (c) = 0

(cid:61607) Nhánh (Branch): là đoạn nối giữa 2 nút (cid:61607) Nút cha (Parent node) (cid:61607) Nút con (Child node) (cid:61607) Nút anh em (Sibling nodes): là những nút có

cùng nút cha

(cid:61607) Nút gốc (Root node): nút không có nút cha (cid:61607) 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) (cid:61607) Nút nội (Internal node): là nút có nút cha và có

nút con

(cid:61607) Cây con (Subtree)

3/11/2010

www.lhu.edu.vn

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

CCáác khc kháái ni i niệệm cơ b m cơ bảảnn CCáác khc kháái ni i niệệm cơ b m cơ bảảnn

(cid:61607) Bậc của cây: là bậc lớn nhất của các nút trong

(cid:61607) Mức (Level):

(cid:61607) Mức (p) = 0 nếu p = root (cid:61607) Mức (p) = 1 + Mức (Cha (p)) nếu p!=root

cây (cid:61607) Bậc () = max {bậc (pi) / pi Î } (cid:61607) Bậc của cây ?

(cid:61607) Chiều cao của cây (Height - hT): đường đi dài

(cid:61607) Đường đi (Path) giữa nút pi đến nút pj: là dãy

nhất từ nút gốc đến nút lá (cid:61607) hT = max {Path(root, pi) / pi là nút lá Î }

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 (cid:61607) Path(a, d) ?

3/11/2010

www.lhu.edu.vn

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

(cid:61607) 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 + d2 + d3 + … + dh-1 = (dh - 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

CCáác khc kháái ni i niệệm cơ b m cơ bảảnn CCáác khc kháái ni i niệệm cơ b m cơ bảảnn

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

CCáác khc kháái ni i niệệm cơ b m cơ bảảnn Cây nhịị phânphân Cây nh

(cid:61607) Cây hoàn chỉnh (Complete tree) với h mức:

(cid:61607) Cây nhị phân là cây có bậc = 2 (cid:61607) Độ cao của cây nhị phân có N nút:

• hT(max) = N • hT(min) = [logN] + 1

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

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

Cây nhịị phânphân Cây nh Cây nhịị phânphân Cây nh

(cid:61607) 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

(cid:61607) 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];

NODETYPE *pRoot; // con trỏ đến nút gốc

}; // binary tree

3/11/2010

www.lhu.edu.vn

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

Cây nhịị phânphân Cây nh Cây nhịị phânphân Cây nh

(cid:61607) Cấu trúc lưu trữ dùng con trỏ

(cid:61607) 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

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

Cây nhịị phânphân Cây nh Cây nhịị phânphân Cây nh

(cid:61607) Duyệt gốc trước (Pre-Order) NLR

(cid:61607) Duyệt gốc giữa (In-Order) LNR

void NLR(const NODETYPE *pCurr) {

void LNR(const NODETYPE *pCurr) {

if (pCurr==NULL) return; “Xử lý nút gốc pCurr” NLR(pCurr->pLeft); NLR(pCurr->pRight);

if (pCurr==NULL) return; LNR(pCurr->pLeft); “Xử lý nút gốc pCurr” LNR(pCurr->pRight);

}

3/11/2010

www.lhu.edu.vn

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

Cây nhịị phânphân Cây nh Cây nhịị phân t Cây nh phân tììm kim kiếếmm

(cid:61607) Duyệt gốc sau (Post-Order) LRN

(cid:61607) 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:

void LRN(const NODETYPE *pCurr) {

(cid:61692) Tất cả các nút thuộc cây con trái (p->pLeft) đều có

if (pCurr==NULL) return; LRN(pCurr->pLeft); LRN(pCurr->pRight); “Xử lý nút gốc pCurr”

}

giá trị nhỏ hơn giá trị của p: (cid:61474)q (cid:61476) p->pLeft: q->Data < p->Data (cid:61692) Tất cả các nút thuộc cây con phải (p->pRight) đều

3/11/2010

www.lhu.edu.vn

có giá trị lớn hơn giá trị của p : (cid:61474)q (cid:61476) p->pRight: q->Data > p->Data

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

Cây nhịị phân t Cây nh phân tììm kim kiếếmm CCáá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 kim kiếếmm

(cid:61607) 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

} (cid:61607) 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

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

CCáá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 kim kiếếmm CCáá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 kim kiếếmm

(cid:61607) 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

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

(cid:61607) Xoá một phần tử

• Thao tác xóa 1 phần tử:

(cid:61692) Á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 (cid:61692) Nếu tìm thấy, xóa phần tử đó khỏi cây

• Các trường hợp xảy ra:

3/11/2010

www.lhu.edu.vn

(cid:61692) Xóa 1 nút không có nút con (cid:61692) Xóa 1 nút có 1 nút con (cid:61692) Xóa 1 nút có 2 nút con

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

CCáá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 kim kiếếmm CCáác thao t c thao táác trên cây nh phân tììm kim kiếếmm

c trên cây nhịị phân t (cid:61607) Xoá một nút có một nút con

(cid:61607) Xoá một nút không có nút con

3/11/2010

www.lhu.edu.vn

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

CCáác thao t c thao táác trên cây nh phân tììm kim kiếếmm CCáác thao t phân tììm kim kiếếmm

3/11/2010

www.lhu.edu.vn

c trên cây nhịị phân t (cid:61607) Xoá một nút có một nút con c thao táác trên cây nh c trên cây nhịị phân t (cid:61607) Xoá một nút có hai nút con

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

CCáác thao t phân tììm kim kiếếmm CCáá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 kim kiếếmm

c thao táác trên cây nh c trên cây nhịị phân t (cid:61607) Xoá một nút có hai nút con

(cid:61607) 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, (cid:61692) là phần tử lớn nhất trong cây con bên trái;

hoặc

(cid:61692) 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

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

int BSTDelete(NODETYPE *&pCurr, int Key) {

void _Delete(NODETYPE *&pCurr) {

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 (cid:61672)Xóa ! _Delete(pCurr); return 1;

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

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

// 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) {

CCáá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 kim kiếếmm Cây nhịị phân cân b Cây nh phân cân bằằngng

(cid:61607) 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(log2n) (cid:61607) 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 (cid:61672) hiệu suất tìm kiếm giảm

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ế

}

(cid:61607) 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

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

C:\MyData\Downloads\books\GiaoTrinh\CauTrucDuLieu1\Htm\images\hinh13.2.gif

2020

3030

1010

3030

2020

3030

1515

2020

1010

1313

1010

1515

Cây mất cân bằng

Cây bị suy biến

3/11/2010

www.lhu.edu.vn

Cây nhịị phân cân b Cây nh phân cân bằằngng Cây nhịị phân cân b Cây nh phân cân bằằngng

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

Cây nhịị phân cân b Cây nh phân cân bằằngng Cây nhịị phân cân b Cây nh phân cân bằằngng

(cid:61607) Cấu trúc lưu trữ

(cid:61607) 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.

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

(cid:61607) 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ị. (cid:61607) Cây AVL có chiều cao log2n +1, với n là số nút

trên cây.

3/11/2010

www.lhu.edu.vn

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

i cây Cân bằằng lng lạại cây Cân b Cây nhịị phân cân b Cây nh phân cân bằằngng

(cid:61607) Trường hợp 1

(cid:61607) 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;

• 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

(cid:61607) 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

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

i cây Cân bằằng lng lạại cây Cân b Xoay đơn sang phảảii Xoay đơn sang ph

(cid:61607) Trường hợp 2

(cid:61607) 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

}

3/11/2010

www.lhu.edu.vn

• 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

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

i cây Cân bằằng lng lạại cây Cân b Xoay kéép Left Xoay k Right p Left--Right

(cid:61607) Trường hợp 3

(cid:61607) Cài đặt

void DLRR(AVLTree &p) {

• 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

P1

if(p!=NULL) {

P

RL

h + 1

C

h

AVL_Node *p1; p1 = p->pLeft; RotateLeft(p1); p->pLeft = p1; RotateRight(p);

A

B

}

Áp dụng xoay đơn phải – trái (Right-Left)

3/11/2010

www.lhu.edu.vn

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

i cây Cân bằằng lng lạại cây Cân b Xoay đơn sang trááii Xoay đơn sang tr

(cid:61607) Trường hợp 4

(cid:61607) Cài đặt

void RotateLeft(AVLTree &P) //Xoay nut P sang ben trai {

(cid:80)

(cid:80)(cid:50)

if(P!=NULL) {

(cid:68)(cid:82)(cid:76)

(cid:50)

(cid:80)(cid:49)

(cid:80)

(cid:80)(cid:49)

(cid:49)

(cid:104)

(cid:80)(cid:50)

(cid:65)

AVL_Node *P1; P1 =P->pRight; //q tro vao con trai' cua p P->pRight = P1->pLeft; //lien ket Right cua p tro

(cid:104)

(cid:68)

(cid:65)

(cid:66)

(cid:67)

(cid:68)

//toi con trai' cua q P1->pLeft = P; //lien ket Left cua Q tro toi P -

//dua P xuong ben trai

(cid:104)

(cid:66)

(cid:67)

P = P1; //xac nhan lai dia chi moi cua P

}

(b) : áp dụng xoay kép Phải – Trái (DRL_Double Right Left)

}

3/11/2010

www.lhu.edu.vn

• 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

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

Xoay kéép Right Xoay k p Right--LeftLeft Cây nhịị phân cân b Cây nh phân cân bằằngng

(cid:61607) Cài đặt

(cid:61607) Thêm phần tử mới vào cây

void DRLR(AVLTree &p) {

if(p!=NULL) {

AVL_Node *p1; P1 = p->pRight; RotateRight(p1); p->pRight = p1; RotateLeft(p);

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.

}

3/11/2010

www.lhu.edu.vn

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

o cây Thêm phầần tn tửử vvàào cây Thêm ph Cây nhịị phân cân b Cây nh phân cân bằằngng

(cid:61607) Huỷ phần tử trên cây

int insertNode(AVLTree &T, DataType X) { int res; if(T) { if(T->key == X) return 0; //đã có if(T->key > X)

{

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.

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;

}

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

}

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

c cây Chương 6 C6 Cấấu tru trúúc cây Chương

trên cây HuHuỷỷ phphầần tn tửử trên cây trên cây HuHuỷỷ phphầần tn tửử trên cây

n t

ng

th

m

ạ

ầ

ử

//Tìm ph ế 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 {

}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; } }

p->key = q->key; p = q; q = q->pRight; return 2;

}

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); }

}

3/11/2010

www.lhu.edu.vn