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

TRƯỜNG ĐHSP HÀ NỘI
LỚP CHK15 - KHOA CNTT
BÀI GIẢNG MÔN
CẤU TRÚC DỮ LIỆU
CÂY TÌM KIẾM NHỊ PHÂN
KHÁI NIỆM
TÌM KIẾM
THÊM
XOÁ
GIẢNG VIÊN HƯỚNG DẪN
PGS.TS LÊ KHẮC THÀNH
HỌC VIÊN THỰC HIỆN
NGUYỄN VIỆT HUỲNH MAI
DUYỆT
KHÁI NIỆM
1.CÂY
Cây là một tập hữu hạn các nút, trong đó có một nút đặc biệt gọi là gốc (root). Giữa các nút có một quan hệ phân cấp gọi là "quan hệ cha con".
2. CÂY NHỊ PHÂN
Cây nhị phân là cây có thứ tự và có đặc điểm mọi nút trên cây có tối đa 2 con:
? Cây con trái
? Cây con phải

KHÁI NIỆM(tt)
3. CÂY TÌM KIẾM NHỊ PHÂN
- Cây tìm kiếm nhị phân được tổ chức theo một cây nhị phân.
- Cây tìm kiếm nhị phân có thể được biểu diễn bởi một cấu trúc dữ liệu nối kết.
- Ngoài một trường key, mỗi nút chứa một trường left, right và p trỏ đến các nút tương ứng với con trái, con phải và cha của nó. Nếu thiếu một con hoặc cha trường thích hợp sẽ chứa giá trị NIL. Nút gốc là nút duy nhất trong cây có trường cha là NIL.
- Các khoá trong cây tìm kiếm nhị phân được lưu trữ theo tính chất sau:
- Cho x là một nút trong cây tìm kiếm nhị phân. Nếu y là một nút trong cây con trái của x, thì key[y] ? key[x]. Nếu y là một nút trong cây con phải của x, thì key[x] ? key[y].

