6.1. ðộ cao trung bình của BST
Trong bài trước ta ủó biết rằng cỏc thao tỏc cơ bản của BST ủược thực hiện trong thời gian $ với là chiều cao của cõy. Nếu khúa ủược chốn vào một BST rỗng, ta sẽ ủược một BST gồm nỳt. Chiều cao của BST cú thể là một số nguyờn nào ủú nằm trong phạm vi từ _[` tới C . Nếu thay ủổi thứ tự chốn khúa vào cõy, ta cú thể thu ủược một cấu trỳc BST khỏc.
ðiều chúng ta muốn biết là nếu chèn khóa vào BST theo các trật tự khác nhau thỡ ủộ cao trung bỡnh của BST thu ủược là bao nhiờu. Hay núi chớnh xỏc hơn, chỳng ta cần biết giỏ trị kỳ vọng của ủộ cao một BST khi chốn khúa vào theo một trật tự ngẫu nhiên.
Thực ra trong cỏc thao tỏc cơ bản của BST, ủộ sõu trung bỡnh của cỏc nỳt mới là yếu tố quyết ủịnh hiệu suất chứ khụng phải ủộ cao của cõy. ðộ sõu của nỳt chớnh là số phộp so sỏnh cần thực hiện ủể chốn nỳt vào BST. Tổng số phộp so sỏnh ủể chốn toàn bộ nỳt vào BST cú thể ủỏnh giỏ tương tự như QuickSort, bằng $ %' . Vậy ủộ sõu trung bỡnh của mỗi nỳt là (.$ %' $%' . Người ta cũn chứng minh ủược một kết quả mạnh hơn: ðộ cao trung bỡnh của BST là một ủại lượng $%' . Cụ thể là N V %' $ với là giỏ trị kỳ vọng của ủộ cao và là số nỳt trong BST. Chứng minh này khỏ phức tạp, bạn có thể tham khảo trong các tài liệu khác .
70
6.2. Treap
Chúng ta có thể tránh trường hợp suy biến của BST bằng cách chèn các nút vào cõy theo một trật tự ngẫu nhiờn*. Tuy nhiờn trờn thực tế rất ớt khi chỳng ta ủảm bảo ủược cỏc nỳt ủược chốn/xúa trờn BST theo trật tự ngẫu nhiờn, bởi cỏc thao tác trên BST thường do một tiến trình khác thực hiện và thứ tự chèn/xóa hoàn toàn do tiến trỡnh ủú quyết ủịnh.
Trong mục này chúng ta quan tâm tới một dạng BST mà cấu trúc của nó không phụ thuộc vào thứ tự chèn/xóa: Treap.
Cho mỗi nỳt của BST thờm một thụng tin !!> gọi là “ủộ ưu tiờn”. ðộ ưu tiờn của mỗi nỳt là một số dương. Khi ủú Treap† [33] ủược ủịnh nghĩa là một BST thỏa mãn tính chất của Heap. Cụ thể là:
Nếu nút > nằm trong nhánh con trái của nút thì >E > N E >. Nếu nút > nằm trong nhánh con phải của nút thì >E > w E >. Nếu nút > là hậu duệ của nút thì >E !!> N E !!>
Hai tớnh chất ủầu tiờn là tớnh chất của BST, tớnh chất thứ ba là tớnh chất của Heap. Nỳt gốc của Treap cú ủộ ưu tiờn lớn nhất. ðể tiện trong cài ủặt, ta quy ủịnh nỳt giả x cú ủộ ưu tiờn bằng 0.
ðịnh lý 6-1
Xột một tập cỏc nỳt, mỗi nỳt chứa khúa và ủộ ưu tiờn, khi ủú tồn tại cấu trỳc Treap chứa các nút trên.
Chứng minh
Khởi tạo một BST rỗng và chèn lần lượt các nút vào BST theo thứ tự từ nút ưu tiờn cao nhất tới nỳt ưu tiờn thấp nhất. Hai ràng buộc ủầu tiờn ủược thỏa món vỡ ta sử dụng phép chèn của BST. Hơn nữa phép chèn của BST luôn chèn nút mới vào thành nỳt lỏ nờn sau mỗi bước chốn, nỳt lỏ mới chốn vào khụng thể mang ủộ ưu tiờn lớn hơn cỏc nỳt tiền bối của nú ủược. ðiều này chỉ ra rằng BST tạo thành là một Treap.
* Từ “trỏnh” ở ủõy khụng chớnh xỏc, trờn thực tế phương phỏp này khụng trỏnh ủược trường hợp xấu. Cú ủiều là xỏc suất xảy ra trường hợp xấu quỏ nhỏ và rất khú ủể “cố tỡnh” chỉ ra cụ thể trường hợp xấu (giống như Randomized QuickSort).
† Tên gọi Treap là ghép của hai từ: “tree” và “Heap”
71
ðịnh lý 6-2
Xột một tập cỏc nỳt, mỗi nỳt chứa khúa và ủộ ưu tiờn. Nếu cỏc khúa cũng như ủộ ưu tiờn của cỏc nỳt hoàn toàn phõn biệt thỡ tồn tại duy nhất cấu trỳc Treap chứa các nút trên.
Chứng minh
Sự tồn tại của cấu trỳc Treap ủó ủược chỉ ra trong chứng minh trong ðịnh lớ 6.1.
Tính duy nhất của cấu trúc Treap này có thể chứng minh bằng quy nạp: Rõ ràng ủịnh lý ủỳng với tập gồm 0 nỳt (Treap rỗng). Xột tập gồm w nỳt, khi ủú nỳt cú ủộ ưu tiờn lớn nhất chắc chắn sẽ phải là gốc Treap, những nỳt mang khúa nhỏ hơn khóa của nút gốc phải nằm trong nhánh con trái và những nút mang khóa lớn hơn khóa của nút gốc phải nằm trong nhánh con phải. Sự duy nhất về cấu trúc của nhỏnh con trỏi và nhỏnh con phải ủược suy ra từ giả thiết quy nạp. ðPCM.
Trong cài ủặt thụng thường của Treap, ủộ ưu tiờn !!> của mỗi nỳt thường ủược gỏn bằng một số ngẫu nhiờn ủể vụ hiệu húa những tiến trỡnh “cố tỡnh” làm cõy suy biến: Cho dự cỏc nỳt ủược chốn/xúa trờn Treap theo thứ tự nào, cấu trỳc của Treap sẽ luôn giống như khi chúng ta chèn các nút còn lại vào theo thứ tự giảm dần của B!!> (tức là thứ tự ngẫu nhiờn). Hơn nữa nếu biết trước ủược tập cỏc nỳt sẽ chốn vào Treap, ta cũn cú thể gỏn ủộ ưu tiờn !!> cho cỏc nỳt một cỏch hợp lý ủể “ộp” Treap thành cõy nhị phõn gần hoàn chỉnh (trung vị của tập cỏc khúa sẽ ủược gỏn ủộ ưu tiờn cao nhất ủể trở thành gốc cõy, tương tự với nhánh trái và nhánh phải…). Ngoài ra nếu biết trước tần suất truy cập nút ta có thể gỏn ủộ ưu tiờn của mỗi nỳt bằng tần suất này ủể cỏc nỳt bị truy cập thường xuyờn sẽ ở gần gốc cõy, ủạt tốc ủộ truy cập nhanh hơn.
6.3.Các thao tác trên Treap a) a)
a) a) CCCC6666u trúc nútu trúc nútu trúc nútu trúc nút
Tương tự như BST, cấu trỳc nỳt của Treap chỉ cú thờm một trường !!> ủể lưu ủộ ưu tiờn của nỳt
type
PNode = ^TNode; //Kiểu con trỏ tới một nút
TNode = record key: TKey;
parent, left, right: PNode;
priority: Integer;
72 end;
var
sentinel: TNode;
nilT: PNode; //Con trỏ tới nỳt ủặt biệt
root: PNode; //Con trỏ tới nút gốc
begin
sentinel.priority := 0;
nilT := @sentinel;
...
end.
Trên lý thuyết người ta thường cho các giá trị B!!> là số thực ngẫu nhiên, khi cài ủặt ta cú thể cho B!!> số nguyờn dương lấy ngẫu nhiờn trong một phạm vi ủủ rộng. Ký hiệu DB là hàm trả về một số dương ngẫu nhiờn, bạn cú thể cài ủặt hàm này bằng bất kỳ một thuật toỏn tạo số ngẫu nhiờn nào. Vớ dụ:
function RP: Integer;
begin
Result := 1 + Random(MaxInt - 1);
//Lấy ngẫu nhiên từ 1 tới MaxInt - 1
end;
Các phép khởi tạo cây rỗng, tìm phần tử lớn nhất, nhỏ nhất, tìm phần tử liền trước, liền sau trên Treap không khác gì so với trên BST thông thường. Phép quay khụng ủược thực hiện tựy tiện trờn Treap vỡ nú sẽ phỏ vỡ ràng buộc thứ tự Heap, thay vào ủú chỉ cú thao tỏc UpTree ủược nhỳng vào trong mỗi phộp chốn (Insert) và xúa (Delete) ủể hiệu chỉnh cấu trỳc Treap.
Nhắc lại về thao tác !
73
Hình 1.24. Thao tác
procedure UpTree(x: PNode);
var y, z, branch: PNode;
begin
y := x^.parent; //y^ là nút cha của x^
z := y^.parent; //z^ là nút cha của y^
if x = y^.left then //Quay phải
begin
branch := x^.right;
SetLink(y, branch, True);
SetLink(x, y, False);
end
else //Quay trái
begin
branch := x^.left;
SetLink(y, branch, False);
SetLink(x, y, True);
end;
>
là nhánh trái Quay phải c
>
c
>
c
là nhánh phải Quay trái
>
c
H!l H!l
H!l H!l
74 SetLink(z, x, z^.left = y); //Móc nối x^ vào làm con z^ thay cho y^
if root = y then root := x;
//Cập nhật lại gốc BST nếu trước ủõt y^ là gốc
end;
b) b) b) b) ChènChènChèn Chèn
Phộp chốn trờn Treap trước hết thực hiện như phộp chốn trờn BST ủể chốn khúa vào một nỳt lỏ. Nỳt lỏ x mới chốn vào sẽ ủược gỏn một ủộ ưu tiờn ngẫu nhiờn.
Tiếp theo là phép hiệu chỉnh Treap: Gọi >x là nút cha của x, chừng nào thấy x mang ủộ ưu tiờn lớn hơn >x (vi phạm thứ tự Heap) ta thực hiện lệnh
! ủể ủẩy nỳt x lờn làm cha nỳt >x và kộo nỳt >x xuống làm con nỳt x.
//Chèn khóa k vào Treap, trả về con trỏ tới nút chứa k
function Insert(k: TKey): PNode;
var x, y: PNode;
begin
//Thực hiện phép chèn như trên BST
y := nilT;
x := root;
while x ≠ nilT do begin
y := x;
if k < x^.key then x := x^.left else x := x^.right;
end;
New(x);
x^.key := k;
x^.left := nilT;
x^.right := nilT;
SetLink(y, x, k < y^.key);
if root = nilT then root := x;
//Chỉnh Treap
x^.priority := RP; //Gỏn ủộ ưu tiờn ngẫu nhiờn
repeat
y := x^.parent;
if (y ≠ nilT)
and (x^.priority > y^.priority) then UpTree(x)
75
else Break;
until False;
Result := x;
end;
Vớ dụ chỳng ta cú một Treap chứa cỏc khúa A, B, E, G, H, K với ủộ ưu tiờn là A:1, B:5, E:2, G:7, H:4, K:3 và chốn một nỳt khúa chứa khúa I và ủộ ưu tiờn 6 vào Treap, trước hết thuật toỏn chốn trờn BST ủược thực hiện như trong hỡnh 1.25.
Hình 1.15. Phép chèn trên Treap trước hết thực hiện như trong BST
Tiếp theo là hai phộp ! ủể chuyển nỳt I:6 về vị trớ ủỳng trờn Treap (h.1.26)
Hỡnh 1.26. Sau phộp chốn BST là cỏc phộp UpTree ủể chỉnh lại Treap
Số phộp ! cần thực hiện phụ thuộc vị trớ và ủộ ưu tiờn của nỳt mới chốn vào (Cú thể là số nào ủú từ 0 tới với là ủộ cao của Treap), nhưng người ta ủó chứng minh ủược ủịnh lý sau:
ðịnh lý 6.3
Trung bình số phép ! cần thực hiện trong phép chèn ="! là 2.
G:7
A:1 E:2
B:5
K:3 H:4
I:6
G:7
A:1 E:2
B:5
I:6 H:4
K:3
G:7
A:1 E:2
B:5
K:3 I:6
H:4 G:7
A:1 E:2
B:5
K:3 H:4
G:7
A:1 E:2
B:5
K:3 H:4
I:6
76
c) c) c) c) XóaXóaXóaXóa
Phộp xúa nỳt x trờn Treap ủược thực hiện như sau:
Nếu x có ít hơn hai nhánh con, ta lấy nút con (nếu có) của x lên thay cho x và xóa nút x.
Nếu x cú ủỳng hai nhỏnh con, gọi >x là nỳt con mang ủộ ưu tiờn lớn hơn trong hai nỳt con, thực hiện phộp !> ủể kộo nỳt x xuống sõu phớa dưới lá và lặp lại cho tới khi x chỉ còn một nút con. Việc xóa quy về trường hợp trên
procedure Delete(x: PNode);
var y, z: PNode;
begin
while (x^.left ≠ nilT) and (x^.right ≠ nilT) do
//Chừng nào x^ có 2 nút con
begin
//Xỏc ủịnh y^ là nỳt con mang ủộ ưu tiờn lớn hơn
y := x^.left;
if y^.priority < x^.right^.priority then y := x^.right;
UpTree(y); //ðẩy y lên phía gốc, kéo x xuống phía lá
end;
//Bõy giờ x^ chỉ cú tối ủa một nỳt con, xỏc ủịnh y^ là nỳt con (nếu cú) của x
if x^.left <> nilT then y := x^.left else y := x^.right;
z := x^.parent; //z^ là nút cha của x^
SetLink(z, y, z^.left = x); //Cho y^ làm con của z^ thay cho x^
if x = root then root := y; //Cập nhật lại gốc
Dispose(x); //Giải phóng bộ nhớ
end;
Vớ dụ chỳng ta cú một Treap chứa cỏc khúa A, B, E, G, H, I, K với ủộ ưu tiờn là A:1, B:5, E:2, G:7, H:4, I:6, K:3 và xóa nút chứa khóa G. Ba phép !
(quay) sẽ ủược thực hiện trước khi xúa nỳt chứa khúa G
77
Hỡnh 1.27. Thực hiện cỏc phộp quay ủẩy dần nỳt cần xúa xuống dưới lỏ, khi nỳt cần xúa cũn ớt hơn 1 nhánh con thì xóa trực tiếp.
Tương tự như phộp chốn, số phộp ! cần thực hiện phụ thuộc vị trớ và ủộ ưu tiờn của nỳt bị xúa, nhưng người ta ủó chứng minh ủược ủịnh lý sau ủõy.
ðịnh lý 6-4
Trung bình số phép ! cần thực hiện trong phép xóa P là 2.
Bài tập
1.28. Thứ tự thống kờ: Cho một Treap, hóy xõy dựng thuật toỏn tỡm khúa ủứng thứ khi sắp thứ tự. Ngược lại cho một nỳt, hóy tỡm số thứ tự của nỳt ủú khi duyệt Treap theo thứ tự giữa.
1.29. Treap biểu diễn tập hợp
Khi dùng Treap biểu diễn tập hợp các giá trị khóa, (tức là các khóa trong Treap hoàn toàn phõn biệt), phộp thử 5 cú thể ủược thực hiện thụng
G:7
E:2 B:5
K:3 I:6
H:4 A:1
G:7
E:2 B:5
K:3 I:6
A:1
H:4
B:5
E:2 A:1
K:3 I:6
G:7
H:4
B:5
G:7 A:1
K:3 I:6
H:4
E:2
B:5
E:2 A:1
K:3 I:6
H:4
78
qua hàm k!l. Việc thêm một phần tử vào tập hợp có thể thực hiện thụng qua một sửa ủổi của hàm ="! (Chỉ chốn nếu khúa chưa cú trong Treap). Việc xúa một phần tử khỏi tập hợp cũng ủược thực hiện thụng qua việc sửa ủổi thủ tục P (tỡm phần tử trong Treap, nếu tỡm thấy thỡ thực hiện phộp xúa). Ngoài ra cũn cú nhiều thao tỏc khỏc ủược thực hiện rất hiệu quả với cấu trỳc Treap, hóy cài ủặt cỏc thao tỏc sau ủõy trờn Treap:
Phép tách (Split): Với một giá trị 4, tách các khóa O 4 và các khóa 1 4 ra hai Treap biểu diễn hai tập hợp riêng rẽ.
Gợi ý: Tìm nút chứa phần tử 4 trong Treap, nếu không thấy thì chèn 4 vào một nỳt mới. ðặt ủộ ưu tiờn của nỳt này bằng . Theo nguyờn lý của cấu trỳc Treap, nỳt này sẽ ủược ủẩy lờn thành gốc cõy. Ngoài ra theo nguyên lý của cấu trúc BST, nhánh con trái của gốc cây sẽ chứa tất cả các khóa O 4 và nhánh con phải của gốc cây sẽ chứa tất cả các khóa 1 4. Phép hợp (Union): Cho hai Treap chứa hai tập khóa, xây dựng Treap mới chứa tất cả cỏc khúa của hai Treap ban ủầu
Phép giao (Intersection): Cho hai Treap chứa hai tập khóa, xây dựng Treap mới chứa tất cả cỏc khúa cú mặt trong cả hai Treap ban ủầu
Phép lấy hiệu (Difference): Cho hai Treap 8 H chứa hai tập khóa, xây dựng Treap mới chứa các khóa thuộc nhưng không thuộc H.