Xem mẫu
- CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU t ÚC dữ ệu v G Ả HU T
1
NỘI DUNG
CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG
Click To Edit Master Title Style
- Ðịnh nghĩa Edit Master Title Style
Click To
Cây nhị phân tìm kiếm cân bằng là cây mà tại mỗi nút
của nó độ cao của cây con trái và của cây con phải
chênh lệch không quá một
44
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
Ví dụ: 23 88
CẤU t ÚC dữ ệu v G Ả HU T
59 108
13 37
15 30 40 55 71
2
- Tổ Click dữ liệu Master Title Style
chức To Edit
Chỉ số cân bằng = độ lệch giữa cây trái và
cây phải của một nút
Các giá trị hợp lệ :
CSCB(p) = 0 ⇔ Độ cao cây trái (p) = Độ cao
cây phải (p)
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
CSCB(p) = 1 ⇔ Độ cao cây trái (p) < Độ cao
CẤU t ÚC dữ ệu v G Ả HU T
cây phải (p)
⇔ Độ cao cây trái (p) > Độ
CSCB(p) = -1
cao cây phải (p)
3
- Tổ Click dữ liệu(tt)
chức To Edit Master Title Style
#define LH -1 //cây con trái cao hơn
#define EH 0 //cây con trái bằng cây con phải
#define RH 1 //cây con phải cao hơn
typedef struct tagAVLNode
{ char balFactor; //chỉ số cân bằng
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
CẤU t ÚC dữ ệu v G Ả HU T
Data key;
struct tagAVLNode* pLeft;
struct tagAVLNode* pRight;
}AVLNode;
typedef AVLNode *AVLTree;
4
- CácClick ToợEdit Masterng do lệch trái
trường h p mất cân bằ Title Style
Cây mất cân bằng tại nút T
T
TH1: Left-Left TH2: Left-Right T
T1 R
T1 R
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
CẤU t ÚC dữ ệu v G Ả HU T
R1
L1
T2
L1
R21
L21
5
- CácClick ToợEdit Masterng do lệch phải
trường h p mất cân bằ Title Style
Cây mất cân bằng tại nút T
TH3: Right-Right TH4: Right-Left
T
T
L
L T1
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
T1
CẤU t ÚC dữ ệu v G Ả HU T
T2 R1
L1 R1
R21
L21
6
- Các thao To Edit cây cân Title Style
Click tác trên Master bằng
Khi thêm hay xoá 1 nút trên cây, cĩ thể làm cho cây
mất tính cân bằng, khi ấy ta phải tiến hành cân
bằng lại.
Cây có khả năng mất cân bằng khi thay đổi chiều
cao:
Lệch nhánh trái, thêm bên trái
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
CẤU t ÚC dữ ệu v G Ả HU T
Lệch nhánh phải, thêm bên phải
Lệch nhánh trái, hủy bên phải
Lệch nhánh phải, hủy bên trái
Cân bằng lại cây : tìm cách bố trí lại cây sao cho
chiều cao 2 cây con cân đối:
Kéo nhánh cao bù cho nhánh thấp
7
- CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU t ÚC dữ ệu v G Ả HU T
L1
T1
R1
T
R
8
L1
Cân bằng lạiEdit ng hợp 1
T1
R1
T
Click To trườMaster Title Style
R
- CàiClick Tobằng Mastertrường hợp 1
đặt cân Edit lại cho Title Style
void LL(AVLTree &T)
{
AVLNode *T1=T->pLeft;
T->pLeft = T1->pRight;
T1->pRight=T;
switch(T1-> balFactor)
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
CẤU t ÚC dữ ệu v G Ả HU T
{ case LH: T-> balFactor =EH;
T1->balFactor=EH; break;
case EH: T->balFactor=LH;
T1->balFactor =RH; break;
}
T=T1;
} 9
- CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU t ÚC dữ ệu v G Ả HU T
L1
T1
L21
T2
T
R21
R
10
L1
T1
Cân bằng lạiEdit ng hợp 2
L21
T2
R21
T
Click To trườMaster Title Style
R
- CàiClick Tobằng Mastertrường hợp 2
đặt cân Edit lại cho Title Style
void LR(AVLTree &T)
{ AVLNode *T1=T->pLeft;
AVLNode *T2=T1->pRight;
T->pLeft=T2->pRight;
T2->pRight=T;
T1->pRight= T2->pLeft;
T2->pLeft = T1;
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
CẤU t ÚC dữ ệu v G Ả HU T
switch(T2->balFactor)
{ case LH: T->balFactor=RH;
T1->balFactor=EH; break;
case EH: T->balFactor = EH;
T1->balFactor=EH; break;
case RH: T->balFactor =EH;
T1->balFactor= LH; break;
}T2->balFactor =EH; T=T2}
11
- CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU t ÚC dữ ệu v G Ả HU T
L
T
L1
T1
R1
12
L
T
Cân bằng lạiEdit ng hợp 3
L1
T1
R1
Click To trườMaster Title Style
- CàiClick Tobằng Mastertrường hợp 3
đặt cân Edit lại cho Title Style
void RR(AVLTree &T)
{ AVLNode *T1= T->pRight;
T->pRight=T1->pLeft;
T1->pLeft=T;
switch(T1-> balFactor)
{
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
CẤU t ÚC dữ ệu v G Ả HU T
case RH: T-> balFactor = EH;
T-> balFactor = EH; break;
case EH: T-> balFactor = RH;
T1-> balFactor = LH; break;
}
T=T1
} 13
- CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU t ÚC dữ ệu v G Ả HU T
L
L21
T
T2
T1
R21
R1
14
L
T
Cân bằng lạiEdit ng hợp 4
L21
T2
R21
T1
Click To trườMaster Title Style
R1
- CàiClick Tobằng Mastertrường hợp 4
đặt cân Edit lại cho Title Style
void RR(AVLTree &T)
{ AVLNode *T1= T->pRight;
AVLNode *T2=T1->pLeft;
T->pRight = T2->pLeft;
T2->pLeft = T;
T1->pLeft = T2->pRight;
T2->pRight = T1;
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
switch(T2-> balFactor)
CẤU t ÚC dữ ệu v G Ả HU T
{ case RH: T-> balFactor = LH;
T1-> balFactor = EH; break;
case EH: T-> balFactor = EH;
T1-> balFactor = EH; break;
case LH: T-> balFactor = EH;
T1-> balFactor = RH; break;
}
T2-> balFactor =EH; T=T2;}
15
- Thêm 1 nút Edit Master Title Style
Click To
Thêm bình thường như trường hợp cây NPTK
Nếu cây tăng trưởng chiều cao
Lần ngược về gốc để phát hiện nút bị mất cân
bằng
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
CẤU t ÚC dữ ệu v G Ả HU T
Tiến hành cân bằng lại nút đó bằng thao tác cân
bằng thích hợp
Việc cân bằng lại chỉ cần thực hiện 1 lần nơi mất
cân bằng
16
- Hủy 1 nút Edit Master Title Style
Click To
Hủy bình thường như trường hợp cây NPTK
Nếu cây giảm chiều cao:
Lần ngược về gốc để phát hiện nút bị mất cân
bằng
Cấu Rrúc DỮ IlIiỆU VÀ à IthuậtẬgiải
CẤU TTRÚCDỮ LLỆU VÀ GIẢI ITTHUẬT11
Tiến hành cân bằng lại nút đó bằng thao tác cân
CẤU t ÚC dữ ệu v G Ả HU T
bằng thích hợp
Tiếp tục lần ngược lên nút cha…
Việc cân bằng lại co thể lan truyền lên tận
gốc
17
nguon tai.lieu . vn
