ĐẠI HỌC QUỐC GIA HÀ NỘI
KHOA CÔNG NGHỆ
Trần Thị Ngọc Hà
TỐI ƯU HOÁ LỚP CÁC THÔNG TIN CÓ CẤU
TRÚC DẠNG CÂY NHỊ NGUYÊN 1 VÀ N CHIỀU
VỚI THÔNG TIN CHỨA Ở LÁ TRÊN TẬP KHÓA
HỮU HẠN BẰNG MÔ HÌNH XỬ LÝ SONG SONG
LUẬN VĂN THẠC SĨ
Hà Nội - Năm 2004
Luận văn tốt nghiệp
Contents
MỤC LỤC
LỜI GIỚI THIỆU .............................................................................. 1
Chương l: ......................................................................................... 4
THUẬT TOÁN PHÂN RÃ LỚP THÔNG TIN CÓ CẤU TRÚC DẠNG
CÂYNHỊ PHÂN MỘT CHIỀU VỚI THÔNG TIN CHỨA Ở LÁ TRÊN
TẬP KHÓA HỮU HẠN ...................................................................... 4
1. Định nghĩa cây nhị phân một chiều với thông tin chứa Ở lá. ......................... 4
2. Hệ tiên dề và các quy tắc dẫn xuất trên TREE. ............................................. 6
2.1 Quy tắc dẫn xuất của TREE. ................................................................. 6
2.2 Hệ tiên đề của TREE trên tập khóa hữu hạn Ki(i=l, 2, ..., n-l). ........... 6
3. Cây chuẩn tắc một chiều trên tập khóa K. ................................................... 11
1.4 Bảng mã của cây trên tập khóa K. ...................................................... 23
1.5 Cây tối ưu một chiều trên tập khóa K. ............................................... 24
1.6 Thuật toán phân rã tìm cây nhị phân tối ưu trên tập khóa hữu hạn
K. ................................................................................................................ 26
1.7 Ví dụ minh hoạ. .................................................................................... 30
Chương 2 ........................................................................................ 38
THUẬT TOÁN PHÂN RÃ LỚP THÔNG TIN CÓ CẤU TRÚC DẠNG CÂY
NHỊ PHÂN N CHIỀU VỚI THÔNG TIN CHỨA Ở LÁ TRÊN TẬP KHÓA
HỮU HẠN ..................................................................................... 38
2.1 Cây nhị phân n-chiều với thông tin chứa ở lá. .................................. 38
2.2 Hệ tiên đề và các quy tắc dẫn xuất trên TREE(n). ..................................... 40
2.2.1 Qui tắc dẫn xuất của TREE(n). ........................................................ 40
2.2.2 Hệ tiên đề của TREE(N) trên tập khóa hữu hạn Ki(n)(i=l, 2, ...,m).
.................................................................................................................... 40
Trang 89
Luận văn tốt nghiệp
2.3 Dạng chuẩn tắc của cây nhị phân n-chiều. ................................................. 48
2.4 Bảng mã của cây n-chiều trên tập khóa K(n). ............................................ 72
2.5 Cây nhị phân n- chiều tối ưu. .................................................................... 73
2.6 Thuật toán phân rã xây dựng cây n-chiều tối ưu trên tập khóa hữu hạn K(n).
....................................................................................................................... 74
2.6.1 Thuật toán chuyển về cây n-chiều chuẩn tắc trên tập khoá hữu hạn
Ki(n)(i=l, 2,..., m) (Thuật toán 2.l). ............................................................ 74
2.6.2 Thuật toán nối các cây n-chiều chuẩn tắc Nin (Ki(n))T(i=l, ...,m)
thành cây n-chiều chuẩn tắc Nn (K(n))T (Thuật toán 2.2). ................... 74
2.6.3 Thuật toán phân rã tập khóa K(n) thành m tập con Kl(n), K2(n), ...,
Km(n) (Thuật toán 2.3) ............................................................................... 75
2.6.4 Thuật toán chuyển về cây n -chiều tối ưu (Thuật toán 2.4). ........... 76
2.6.5 Thuật toán phân rã xây dựng cây n-chiều tối ưu trên tập khóa
K(n). ............................................................................................................ 76
2.7 Ví dụ minh hoạ. ........................................................................................ 77
2.7.1 Ví dụ mô phỏng thuật toán chuyển về cây 2-chiều chuẩn tắc trên
tập khóa hữu hạn Ki(2) (thuật toán 2.l). ................................................... 77
2.2.7 Ví dụ mô phỏng thuật toán nối các cây chuẩn tắc Ni2 (Ki( 2))T
thành cây chuẩn tắc N2 (K(2))T (Thuật toán 2.3). .............................. 78
2.7.3 Ví dụ mô phỏng thuật toán chuyển cây 2 - chiều chuẩn tắc của T về
cây tối ưu ( thuật toán 2.5) ........................................................................ 80
KẾT LUẬN ..................................................................................... 85
TÀI LIỆU THAM KHẢO: ................................................................ 87
PHỤ LỤC ....................................................................................... 88
Trang 90
Luận văn tốt nghiệp
LỜI GIỚI THIỆU
Khái niệm cây tìm kiếm nhị phân đóng vai trò rất quan trọng trong cấu trúc
dữ liệu và trong lý thuyết thuật toán. Tuy nhiên, để khai thác tối đa ưu điểm của
cây tìm kiếm nhị phân thì nhất thiết ta phải lưu trữ thông tin trên cây tìm kiếm
nhị phân tối ưu (tức cây nhị phân có số đỉnh và độ cao nhỏ nhất trong tất cả các
cây tương đương với nó). Hơn thế nữa, sau một thời gian sử dụng thì thông tin
lưu trữ trên cây sẽ bị lạc hậu, khi đó ta phải đánh giá và tổ chức lại chúng, các
thông tin lạc hậu sẽ bị loại bỏ. Như vậy, nhu cầu xây dựng cây nhị phân tối ưu
luôn được đặt ra. Vấn đề đặt ra là làm thế nào để xây dựng cây nhị phân tối ưu?
Đã có nhiều thuật toán xây dựng cây nhị phân tối ưu, tuy nhiên, các thuật toán
này hoạt động dựa trên việc xét duyệt trên toàn bộ tập khóa, chính vì vậy khi tập
khóa quá lớn nhất là khi tập khóa là vô hạn thì thời gian thực hiện thuật toán là
rất lớn. Để khắc phục nhược điểm trên, trong luận văn này, ta áp dụng thuật toán
phân rã để tìm cây nhị phân tối ưu và lưu trữ các thông tin đã được phân loại
trong cây tối ưu đó. Thuật toán phân rã dựa trên việc chia nhỏ tập khóa hữu hạn
ban đầu thành n tập khóa con (n tập hữu hạn). Sau đó áp dụng phương pháp tiên
đề của H.Thiele để tìm cây nhị phân chuẩn tắc trên từng tập con đó. Công việc
này có thể tiến hành đồng thời trên tất cả các tập khóa con vì vậy nó sẽ làm giảm
đáng kể thời gian thực hiện thuật toán so với việc thực hiện thuật toán trên toàn
tập khóa ban đầu. Tiếp theo, ta ghép nối các cây chuẩn tắc của từng tập con theo
quy luật các khóa có giá trị tăng dần ta được cây chuẩn tắc trên toàn tập khóa ban
đầu. Từ đó dùng thuật toán bẻ đôi cây chuẩn tắc ta được cây nhị phân tối ưu trên
toàn tập khóa ban đầu. Thuật toán phân rã hoàn toàn không làm mất thông tin có
ích, Cây nhị phân tối ưu thu được bằng thuật toán phân rã hoàn toàn giống với
cây tối ưu thu được khi thực hiện trên toàn tập khóa ban đầu.
Một vấn đề nữa đặt ra là: với cấu trúc cây nhị phân n-chiều thì liệu các kết
quả trên có còn đúng không? Để trả lời câu hỏi này chúng tôi đã tổng quát hoá
Trang 1
Luận văn tốt nghiệp
bài toán trên cho cấu trúc cây nhị phân n-chiều. Tuy nhiên, cho đến nay, em mới
chỉ giải quyết xong bài toán với cấu trúc cây nhị phân n-chiều với thông tin chứa
ở lá. Điều thú vị là khi thay n = 1 ta thu lại được hoàn toàn những kết quả đã
nghiên cứu với cấu trúc cây nhị phân một chiều với thông tin chứa ở lá.
Luận văn gồm các chƣơng sau:
Chƣơng 1: Thuật toán phân rã lớp thông tin có cấu trúc dạng cây nhị phân một
chiều với thông tin chứa ở lá trên tập khóa hữu hạn.
- Xây dựng các khái niệm: Cây nhị phân một chiều với thông tin chứa ở lá, hàm
kết quả, sự tương đương giữa các cây nhị phân một chiều, dạng chuẩn của cây
nhị phân một chiều, bảng mã của cây nhị phân, cây nhị phân một chiều tối ưu.
Các qui tắc dẫn xuất và hệ tiên đề của cây nhị phân một chiều.
- Các tính chất tương đương giữa các cây nhị phân một chiều, của dạng chuẩn
tắc, của cây tối ưu và các bổ đề, các định lý cho phép kiểm tra tính tương
đương giữa các cây nhị phân, biến đổi tương đương giữa các cây nhị phân.
- Thuật toán chuyển về cây nhị phân một chiều chuẩn tắc, thuật toán nối các
cây nhị phân một chiều chuẩn tắc, phân hoạch tập khóa ban đầu K thành n tập
khóa con
- Thuật toán chuyển về cây nhị phân một chiều tối ưu.
- Thuật toán phân rã xây dựng cây nhị phân một chiều tối ưu.
- Các ví dụ minh hoạ.
Chƣơng 2: Thuật toán phân rã lớp thông tin có cấu trúc dạng cây nhị phân nchiều với thông tin chứa Ở lá trên tập khóa hữu hạn.
- Xây dựng các khái niệm về: cây nhị phân n-chiều với thông tin chứa Ở lá,
hàm kết quả, sự tương đương giữa các cây nhị phân n-chiều, dạng chuẩn của
cây nhị phân n- chiều, cây nhị phân n-chiều tối ưu. Các qui tắc dẫn xuất và hệ
tiên đề của cây nhị phân n-chiều.
Trang 2
Luận văn tốt nghiệp
- Các tính chất tương đương giữa các cây nhị phân n-chiều, của dạng chuẩn tắc,
của cây tối ưu và các bổ đề, các định lý cho phép kiểm tra tính tương đương
giữa các cây nhị phân n-chiều, biến đổi tương đương giữa các cây nhị phân nchiều.
- Thuật toán chuyển về cây nhị phân n-chiều chuẩn tắc, thuật toán nối các cây
nhị phân n-chiều chuẩn tắc tắc, phân hoạch tập khóa ban đầu K(n) thành in tập
con Kl(n), K2(n), ..., Kn(n), thuật toán chuyển về cây nhị phân n-chiều tối ưu.
- Thuật toán phân rã xây dựng cây nhị phân n-chiều tối ưu.
- Các ví dụ minh hoạ.
Kết luận: Tóm tắt lại những kết quả thu được của luận văn này.
Tài liệu tham khảo.
Phụ lục: Cài đặt chương trình mô phỏng thuật toán xây dựng cây nhị phân một
chiều tối ưu cho lớp các thông tin có cấu trúc dạng cây nhị phân một chiều với
thông tin chứa ở lá.
Trang 3
Luận văn tốt nghiệp
Chương l:
THUẬT TOÁN PHÂN RÃ LỚP THÔNG TIN CÓ CẤU TRÚC DẠNG CÂY
NHỊ PHÂN MỘT CHIỀU VỚI THÔNG TIN CHỨA Ở LÁ TRÊN TẬP
KHÓA HỮU HẠN
Nội dung của chương này gồm:
- Các định nghĩa về: cây nhị phân một chiều với thông tin chứa Ở lá, hàm kết
quả, sự tương đương giữa các cây nhị phân một chiều, dạng chuẩn của cây nhị
phân một chiều, bảng mã của cây nhị phân, cây nhị phân một chiều tối ưu. Các
qui tắc dẫn xuất và hệ tiên đề của cây nhị phân một chiều.
- Các tính chất tương đương giữa các cây nhị phân một chiều, của dạng chuẩn tắc
và các bổ đề, các định lý cho phép kiểm tra tính tương đương giữa các cây nhị
phân, biến đổi tương đương giữa các cây nhị phân.
- Thuật toán chuyển về cây nhị phân một chiều chuẩn tắc trên tập khóa hữu hạn,
- Thuật toán nối các cây nhị phân một chiều chuẩn tắc, phân hoạch tập khóa ban
đầu K thành n tập con K1, K2, ...Kn
- Thuật toán chuyển về cây nhị phân một chiều tối ưu.
- Thuật toán phân rã xây dựng cây nhị phân một chiều tối ưu.
- Các ví dụ minh họa các thuật toán.
1. Định nghĩa cây nhị phân một chiều với thông tin chứa Ở lá.
Giả sử D là tập không rỗng các Documents nào đó và mỗi phần tử của nó
ta gọi là một thông tin, D được gọi là tập các thông tin. Tập K là tập hữu hạn các
phần tử mà trên đó thỏa mãn quan hệ so sánh (tức là với mọi x, y
y hoặc x
K ta có : x >
y). Không mất tính tổng quát ta xem K là tập các số tự nhiên. K được
gọi là tập khóa của các cây nhị phân.
Ta kí hiệu là cây rỗng và ta đặt D+ = D
Giả sử các kí hiệu [ ] < > , D+
{ }.
K.
Trang 4
Luận văn tốt nghiệp
Định nghĩa l.1 (Định nghĩa đệ qui cây nhị phân một chiều với thông tin chứa
ở lá)
a. Mỗi phần tử d
D gọi là một cây.
b. Nếu T1, T2 là hai cây và k
K, thì dãy kí hiệu k cũng là một cây.
Dạng đồ thị của cây d như sau:
k
T1
T2
Tập tất cả các cây định nghĩa như trên ta kí hiệu qua TREE và gọi là tập
các cây nhị phân một chiều với thông tin chứa ở lá trên tập khóa K (gọi tắt là câ y
nhị phân).K là tập khoá của TREE. Mỗi đỉnh có khoá k được gọi là đỉnh trong
của cây. Thông tin được chứa ở đỉnh ngoài ( tức là đỉnh không chứa khoá) còn
gọi là lá. T 1 là cây con bên trái, T 2 là cây con bên phải.
Định nghĩa 1.2 (Định nghĩa hàm đánh giá hay hàm kết quả)
Ta kí hiệu " " "
" để chỉ sự đồng nhất bằng nhau(không đồng nhất bằng
nhau) giữa các cây nhị phân. Giả sử T là một cây nhị phân và l
K. Ta định
nghĩa hàm kết quả f từ tập TREE K vào D theo định nghĩa đệ quy của T như sau:
a. Nếu cây nhị phân T
d
D thì f(T,l) = f(d,1) = d với mọi l
b. Nếu cây nhị phân T
k thì :
f(T1,l) nếu 1
K.
k
f(T,1) = f(k,l) =
f(T2) nếu 1 > k
Định nghĩa 1.3 (Định nghĩa sự tương đương giữa hai cây nhị phân)
Giả sử T1 , T2
TREE. Ta nói T 1 là tương đương với T 2 trên K( Kí hiệu T 1
(K) T2 ) khi và chỉ khi: f(T 1, l) = f(T2, l) với mọi 1 K.
Từ định nghĩa trên ta thấy rằng: T 1 không tương đương với T 2 trên K (Ký
hiệuT1
(K) T2) khi và chỉ khi tồn tại một khóa l0
Trang 5
K sao cho f(T 1, l0)
f(T2, l0)
Luận văn tốt nghiệp
2. Hệ tiên dề và các quy tắc dẫn xuất trên TREE.
2.1 Quy tắc dẫn xuất của TREE.
Trước hết ta đưa vào khái niệm phương trình cây:
Giả sử T1, T2
TREE và "=" là một kí hiệu không thuộc tập K
D+
{
[,],<,>} . Khi đó dãy kí hiệu T l = T2 gọi là một phương trình cây.
Đặt EQU : {T1 = T2 | T1,T2
TREE}. EQU được gọi là tập tất cả những phương
trình cây trên TREE. Giả sử X
EQU và Tl= T2
EQU.
Định nghĩa 1.4 (Định nghĩa dẫn được)
Phương trình cây T 1 = T2 là dẫn được từ X( kí hiệu X ├ T1 = T2) khi và chỉ khi
T1= T2
X hoặc T1 = T2 dẫn được từ các phần tử trong X bằng cách áp dụng
một số hữu hạn lần các qui tắc dẫn xuất sau :
Quy tắc 1 (R1): X ├ T =T với mọi T
TREE.
Quy tắc 2 (R2): Nếu X ├ T1= T2 thì X ├ T2= T1.
Quy tắc 3 (R3): Nếu X ├ T1= T2 và X ├ T2 = T3 thì X ├ T1= T3
Quy tắc 4 (R4): Nếu X ├ T1= T1' thì X ├ k = k < T1', T2>
Quy tắc 5 (R5): Nếu X ├ T2=T2' thì X ├ k = k < T1, T2'>
2.2 Hệ tiên đề của TREE trên tập khóa hữu hạn Ki (i=l, 2, ..., n-l).
Do Ki hữu hạn nên trong Ki tồn tại phần tử bé nhất và phần tử lớn nhất mà ta kí
hiệu tương ứng là k imin , kimax
Hệ tiên đề của TREE trên tập khóa hữu hạn Ki là tập các phương trình cây sau:
Tiên đề axi1: k, T3> = k là một tiên đề nếu
kimin
k < k’
kimax .
Dạng đồ thị:
k
k’
T1
=
T3
T2
Trang 6
k
T1
T3
Luận văn tốt nghiệp
Tiên đề axi2: k < k' , T3 > = k' > là một tiên
đề nếu kimin
k’ < k
kimax .
Dạng đồ thị:
k
k’
T1
=
T3
k’
T1
T2
k
T2
T3
Tiên đề axi3: k < T1, k' > = k là một tiên đề nếu
kimin
k
k’
kimax . Dạng đồ thị:
k
=
k’
T1
T2
Tiên đề axi4 :
k
T1
T3
k = T là một tiên đề với mọi T
Dạng đồ thị:
k
=
T
T3
TREE và k
T
T
Tiên đề axi5: k < T1, k' > = k’ là một tiên đề nếu
kimin
k < k’
kimax . Dạng đồ thị:
k
=
k’
T1
T1
k’
T1
T2
T2
Tiên đề axi6(tiên đề max) k = T1 là một tiên đề nếu k > kimax
Dạng đồ thị:
k
T1
=
T2
Trang 7
T1
Ki
Luận văn tốt nghiệp
Tiên đề axi7(tiên đề min) k = T2 là một tiên đề nếu k < kimin
Dạng đồ thị:
k
=
T2
T1
T2
Đặt AXi = {axi1 , axi2 , axi3 , axi4 , axi5 , axi6 , axi7} và gọi AXi là hệ tiên đề trên
tập khoá hữu hạn Ki (i= 1, ..., n-l).
Một cách tổng quát, trong cây T l ta có thể thay cây con T 0 bởi cây T00 , Khi
đó, ta sẽ được cây T 2 (ký hiệu T1T0T00T2). Như vậy, ký hiệu T 1T0T00T2 có nghĩa
là T2 nhận được từ T l bằng cách thay cây con T 0 của Tl bởi T00
Giả sử X
EQU ta có bổ đề sau:
Bổ đề l.l: Nếu Tl , T0, T00 , T2
TREE, T1T0T00T2 và X ├ T0 = T00 thì X ├ T1 =
T2
Thật vậy, ta sẽ chứng minh bổ đề 1 . 1 theo quy nạp từ định nghĩa 1 . 1 ta có các
trường hợp sau:
Trường hợp l: Nếu Tl
d Khi đó T l = T0 T00
T2 d
Hiển nhiên là X ├ T1 = T2
Trường hợp 2: Nếu Tl
k < Tll, T12> , Khi đó ta có các trường hợp sau:
Nếu Tl
T2 thì bổ đề hiển nhiên đúng.
Nếu Tl
T0 và T00
Nếu Tl
T2 , Tl T0 và T00
T2 Theo giả thiết ta có X ├ T0 = T00
X ├ T1 = T2
T2 giả sử ta đã có T 21 , T22 thoả mãn
X ├ T11 = T21 (l) , X ├ T12= T22 (2) và T11T0T00T21 , T12T0T00T22 Ta cần chứng
minh X ├ T1 = T2 Dễ thấy: T2
k < T21, T22> Từ ( 1 ) , áp dụng quy tắc
R4 ta có X ├ k = k < T21 ,T22> (3).
áp dụng R5 ta có : X ├ k = k < T21 ,T22> (4) .
Từ (3) và (4) áp dụng R 3 ta có: X ├ k = k < T21 ,T22> hay X ├ T1 = T2
Bổ đề 1.1 đã được chứng minh.
Định lý l.l: Giả sử T1, T2
TREE, nếu AX ├ T1 = T2 thì T1
Trang 8
(K)T2
Luận văn tốt nghiệp
Thật vậy ta chứng minh định lý 1.1 bằng qui nạp theo chiều dài dẫn xuất của cây
.
Ta có các trường hợp sau:
+ Nếu Tl = T2 là axl, khi đó ta có: T l
T2
k <[k' < Tll, T21>, T31> và
k với k < k'. Với mọi l
K ta có các trường hợp sau:
Nếu l k < k' ta có:
f(Tl, l) = f(k <[k' , T31>, l ) = f( k', , l ) = f(T ll, l)
và f(T2, l) = f(k < T 21 , T3l>, l ) = f(T ll, l).
Vậy ta có f(T l , l)
f(T2, l) với mọi l
K thỏa mãn l k < k'.
Nếu k < l k' ta có:
f(Tl, 1 ) = f( k <[k' , T31>, l ) = f(T2l, l).
f(T2, 1 ) = f( k , 1 )= f(T31, 1 ) .
vậy ta có f(T l , 1 ) = f(T2, l ) với mọi l
K thỏa mãn k’ < l k'.
Nếu l > k' ta có:
f(Tl, l) = f(k <[k', , T31>, l ) = f(T 3l, l).
f(T2, l ) = f(k , l ) = f(T 31, l ).
vậy ta có f(T l, l ) = f(T2 ,1 ) với mọi l
K thỏa mãn l > k'.
Vậy ta có f(T l, l ) = f(T2, l ) Với mọi l
K nếu Tl
+ Nếu Tl = T2 là ax2 , khi đó ta có: T l
k < k', , T31> và
T2
k' > với k > k'. Với mọi l
Nếu l
T2 là axl.
K ta có các trường hợp sau:
k'< k ta có:
f(T1, l) = f( k < k' ,T31>, l ) = f( k' , l) = f(T ll , l >
f(T2, l ) = f( k' > , l ) = f(T ll, l ).
Vậy ta có f(T l, l ) = f(T2 , l ) với mọi l
Nếu k'< l
K thỏa mãn l
k ta có:
f(Tl, l) = f( k' , l ) = f(T 21, l).
Trang 9
k'< k.
Luận văn tốt nghiệp
f(T2 , l) = f( k , l ) = f(T 21 , l) .
Vậy ta có f(T l, l ) = f(T 2, l ) Với mọi l
K thỏa mãn k' < l
k.
Nếu l > k ta có:
f(Tl, l) = f(T31, l)
và f(T2 , l) = f(k , l) = f(T31, l).
vậy ta có f(T l , l) = f(T2, l) với mọi l
K thỏa mãn l > k.
Vậy ta có f(T l , l) = f(T2 , l) với mọi l
K nếu T1 = T2 là ax2
+ Nếu Tl = T2 là ax3, khi đó ta có: T 1
k > và
T2
k Với k
Nếu l
k'
k'. Với mọi l
K ta có các trường hợp sau:
k ta có:
f(Tl , l ) = f(Tl1 , l ) và f(T2 , l) = f(Tl1 , l) .
Vậy ta có f(T l , l) = f(T2, l) Với mọi l
Nếu k' < l
K thỏa mãn l
k'
k.
K thỏa mãn k'< 1
k.
k ta có:
f(Tl , l) = f(Tl1 , 1 ) và f(T2 , l) = f(Tl1 , l). .
Vậy ta có f(T l, l) = f(T2 , l) Với mọi l
Nếu l > k ta có:
f(Tl, l) = f( k', , l) = f(T 31, l)
và f(T2 , l) = f(T31 , l).
vậy ta có f(Tl, l) = f(T2 , l) với mọi l
Vậy ta có f(T l , l) = f(T2 , l) Với mọi l
+ Nếu Tl = T2 là ax4 , khi đó ta có:T 1
Với mọi l
K thỏa mãn l > k.
K nếu Tl = T2 là ax3
k và T2
Tll với k > kmax
K ta có: f(T l, l) = f(Tll, l) = f(T2 ,l) (Vì l
kmax < k).
Vậy ta có f(T l, l) = f(T2 , l) với mọi l
K nếu Tl = T2 là ax4
+ Nếu Tl = T2 là ax5 khi đó ta có:T l
k và T2 T12 với k < kmin
Với mọi l
K ta có: f(Tl, l) = f(T12 , l ) = f(T2 , l) (vì k < kmin
Vậy ta có f(T l, l) = f(T2 , l) với mọi l
K nếu Tl = T2 là ax5
Trang 10
l)
Luận văn tốt nghiệp
Ngoài ra để chứng minh tính đúng đắn của định lý 1 ta cần chứng minh thêm
rằng: các quy tắc dẫn xuất cũng bảo đảm tính tương đương. Thật vậy:
Quy tắc l(Rl): X ├ T1 = T1 với mọi T1
f(Tl, l) = f(Tl, l) với mọi l
TREE(n), hiển nhiên ta có:
K.
Quy tắc 2(R2): Nếu X ├ T1 = T2 thì X ├ T2 = T1 , hiển nhiên ta có:
f(Tl , l) = f(T2 , l) Với mọi l
K.
Quy tắc 3(R3): Nếu X ├ T1 = T2 và X ├ T2 = T3 thì X ├ T1 = T3
hiển nhiên ta có: f(Tl, l) = f(T2, l) và f(T 2 , l) = f(T3 , l)
với mọi l
f(Tl, l) = f(T3 , l)
K.
Quy tắc 4(R4): Nếu X ├ T1 = T1’ (*) thì X ├ k = k
Ta chứng minh f(k , l) = f(k < T l, T2>, l) với mọi l
K.
Thật vậy:
*Nếu l
k ta có: f( k , l) = f(Tl , l).
f( k , l) = f(Tl, l). Theo (*) ta có:
f(Tl, l)
f(Tl, l). Vậy: f(k , l) = f( k , l).
*Nếu l > k ta có: f(k , l) = f(k , l) : f( T2, l).
vậy quy tắc R4 thỏa mãn định lý 1.1 .
Quy tắc 5(R5):
Nếu X ├ T2 = T2’ (**) thì X ├ k = k
Ta chứng minh f( k , l) = f( k , l) Với mọi l
K.
Thật vậy:
*Nếu l < k ta hiển nhiên có: f( k , l) = f( k < T l , T2’>, l) = f( T l, l).
*Nếu l > k ta có: f( k , l) = f(T2, l).
f( k < Tl’, T2>, l) = f(T 2’ , l). Theo (**) ta có: f(T 2 , l) = f( T2’ , l).
vậy: f(k , l) = f( k , l)'
vậy quy tắc R5 thỏa mãn định lý 1.1. Định lý 1.1 đã được chứng minh.
Trang 11
Luận văn tốt nghiệp
3. Cây chuẩn tắc một chiều trên tập khóa K.
Định nghĩa 1.5 (Định nghĩa cây chuẩn tắc ).
Cây N TREE gọi là cây chuẩn tắc nếu N là một trong hai dạng sau :
a. N
d
D.
b. Nếu N
d thì N
k1 < d1, k2< d2,.....,ks, ds+1>....>>
Dạng đồ thị của cây chuẩn tắc N: N
k1
d1
k2
d1
...
ks
Ở đây: k1< k2< ... < ks (ki
di
ds
ds+1
K với i =l, 2, ..., s) và d 1, d2 ... ds D.
di+1 (i=1,...,s)
Nếu N, T
TREE, N là dạng chuẩn tắc và N
(K)T thì ta nói N là cây một
chiều chuẩn tắc của T trên K.
Định lý l.2 (tính duy nhất của dạng cây chuẩn tắc)
Giả sử N1, N2 là 2 cây một chiều chuẩn tắc khi đó ta có: N1
N2
N1
N2
Chứng minh:
Điều kiện đủ: Nếu N1
với mọi l
N2 thì N1
N2 là hiễn nhiên đúng vì f(N1,l) = f(N2,l)
K
Điều kiện cần: Ta có 4 trường hợp sau:
1. N1
d1 , N2
e1 (với d1 , e1
D)
Theo định nghĩa 3 ta có :
N1
N2 khi f(N1,l) = f(N2,l) với mọi l
Ta có :
Trang 12
K
(1)
Luận văn tốt nghiệp
f(N1,l) = f(d 1,l) = d 1
}
theo (1) = > d 1 = e1 hay N1
N2
f(N2,l) = f(e1,l) = e1
Vậy N1
2. N1
N2 thì N1
d1 , N2
N2
k1
e1
k2
e2
...
ks
Ở đây: k1< k2< ... < ks (ki
di
es
es+1
K với i =l, 2, ..., s-1) và d i
D.
di+1 (i=1,...,s)
Do N1
N2 nên N1
N2 vì
f(N2,k1) =e1 = f(N1,k1) = d 1
f(N2, k2) = e2 = f(N1,k2) = d1
Mà giả thiết e1
Vậy N1
3.
}
= > e1 = e2
e2 (định nghĩa cây lệch phải) nên e1 = e2 là trái với giả thiết.
N2
N1
k1
d1
N2
e1
k2
d2
...
ks
ds
ds+1
Chứng minh tương tự mục 2 ta có:
Do N1
N2 nên N1
N2 vì
f(N1,k1) =d1 = f(N2,k1) = e1
}
= > d1 = d2
Trang 13
Luận văn tốt nghiệp
f(N1, k2) = d 2 = f(N2,k2) = e1
Mà giả thiết d 1
Vậy N1
d2 (định nghĩa cây lệch phải) nên d 1 = d2 là trái với giả thiết.
N2
4. N1 và N2 có các dạng sau:
N1
k1
d1
N2
k2
l1
e1
d2
...
l2
e2
...
ks
Với di, ej
D. di
di+1
lt
ds
, ej
ds+1
ej+1 , (ki, kj)
et
et+1
K, i =1..s , j= 1..t
ki+1 - ki > 0 , lj+1 -lj > 0 , i = 1..s-1 , j =1.. t-1
Nếu N1
{
`
N2 thì ta chứng minh N1
tức là chứng minh
N2
l1 = k1 , l2 = k2 , ... lt = ks
(a)
d1 = e1 , d2 = e2 , ... d s = et , ds+1 = et+1
và chứng minh:
s=t
(b)
Bây giờ ta lần lượt chứng minh (a) và (b).
* Chứng minh (a):
Giả sử l1
k1
Xét trường hợp k1 < l1 . lấy m
f(N1,k1) = f(N1,m) = d 1
f(N2,k1) = f(N2,m) = e1
}
f(N1,k1+1) = f(N1,m+1) = d 2
f(N2,k1+1) = f(N2,m+1) = e1
K với k1=m ta có:
= > d1 = e1 (1)
}
= > d2 = d1 (2)
Từ (1) và (2) suy ra d 1 = d2 (vô lý) vì d 1 d2
= > kết luận k1 = l1 = > d 1 = e1
Trang 14
Luận văn tốt nghiệp
Chứng minh tương tự ta có:
{
l2 = k2 , l3 = k3 , ... ls = ks
d2 = e2 , d3 = e3 , ... ds = es
* Chứng minh (b) tức chứng minh s = t:
Giả sử s < t ( với trường hợp s > t) ta chứng minh tương tự)
Vì s < t nên ks = ls < lt
(3)
N2
l1
e1
l2
e2
...
ls
es
ls+1
ls+1
lt
et
Với
{
ki
K , i=1..t , l1< l2 < ... ở đây Ti (i=1,2) đã tồn tại cây lệch phải là R i (i=1,2) . Ta
có
AX ├ T = k
T1
T2
áp dụng 2 lần bổ đề 1 ta được
AX ├ T = k
N1
* Với k
kmin ta chọn ngay được cây N
kmax và k
phải thoả mãn:
N2
(T
N) và AX ├ T = N
Trang 16
N1 hoặc N
N2 là cây lệch
Luận văn tốt nghiệp
* Với k
K tức ( kmin < k < kmax ) ta xét các trường hợp sau:
2.1 Nếu N1
d , N2
d . Ta chọn N = k < d, d >
= > suy ra N là cây lệch phải và AX ├ T = N
2.2 Nếu N1
d , N2
k1...>>
với k1 N là dạng lệch phải và AX ├ T = N
b. Nếu k < k1 và d
d1 thì chọn
N
k
d
k1
d1
...
kn
Trang 17
- Xem thêm -