C u trúc d li u và thu t gi iấ ữ ệ ậ ả
C U TRÚC D LI U VÀ GI I THU T 1Ấ Ữ Ệ Ả Ậ
Click To Edit Master Title Style
C U TRÚC D LI U VÀ GI I THU T 1Ấ Ữ Ệ Ả Ậ
1
N I DUNGỘ
CÂY NH PHÂN TÌM KI M CÂN B NGỊ Ế Ằ
C u trúc d li u và thu t gi iấ ữ ệ ậ ả
C U TRÚC D LI U VÀ GI I THU T 1Ấ Ữ Ệ Ả Ậ
Click To Edit Master Title Style
C U TRÚC D LI U VÀ GI I THU T 1Ấ Ữ Ệ Ả Ậ
2
Ð nh nghĩaị
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ệ ộ
Ví d :ụ
44
23 88
13 37 59 108
15 30 40 55 71
C u trúc d li u và thu t gi iấ ữ ệ ậ ả
C U TRÚC D LI U VÀ GI I THU T 1Ấ Ữ Ệ Ả Ậ
Click To Edit Master Title Style
C U TRÚC D LI U VÀ GI I THU T 1Ấ Ữ Ệ Ả Ậ
3
T ch c d li uổ ứ ữ ệ
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)
CSCB(p) = 1 ⇔Độ cao cây trái (p) < Độ cao
cây ph iả (p)
CSCB(p) = -1 ⇔Độ cao cây trái (p) > Độ
cao cây ph iả (p)
C u trúc d li u và thu t gi iấ ữ ệ ậ ả
C U TRÚC D LI U VÀ GI I THU T 1Ấ Ữ Ệ Ả Ậ
Click To Edit Master Title Style
C U TRÚC D LI U VÀ GI I THU T 1Ấ Ữ Ệ Ả Ậ
4
T ch c d li u(tt)ổ ứ ữ ệ
#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ỉ ố ằ
Data key;
struct tagAVLNode* pLeft;
struct tagAVLNode* pRight;
}AVLNode;
typedef AVLNode *AVLTree;
C u trúc d li u và thu t gi iấ ữ ệ ậ ả
C U TRÚC D LI U VÀ GI I THU T 1Ấ Ữ Ệ Ả Ậ
Click To Edit Master Title Style
C U TRÚC D LI U VÀ GI I THU T 1Ấ Ữ Ệ Ả Ậ
5
Các tr ng h p m t cân b ng do l ch tráiườ ợ ấ ằ ệ
T
R
T1
R1
L1
T
R
T1
T2
L1
R21
L21
Cây m t cân b ng t i nút Tấ ằ ạ
TH1: Left-Left TH2: Left-Right