Chương 5. Cây nhị phân tìm kiếm – Cây cân bằng

ầ

Tr n Minh Thái Email: minhthai@huflit.edu.vn Website: www.minhthai.edu.vn

1

Nội dung

1.

Khái niệm cây AVL

2.

Đặc điểm

3.

Định nghĩa cấu trúc dữ liệu

4.

Các kỹ thuật cân bằng cây

5.

Chèn phần tử vào cây

6.

Xóa phần tử khỏi cây

2

Cây nhị phân tìm kiếm cân bằng

• Phát minh: Nhà toán học Nga G. M. Adel’Son-

Vel’Skil và E. M. Landis (1962)

• Cấu trúc cây giúp tối ưu thời gian tìm kiếm

• Cây nhị phân tìm kiếm cân bằng: cây AVL

• Chi phí tìm kiếm, thêm mới, xoá trong cây n nút là

O(log n)

3

Định nghĩa

• Cây AVL là một cây nhị phân tìm kiếm

• Chiều cao cây con trái và phải của nút gốc hơn

kém nhau không quá 1

• Cả hai cây con trái và phải cũng phải là cây AVL

4

Chỉ số cân bằng (Balance factor)

Chỉ số cân bằng (bF – balance Factor) của một nút:

bF = hL – hR

ü hL: chiều cao cây con trái

ü hR: chiều cao cây con phải

Có 3 trường hợp:

ØbF = 0: hL = hR

ØbF > 0: hL > hR

ØbF < 0: hL < hR

5

Khai báo cấu trúc cây AVL

class CMyAVLNode {

private T data; private int height; private CMyAVLNode pLeft = null; private CMyAVLNode pRight = null; //Các property get/ set //Các phương thức

}

6

Constructor cho node

public CMyAVLIntNode(T x) {

data = x; height = 1; pLeft = null; pRight = null;

7

}

Trường hợp 1: Lệch trái

1.1 Lệch trái – trái

1.2 Lệch trái – phải 8

Trường hợp 2: Lệch phải

2.1 Lệch phải – trái

2.2 Lệch phải – phải 9

Lệch trái - trái

10

Quay phải

Lệch trái – phải: Thực hiện quay kép

11

B1. Quay trái

Lệch trái – phải: Thực hiện quay kép

12

B2. Quay phải

Thêm 1 node vào cây AVL

• Tương tự như trên cây NPTK

• Sau khi thêm xong, nếu chiều cao của cây thay

đổi. Nếu có mất cân bằng  cân bằng lại ở nút

này

• Phương thức InsertNode trả về node root mới sau

khi cân bằng

13

Bài tập 1

Cho dãy số: 45, 46, 70, 11, 13, 42, 21, 9, 25, 4

•

Hãy trình bày từng bước quá trình xây dựng cây AVL

•

Trình bày từng bước duyệt cây theo thứ tự sau

14

Xác định chỉ số cân bằng

int Height(CMyAVLNode N) {

if (N == null) return 0; return N.Height;

}

int GetBalance(CMyAVLNode N) {

if (N == null) return 0;

return Height(N.PLeft) - Height(N.PRight);

15

}

Phương thức xoay phải

public CMyAVLNode RightRotate(CMyAVLNode T) {

CMyAVLNode T1 = T.PLeft; CMyAVLNode RT1 = T1.PRight;

T1.PRight = T; T.PLeft = RT1; T.Height = Max(Height(T.PLeft), Height(T.PRight)) + 1; T1.Height = Max(Height(T1.PLeft), Height(T1.PRight)) + 1; return T1;

}

16

Phương thức xoay trái

public CMyAVLNode LeftRotate(CMyAVLNode T) {

CMyAVLNode T1 = T.PRight; CMyAVLNode LT1 = T1.PLeft;

T1.PLeft = T; T.PRight = LT1;

T.Height = Max(Height(T.PLeft), Height(T.PRight)) + 1; T1.Height = Max(Height(T1.PLeft), Height(T1.PRight)) + 1;

return T1;

}

17

public CMyAVLNode Insert(CMyAVLNode node, T x) {

if (node == null)

return (new CMyAVLNode(x));

if (node.Data == x) return node; if (x < node.Data)

node.PLeft = Insert(node.PLeft, x);

else

node.PRight = Insert(node.PRight, x);

node.Height = 1 + Max(Height(node.PLeft),

Height(node.PRight));

18

//Xác định ch s cân bằng ỉ ố int balance = GetBalance(node);

if (balance > 1 && x < node.PLeft.Data)//LL

return RightRotate(node);

if (balance < -1 && x > node.PRight.Data)//RR

return LeftRotate(node);

if (balance > 1 && x > node.PLeft.Data)//LR

{

node.PLeft = LeftRotate(node.PLeft); return RightRotate(node);

} if (balance < -1 && x < node.PRight.Data)//RL {

node.PRight = RightRotate(node.PRight); return LeftRotate(node);

} return node;

19

}

Hủy 1 node trên cây

• Tương tự như trên cây NPTK

• Sau khi hủy, nếu mất cân bằng  cân bằng lại

• Hàm DeleteNode trả về node root sau khi cân

bằng

20

Bài tập 2

1. Hãy trình bày từng bước quá trình:

• Xóa node có giá trị 13

• Xóa node có giá trị 45

2. Trình bày thuật toán và cài đặt phương thức xóa

node trên cây AVL

21