Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 4, Phần 2: Tìm kiếm - Nguyễn Duy Hiệp
3/24/2011
Chương 4.
Tìm kiếm (tiếp)
Cây tìm kiếm nhị phân cân bằng
AVL Tree
G. M. ADELSON‐VELSKII và E. M. LANDIS
Tìm kiếm
AVL tree
Cây tìm kiếm nhị phân cân bằng – AVL tree:
Là cây tìm kiếm nhị phân
Chiều cao của cây con trái và cây con phải của gốc chênh nhau
không quá 1
Cây con trái và cây con phải cũng là các cây AVL
Đặc điểm của cấu trúc cây tìm kiếm nhị phân
Kiểu cấu trúc liên kết
Thao tác tìm kiếm, thêm, xóa thực hiện dễ dàng
Thời gian thực hiện các thao tác trong trường hợp tốt nhất
ꢀꢁlog ꢂꢃ, tồi nhất ꢀꢁꢂꢃ
12
12
12
Trường hợp tồi khi cây bị suy biến
Cây cân bằng cho thời gian thực hiện tốt nhất
21
9
21
9
21
Cải tiến cấu trúc cây tìm kiếm nhị phân để
luôn thu được thời gian thực hiện tối ưu
5
10
15
30
1
3/24/2011
AVL tree
AVL tree
Quản lý trạng thái cân bằng của cây
Thêm các nút 3, 2, 1, 4, 5, 6, 7 vào cây AVL ban đầu rỗng
Mỗi nút đưa thêm 1 thông tin là hệ số cân bằng (balance
factor) có thể nhận 3 giá trị
Xoay phải
3
3
‐2
3
2
Left_higher (hoặc ‐1)
Equal_height (hoặc 0)
Right_higher (hoặc +1)
‐1
2
2
1
3
12
1
Thêm 3
Thêm 2
Vi phạm tính
chất của cây
AVL
0
1
Hai thao tác làm thay đổi
hệ số cân bằng của nút:
Thêm nút
9
21
0
‐1
Thêm 1
15
Xóa nút
0
Xử lý bằng phép xoay nút
AVL tree
AVL tree
2
Khai báo cấu trúc 1 nút cây AVL
2
2
2
Xoay trái
2
enum Balance_factor { left_higher, equal_height, right_higher };
1
3
1
0
3
1
4
typedef struct AVLNode
{
1
4
4
3
5
int data;
Vi phạm
Thêm 4
Balance_factor balance;
struct TreeNode *leftChild;
struct TreeNode *rightChild;
} AVLNODE;
0
Thêm 5
5
Xoay giữa nút vi phạm và nút con của nó
2
3/24/2011
AVL tree
AVL tree
Xoay phải
Xoay trái
K1
K2
Vi phạm
2
K1
2
4
K2
X
Z
X
Y
Y
1
4
1
Z
5
2
Xoay trái
3
5
1
3
6
1
K2
K1
K1
6
K2
0
Thêm 6
X
Z
X
Y
Y
Z
AVL tree
AVL tree
Phép xoay đơn – single rotation:
Dùng để điều chỉnh khi mà nút mới thêm vào trong
trường hợp:
4
4
Vi phạm
5
2
(i) Cây con trái của nút con trái, hoặc
6
2
(ii)Cây con phải của nút con phải của nút
3
6
1
Thực hiện tại nút vi phạm đầu tiên trên đường từ vị trí
mới thêm trở về gốc
3
5
1
7
Xoay giữa nút vi phạm và nút con trái (xoay phải) – TH i)
(hoặc con phải (xoay trái)– TH ii)
7
Thêm 7
Sau khi xoay các nút trở nên cân bằng
3
3/24/2011
AVL tree
AVL tree
Thực hiện thêm tiếp các khóa 16, 15, 14, 13, 12, 11, 10, 8, 9
vào cây
2
4
4
Vi phạm
2
4
Nút vi phạm
đầu tiên
2
6
2
7
2
2
6
2
5
3
1
6
3
1
15
‐1
15
3
5
2
1
7
‐2
16
1
7
16
5
14
16
Vẫn vi phạm
Thêm 16
1
16
‐1
7
14
Thêm 14
15
15
0
Thêm 15
0
AVL tree
AVL tree
K1
K1
4
4
K2
K2
X
X
6
6
2
2
K3
Y
Z
Y
Z1’
Z2’
3
5
3
5
1
7
1
15
K1
K1
Hai trường hợp áp
dụng xoay kép
2. Xoay trái
16
7
16
K2
K2
X
1. Xoay phải
15
X
K3
Thêm 15
Y
Z
Y
Z1’
Z2’
4
3/24/2011
AVL tree
AVL tree
K1
K3
2
2
4
7
K1
K2
1
K2
1
2
7
4
15
X
K3
Z1’
Z2’
Y
X
Y
‐1
6
1
3
15
2
Z1’
Z2’
K1
6
14
16
K3
2
1
3
5
14
16
5
13
K1
K2
K2
1
13
X
K3
Thêm 13
Y
X
Y
Z1’
Z2’
Z1’
Z2’
AVL tree
AVL tree
Phép xoay kép – double rotation:
7
Dùng để điều chỉnh khi mà nút mới thêm vào trong
trường hợp:
(i) Cây con phải của nút con trái, hoặc
4
15
(ii)Cây con trái của nút con phải của nút
2
Thực hiện tại nút vi phạm đầu tiên trên đường từ vị trí
mới thêm trở về gốc
6
14
16
Xoay giữa nút vi phạm, nút con, và nút cháu (con của nút
con)
1
3
5
13
Xoay kép gồm 2 phép xoay trái và xoay phải
Số nút trong quá trình thực hiện xoay là 3
Thêm 12
5
3/24/2011
AVL tree
AVL tree
Thêm 11
Thêm 8
AVL tree
AVL tree
Thêm 10
Thêm 9
6
3/24/2011
AVL tree
AVL tree
Mỗi phép xoay có 2 trường hợp, khi cài đặt sẽ phải có 4
trường hợp
Trái – trái (xoay đơn)
void rotate_right(AVLNODE *&root)
{
if(root==NULL || root‐>leftChild==NULL)
//error, because it's impossible
Phải – phải (xoay đơn)
{
printf("It's must be a mistake when using this function!\n");
Trái – phải (xoay kép)
}
else
{
Phải – trái (xoay kép)
AVLNODE *pLeft = root‐>leftChild;
root‐>leftChild = pLeft‐>rightChild;
pLeft‐>rightChild = root;
root = pLeft;
Sau mỗi lần xoay, trạng thái cân bằng lại được xác lập lại
tại nút vi phạm
}
}
AVL tree
AVL tree
void left_balance(AVLNODE *&root)
//balance function for insert in left subtree
{
//2 single rotations
void rotate_left(AVLNODE *&root)
{
AVLNODE *pLeft = root‐>leftChild;
if(pLeft‐>balance == equal_height)
{
if(root==NULL || root‐>rightChild==NULL)
//error, because it's impossible
{
printf("It's must be a mistake when using this function!\n");
}
else
printf("It's must be a mistake when using this function!\n");
}
else if(pLeft‐>balance == left_higher)
//left‐left case (single rotation)
{
{
AVLNODE *pRight = root‐>rightChild;
root‐>rightChild = pRight‐>leftChild;
pRight‐>leftChild = root;
root = pRight;
root‐>balance = equal_height;
pLeft‐>balance = equal_height;
rotate_right(root);
}
else
}
}
//left‐right case (double rotation:(1)rotate left,(2)rotate right)
7
3/24/2011
{
AVLNODE *pLeftRight = root‐>leftChild‐>rightChild;
if(pLeftRight‐>balance == left_higher)
{
AVL tree
Xóa nút khỏi cây:
Chuyển bài toán xóa nút đầy đủ thành xóa nút có nhiều nhất
một con.
Xóa nút có nhiều nhất một con bị xóa làm chiều cao của
nhánh bị giảm
pLeft‐>balance = equal_height;
root‐>balance = right_higher;
}
else if(pLeftRight‐>balance == equal_height)
{
pLeft‐>balance = equal_height;
root‐>balance = equal_height;
}
else
{
Căn cứ vào trạng thái cân bằng tại các nút từ nút bị xóa trên
đường trở về gốc để cân bằng lại cây nếu cần (giống với khi
thêm một nút mới vào cây)
pLeft‐>balance = left_higher;
root‐>balance = equal_height;
}
pLeftRight‐>balance = equal_height;
rotate_left(pLeft);
root‐>leftChild = pLeft;
rotate_right(root);
}
}
AVL tree
AVL tree
Xóa nút khỏi cây:
Nếu nút cần xóa là nút đầy đủ: chuyển về xóa nút có nhiều
nhất 1 nút con
Thay thế nút cần xóa bằng nút phải nhất trên cây con trái
hoặc , nút trái nhất trên cây con phải
Copy các thông số của nút thay thế giống với thông số của
nút bị xóa thực sự
Nếu nút bị xóa là nút có 1 con: thay thế nút đó bằng nút gốc
của cây con
Chiều cao cây không đổi
Nếu nút bị xóa là nút lá: gỡ bỏ nút, gán con trỏ của nút cha
nó bằng NULL
Trường hợp 1: nút p đang ở trạng thái cân bằng (equal)
Xóa một nút của cây con trái (hoặc phải) làm cây bị lệch nhưng
chiều cao không đổi
8
3/24/2011
AVL tree
AVL tree
Trường hợp 3.1
Chiều cao cây thay đổi
Trường hợp 2: nút p đang ở trạng thái lệch trái hoặc phải
Nút bị xóa là nút của nhánh cao hơn, sau khi xóa cây trở về trạng
thái cân bằng và chiều cao của cây giảm
Chiều cao cây không đổi
AVL tree
AVL tree
Trường hợp 3: cây đang bị lệch và nút bị xóa nằm trên nhánh
thấp hơn.
Để cân bằng lại cây ta phải thực hiện các phép xoay.
Căn cứ vào tình trạng cân bằng của nút con còn lại q của p mà
ta chia thành các trường hợp nhỏ sau:
Trường hợp 3.2: nút q bị lệch trái (nếu q là con phải của
p) hoặc lệch phải (nếu q là con trái của p)
Cân bằng p bằng cách thực hiện phép xoay đơn giữa q và p
Sau khi xoay p trở về trạng thái cân bằng và chiều cao của p
bị giảm đi
Trường hợp 3.1: Nút q đang ở trạng thái cân bằng
Thực hiện phép xoay đơn (xoay trái hoặc xoay phải)
Sau khi xoay, p trở về trạng thái cân bằng
9
3/24/2011
AVL tree
AVL tree
Chiều cao cây thay đổi
Chiều cao cây thay đổi
AVL tree
AVL tree
Trường hợp 3.3: nút q bị lệch cùng phía với nhánh bị xóa.
Nếu nhánh bị xóa là nhánh trái của p thì q bị lệch trái và
ngược lại
7
4
15
Để tái cân bằng cho p ta phải thực hiện 2 phép xoay giữa nút
con của q, nút q, và nút p
Sau khi xoay, chiều cao của cây giảm đi, p trở về trạng thái cân
bằng
2
6
14
16
1
3
13
Xóa một trong các nút 4, 7, 15 trên cây AVL
10
3/24/2011
Cấy trúc tự điều chỉnh
Trong nhiều bài toán chúng ta cần một cấu trúc xử lý hiệu
quả với những truy cập có số lượng lớn trên các bản ghi
mới đưa vào.
Ví dụ: bài toán quản lý thông tin bệnh nhân tại bệnh viện
Bệnh nhân ra khỏi bệnh viện thì có số lần truy cập thông tin ít
hơn
Question
Bệnh nhân mới vào viện thì sẽ có số lượng truy cập thông tin
thường xuyên
Ta cần cấu trúc mà có thể tự điều chỉnh để đưa những bản ghi
mới thêm vào ở gần gốc để cho việc truy cập thường xuyên dễ
dàng.
Cây splay
Splay tree
Là cây tìm kiếm nhị phân
Mỗi khi truy cập vào một nút trên cây (thêm, hoặc xóa) thì nút
mới truy nhập sẽ được tự động chuyển thành gốc của cây mới
Các nút được truy cập thường xuyên sẽ ở gần gốc
Các nút ít được truy cập sẽ bị đẩy xa dần gốc
Splay tree
Cấu trúc tự điều chỉnh
Để dịch chuyển các nút ta dùng các phép xoay giống với trong
AVL tree
Các nút nằm trên đường đi từ gốc đến nút mới truy cập sẽ chịu
ảnh hưởng của các phép xoay
11
3/24/2011
Cây splay
Cây splay
Nhắc lại về các phép xoay
Trường hợp chỉ dùng phép xoay đơn để điều chỉnh nút
Xoay đơn – single rotation:
Nút cha xuống thấp 1 mức và nút con lên 1 mức
25
9
21
6
25
‐2
3
2
15
9
4
21
18
‐1
2
1
3
6
18
15
0
1
4
Cây splay
Cây splay
Xoay kép – double rotation:
gồm 2 phép xoay đơn liên tiếp.
Nút tăng lên 1 mức, còn các nút còn lại lên hoặc giảm xuống
nhiều nhất 1 mức
Nhận xét:
Nút mới truy cập (nút 9) được chuyển thành nút gốc của cây
mới
Tuy nhiên nút 18 lại bị đẩu xuống vị trí của nút 9 trước
Như vậy:
7
Truy cập tới 1 nút sẽ đẩy các nút khác xuống sâu hơn.
Tốc độ của nút bị truy cập được cải thiện nhưng không cải
thiện tốc độ truy cập của các nút khác trên đường truy cập
15
16
Thời gian truy cập với ꢄ nút liên tiếp vẫn là ꢀꢁꢄ ∗ ꢂꢃ
7
16
Ý tưởng dùng chỉ phép xoay đơn để biến đổi cây là không đủ
tốt
15
12
3/24/2011
Cây splay
Cây splay
Ý tưởng mới:
Tại mỗi bước ta di chuyển nút liền 2 mức
Xét các nút trên đường đi từ gốc đến nút mới truy nhập
Nếu ta di chuyển trái (từ gốc xuống), ta gọi là Zig
Ngược lại, di chuyển phải ta gọi là Zag
T1
T4
21
21
21
21
21
21
T2
T3
T3
T4
T1
T2
15
15
15
27
27
27
Trường hợp Zig‐Zig
Zag
Zig
6
17
Zig‐Zag
23
Zag‐Zig
34
Zag‐Zag
Zig‐Zig
Cây splay
Cây splay
Dịch chuyển:
Nếu nút đang xét nằm ở mức sâu hơn hoặc bằng 2 ta dịch chuyển
2 mức mỗi lần
Nếu nút ở mức 1: ta chỉ dịch chuyển 1 mức (trường hợp Zig hoặc
Zag)
T4
T1
T4
T2
T3
T3
T1
T3
T1
T2
Trường hợp Zag‐Zig
T1
T2
T2
T3
Trường hợp Zig
13
3/24/2011
Cây splay
Cây splay
Chú ý: trường hợp Zig‐Zig (hoặc Zag‐Zag) khác hoàn toàn với
trường hợp dùng hai phép xoay đơn liên tiếp
Nhận xét về cây splay:
Cây không cân bằng (thường bị lệch)
Các thao tác có thời gian thực hiện khác nhau từ O(1) tới O(n)
Thời gian thực hiện trung bình của một thao tác trong một
chuỗi thao tác là ꢀꢁlog ꢂꢃ
Thực hiện giống như cây AVL nhưng không cần quản lý thông
tin về trạng thái cân bằng của các nút
T1
T4
T4
T3
Nếu dùng 2 phép xoay đơn
T2
T1
T2
T3
Cây splay
Thực hiện splay tại nút 23
45
21
73
15
37
6
35
40
Cây 2‐3
25
23
27
14
3/24/2011
Cây 2‐3
Cây 2‐3
Đảm bảo cây luôn luôn cân bằng
Chi phí thực hiện các thao tác luôn là ꢀꢁlog ꢂꢃ
Nút trong có 3 con – nút 3
Nút chứa 2 phần tử
Có 3 nút con
Cây 2‐3:
Mỗi nút trong có 2 tới 3 nút con
Nút lá có 1 tới 2 giá trị
p
q
x < p
x >q
Dữ liệu được lưu trên nút lá hoặc nút trong
ĐÂY KHÔNG PHẢI CÂY NHỊ PHÂN
Trạng thái cân bằng của cây được duy trì dễ dàng hơn so với
p< x <q
Giá trị khóa
tìm kiếm
nhỏ hơn p
Giá trị khóa
tìm kiếm
lớn hơn q
Giá trị khóa
tìm kiếm
lớn hơn p
nhỏ hơn q
cây AVL
Cây 2‐3
Cây 2‐3
Nút trong có 2 con – nút 2
Nút chứa 1 phần tử
Có 2 nút con
34 57
p
24
37 45
42
59 67
x < p
x > p
12
27 32
35
47 52
Giá trị khóa
tìm kiếm
Giá trị khóa
tìm kiếm
nhỏ hơn p
lớn hơn p
15
3/24/2011
Cây 2‐3
Cây 2‐3
Định nghĩa cấu trúc 1 nút
34 57
struct TreeNode
{
24
37 45
42
59 67
DATA_TYPE smallItem, largeItem;
struct TreeNode *left, *middle, *right;
struct TreeNode *parent; //to make your life easier
}
12
27 32
35
47 52
Duyệt cây theo thứ tự giữa:
12, 24, 27, 32, 34, 35, 37, 42, 45, 47, 52, 57, 59, 67
Cây 2‐3
Cây 2‐3
Duyệt cây theo thứ tự giữa – in‐order traversal
(1) Duyệt cây con trái
(2) Xử lý nội dung khóa nhỏ hơn tại nút
(3) Duyệt cây con giữa
(4) Xử lý nội dung khóa lớn hơn tại nút
(5) Duyệt cây con phải
Tìm kiếm
Nếu nút hiện tại rỗng không tìm thấy
Nếu giá trị tìm kiếm k xuất hiện trên nút hiện tại tìm thấy
Nếu k< giá trị khóa nhỏ hơn tìm tiếp tại cây con trái
Nếu khóa nhỏ hơn< k< khóa lớn hơn tìm tại cây con giữa
Ngược lại tìm tại cây con phải
2
4
37 45
3
5
1
16
3/24/2011
Cây 2‐3
Cây 2‐3
Thêm 29
Thêm nút
24
24
Phần tử mới được thêm vào tại nút lá của cây
Nếu nút lá sau khi thêm có 3 phần tử ta phải thực hiện thao
tác tách nút
12
27 32
12
27 29 32
Khi tách nút, khóa giữa bị đẩy lên nút cha
Tách nút tại nút lá có thể dẫn đến tách nút tại nút trong
Tách nút
24 29
Tách nút:
• Khóa ở giữa bị đẩy lên nút
cha
• Nút hiện tại bị tách thành 2
12
27
32
nút con
Cây 2‐3
Cây 2‐3
34 57
Thêm 19
24
24
24
37 45
42
59 67
12
27 32
12 19
27 32
12
27 32
35
47 52
Không phải tách nút
Thêm nút 50 ?
17
3/24/2011
Cây 2‐3
Cây 2‐3
Thêm nút 50
Thêm nút 50
Vi phạm
34 57
34 45 57
24
37 45
42
59 67
24
37
50
59 67
12
27 32
35
47 50 52
12
27 32
35
42
47
52
Vi phạm
Cây 2‐3
Cây 2‐3
45
Thêm nút 50
Thêm nút 50
34
57
34 57
Vi phạm
24
37
50
59 67
24
37 45 50
59 67
12
27 32
35
42
47
52
12
27 32
35
42
47
52
Tách tại nút gốc
18
3/24/2011
Cây 2‐3
Cây 2‐3
Xóa nút lá
45
Nếu nút lá sau khi xóa vẫn còn phần tử kết thúc
Ngược lại ta phải dịch chuyển phần tử từ nút anh em
của nó, hoặc từ nút cha của nó
34
57
(i) Nếu nút anh em của nó có 2 phần tử thì dịch một phần
tử sang nút hiện tại
(ii) Nếu không thực hiện dịch được thì ta sẽ thực hiện kết
hợp (điều này có thể dẫn đến giảm chiều cao của cây)
24
37
50
59 67
12
27 32
35
42
47
52
Vẽ cây thu được sau khi thêm lần lượt các khóa
5, 7, 29, 31, 70, 75 vào cây trên
Cây 2‐3
Cây 2‐3
Xóa nút:
Xóa 27 (trường hợp nút lá sau khi xóa vẫn còn phần tử)
Nếu phần tử bị xóa ở trên nút trong:
Phải chuyển phần tử đó về nút lá để xóa
Thay thế bằng nút kế tiếp trong duyệt theo thứ tự giữa
24
24
37 45
42
42 45
37
12
27 32
12
32
35
47 52
35
47 52
Xóa 37, ta thay bằng 42
19
3/24/2011
Cây 2‐3
Cây 2‐3
Xóa 35 : trường hợp (i)
Xóa 37: trường hợp (ii)
42 47
45
47
37 45
42 47
37
52
35
42
47 52
37
45
52
42 45
52
Cây 2‐3
Cây 2‐3
Xóa 52: trường hợp (ii)
Xóa 12: trường hợp (ii)
34
42
42 47
24
42 47
45
37
45
52
37
45 47
12
32
37
52
20
Tải về để xem bản đầy đủ
22 trang
17360
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 4, Phần 2: Tìm kiếm - Nguyễn Duy Hiệp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_thuat_toan_phan_1_gioi_thieu_v.pdf