0
KHÁI NIỆM(tt)
4. VÍ DỤ CÂY TÌM KIẾM NHỊ PHÂN
1
4
4
5
10
8
0
1
4
4
5
10
8
Chọn nút số 4 làm nút gốc
Các nút con là 1 0 4 5 8 10
Chọn nút số 0 làm nút gốc
Các nút con là 1 5 4 4 8 10
0
1
4
4
5
10
8
DUYỆT CÂY
1. Duyệt theo thứ tự trước (NODE-LEFT-RIGHT)
NLR_TREE(x)
IF X<>NIL THEN
PRINT key(x)
NLR_TREE(Left[x])
NLR_TREE(Right[x])
0
1
4
4
5
10
8
4
Kết quả duyệt:
4
1
1
0
0
4
4
5
5
8
8
10
10
Ý tưởng:
Thăm nút gốc sau đó thăm các nút
của cây con trái rồi đến cây con phải
DUYỆT CÂY
2. Duyệt theo thứ tự giữa (LEFT-NODE-RIGHT)
LNR_TREE(x)
IF X<>NIL THEN
LNR_TREE(Left[x])
PRINT key(x)
LNR_TREE(Right[x])
0
1
4
4
5
10
8
4
Kết quả duyệt:
4
1
1
0
0
4
4
5
5
8
8
10
10
Ý tưởng:
Thăm các nút của cây con trái sau đó thăm nút gốc rồi đến cây con phải
DUYỆT CÂY
3. Duyệt theo thứ tự sau (LEFT- RIGHT- NODE)
LRN_TREE(x)
IF X<>NIL THEN
LRN_TREE(Left[x])
LRN_TREE(Right[x])
PRINT key(x)
0
1
4
4
5
10
8
4
Kết quả duyệt:
4
1
1
0
0
4
4
5
5
8
8
10
10
Ý tưởng:
Thăm các nút của cây con trái sau đó thăm đến cây con phải rồi đến nút gốc
TÌM KIẾM TRÊN CÂY
SEARCHNODE(x,k)
While x<>NIL và k<>key[x]
Do if k3. x:=left(x)
4. else
5. x:=right(x)
6. return x
13
18
44
37
88
71
99
Ý tưởng:
Cho một biến trỏ đến gốc của cây và một khoá k. Thủ tục tìm kiếm SEARCHNODE trả về một biến trỏ đến một nút có khoá k nếu như nó tồn tại, nếu không nó trỏ về NIL
23
40
15
59
55
Ví dụ: Tìm nút có khoá 55
So sánh 55 với nút gốc
55 > 44
55 < 88
55 < 59
55 = 55
Đã tìm thấy !
THÊM NÚT VÀO CÂY
Ý tưởng:
- Khi thêm một giá trị mới v vào một cây tìm kiếm nhị phân T, ta dùng thủ tục TREE-INSERT.
- Thủ tục TREE-INSERT được truyền qua một nút z , với key[z]=v, left[z]=NIL, và right[z]=NIL. Thủ tục sửa đổi T và vài trường của z theo cách thức mà z được truyền vào một vị trí thích hợp trong cây.
- Thủ tục TREE-INSERT bắt đầu tại nút gốc của cây và lần theo một lộ trình đi xuống. Biến trỏ x lần theo lộ trình, và biến trỏ y được duy trì dưới dạng cha của x. Sau khi khởi tạo dòng lặp while trong các dòng 3-7 sẽ khiến hai biến trỏ này dời xuống, đi theo con trái hay phải tùy thuộc vào phép so sánh của key[z] với key[x], cho đến khi x được ấn định là NIL. NIL là vị trí ở đó ta muốn đặt mục đầu vào z. Các dòng 8-13 ấn định các biến trỏ khiến z được chèn.
THÊM NÚT VÀO CÂY (tt)
TREE-INSERT(T,z)
1. y:=NIL
2. x:= root[T]
3. while x <> NIL
4. do y:=x
5. if key[z]6. then x :=left[x]
7. else x := right[x]
8. p[z] :=y
9. if y=NIL
10. then root[T]:= z
11. else if key[z]< key[y]
12. then left[y]:=z
13. else right[y]:=z
THÊM NÚT VÀO CÂY (tt)
13
18
44
37
88
71
99
Ví dụ:
Thêm vào cây T một nút z, với key[z]=12, left[z]=NIL, right[z]=NIL.
23
40
15
59
55
12
NIL
NIL
Nút Z
x
y
x
y
x
y
x
Nút Z được thêm vào
Bắt đầu tại nút gốc, con trỏ x đi xuống,
con trỏ y duy trì dạng cha của x
XOÁ NÚT TRÊN CÂY TKNP
1. PHẦN TỬ KẾ VỊ
Nếu tất cả các khóa điều riêng biệt, phần tử kế vị của nút x là nút có khóa nhỏ nhất lớn hơn key[x]. thủ tục dưới đây trả về phần tử kế vị của một nút x trong một cây tìm kiếm nhị phân nếu nó tồn tại, và NIL nếu x có khóa lớn nhất trong cây.
TREE-SUCCESSOR(x)
1. if right[x] <> NIL
2. then return TREE-MINIMUM(right[x])
3. else y:= p[x]
4. while y <> NIL và x=right[y]
5. do x:=y
6. y:=p[y]
7. return y
XOÁ NÚT TRÊN CÂY TKNP (tt)
13
18
44
37
88
71
99
23
40
15
59
55
Ví dụ với cây bên dưới:
Phần tử kế vị của nút có khóa 40 là nút có khóa 44.
Phần tử kế vị của nút có khóa 44 là nút có khóa 55.
XOÁ NÚT TRÊN CÂY TKNP (tt)
2. XÓA NÚT TRÊN CÂY
Thủ tục để xóa một nút z đã cho ra khỏi cây tìm kiếm nhị phân chấp nhận một biến trỏ đến z dưới dạng một đối số. Thủ tục xét ba trường hợp:
- Nếu z không có các con, ta sửa đổi cha của nó là p[z] bằng NIL.
- Nếu nút chỉ có một con đơn lẻ, ta "nối khử" z bằng cách tạo một nối kết mới giữa con của nó và cha của nó.
- Nếu nút có hai con, ta nối khử phần tử kế vị y của z, không có con trái và thay nội dung của z bằng nội dung của y.
TREE-DELETE(T,z)
1.if left[z]=NIL or right[z]=NIL
2. then y:=z
3. else y:= TREE-SUCCESSOR(z)
4.if left[y]<> NIL
5. then x := left[y]
6. else x:= right[y]
7.if x <> NIL
8. then p[x] := p[y]
9.if p[y]=NIL
10. then root[T] :=x
11. else if y=left[p[y]]
12. then left[p[y]] :=x
13. else right[p[y]] :=x
14.if y<> z
15. then key[z] :=key[y]
16.return y
XOÁ NÚT TRÊN CÂY TKNP (tt)
1-3 xác định nút y để khử
4-6 ấn định x dựa trên y
7-13 nối khử y bằng cách sửa đổi các biến trỏ trong p[y] và x
14-16 nội dung của z được dời từ y sang z
XOÁ NÚT TRÊN CÂY TKNP (tt)
13
18
44
37
88
71
99
1. TRƯỜNG HỢP Z KHÔNG CÓ NÚT CON
23
40
15
59
55
Z
NIL
Nút 15 đã được xoá!
XOÁ NÚT TRÊN CÂY TKNP(tt)
13
18
44
37
88
2. TRƯỜNG HỢP Z CÓ 1 NÚT
23
40
15
Z
Nút 88 đã được xoá!
XOÁ NÚT TRÊN CÂY TKNP (tt)
13
18
44
37
88
3. TRƯỜNG HỢP Z CÓ ĐỦ 2 NÚT CON
33
40
29
Z
Nút 18 đã được xoá!
25
y