Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 6: Cấu trúc cây - Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán Cấu Trúc Cây TS. Lê Nguyên Khôi Trường Đại Học Công Nghệ - ĐHQGHN Nội Dung
Khái niệm cơ bản
Duyệt cây
Cây nhị phân
Cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân cân bằng
Cây thứ tự bộ phận 1 Phân Loại Cây
Cây tự do (Đồ thị)
Đồ thị – mạng
Vô hướng, có hướng
Trọng số
Liên thông
Chu trình, phi chu trình
Cây có gốc
Có 1 đỉnh được coi là gốc
Quan hệ cha - con 2 Cây Tự Do (Đồ Thị) vô hướng định hướng 3 ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở Cây Tự Do (Đồ Thị) trọng số không trọng số 4 ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở 5 7 11 15 ĐHQG Cầu Giấy BX Kim Mã Ngã tư Sở Cây Tự Do (Đồ Thị) liên thông không liên thông 5 Cây Tự Do (Đồ Thị) chu trình phi chu trình 6 Cây Tự Do (Đồ Thị)
Mạng vận tải
Mạng liên lạc
Mạng thông tin
Mạng xã hội
Mạng phụ thuộc 7 Cây Có Gốc – Định Nghĩa
Sử dụng khái niệm đồ thị có hướng
Có một đỉnh đặc biệt được gọi là gốc cây
Mỗi đỉnh C bất kỳ không phải là gốc, tồn tại duy nhất một đỉnh P có đường đi từ P đến C. Đỉnh Parent được gọi là cha của đỉnh Child, và Child là con của Parent.
Có đường đi duy nhất từ gốc tới mỗi đỉnh của cây. 8 Cây Có Gốc – Ví Dụ 9 gốc đỉnh trong lá A B C D E F G mức 0 mức 1 mức 2 Cây Có Gốc – Thuật Ngữ
Độ cao (height)
của một đỉnh là độ dài đường đi dài nhất từ đỉnh đó tới một lá.
độ cao của lá bằng 0.
độ cao của cây là độ cao của gốc
Độ sâu (depth)
của một đỉnh là độ dài đường đi từ gốc tới đỉnh đó
độ sâu của gốc bằng 0. 10 Cây Có Gốc – Độ Cao
Độ cao của một đỉnh là độ dài đường đi dài nhất từ đỉnh đó tới một lá.
Xác đinh độ cao của mỗi đỉnh ℎ  = max ∀ ℎ( ) + 1 11 A B C D E F G Cây Biểu Thức 12 * + - / 3 7 4 6 2 Duyệt Cây
Thứ tự trước (preorder)
Thứ tự trong (inorder)
Thứ tự sau (postorder) 13 r T1 T2 Tk r1 r2 rk Duyệt Cây – Thứ Tự Trước
Thăm gốc r
Duyệt lần lượt các cây con T1, , Tk theo thứ tự trước
Còn được biết đến là kỹ thuật tìm kiếm theo độ sâu A-B-E-F-C-D-G 14 r T1 T2 Tk r1 r 2 rk A B C D E F G Duyệt Cây – Thứ Tự Trước – Mã Giả Algorithm preOrder(p) visit(p) for each child ci of p preOrder(ci) 15 Duyệt Cây – Thứ Tự Trong
Duyệt cây con trái T1 theo thứ tự trong
Thăm gốc r
Duyệt lần lượt các cây con T2, , Tk theo thứ tự trong E-B-F-A-C-G-D 16 r T1 T2 Tk r1 r 2 rk A B C D E F G Duyệt Cây – Thứ Tự Trong – Mã Giả Algorithm inOrder(p) inOrder(c1) visit(p) for each child ci of p inOrder(ci) 17 Duyệt Cây – Thứ Tự Sau
Duyệt lần lượt các cây con T1, , Tk theo thứ tự sau
Thăm gốc r E-F-B-C-G-D-A 18 r T1 T2 Tk r1 r 2 rk A B C D E F G Duyệt Cây – Thứ Tự Sau – Mã Giả Algorithm postOrder(p) for each child ci of p postOrder(ci) visit(p) 19 Cây Nhị Phân
Mỗi đỉnh có nhiều nhất 2 đỉnh con
Nhị phân chuẩn (full/proper binary tree)
Mỗi đỉnh có 0 hoặc 2 đỉnh con
Nhị phân đầy đủ (complete binary tree)
Các lá ở cùng mức
Nhị phân gần đầy đủ (almost complete binary tree)
Có con phải thì có con trái 20 Cây Nhị Phân Đầy Đủ
Độ cao ℎ có 2 − 1 lá
 lá có độ cao log  + 1 21 Cây Tìm Kiếm Nhị Phân
Cây tìm kiếm nhị phân là cây nhị phân lưu khóa ở các đỉnh trong của nó và thỏa mãn tính chất sau:
Gọi , ,  là 3 đỉnh sao cho  nằm trong cây con trái của  và  nằm trong cây con phải của , thỏa mãn  !(") ≤  !($) ≤  !(%)
Duyệt cây tìm kiếm nhị phân theo thứ tự trong sẽ thăm các khóa theo thứ tự tăng dần 22 Cây Tìm Kiếm Nhị Phân
Một số thao tác chính:
Tìm kiếm:
đỉnh có khóa &
đỉnh trước/sau đỉnh có khóa &
đỉnh có khóa min/max
Sửa đổi:
thêm đỉnh có khóa &
xóa đỉnh có khóa &
Mã giả
Độ phức tạp 23 6 92 41 8 Cây Tìm Kiếm Nhị Phân Cân Bằng
Cây tìm kiếm nhị phân cân bằng có cấu trúc của cây tìm kiếm nhị phân nhưng đảm bảo độ cao của cây là '(log )
Ví dụ:
Cây AVL
Tìm kiếm nhanh
Cây Đỏ-Đen
Sửa đổi nhanh 24 Cây Thứ Tự Bộ Phận – Heap
Cây nhị phân gần đầy đủ:
Có tất cả các mức của cây đều không thiếu đỉnh nào, trừ mức thấp nhất được lấp đầy kể từ bên trái
Độ cao là log  25 2 35 79 8 0 1 2 3 4 5 Cây Thứ Tự Bộ Phận – Heap
Min heap là cây nhị phân gần đầy đủ với tính chất:
Khóa của một đỉnh bất kỳ NHỎ hơn hoặc bằng khóa của các đỉnh con của nó.
Max heap là cây nhị phân gần đầy đủ với tính chất:
Khóa của một đỉnh bất kỳ LỚN hơn hoặc bằng khóa của các đỉnh con của nó. 26 Cây Thứ Tự Bộ Phận – Min Heap
Một số thao tác chính:
Tìm nhỏ nhất
Xóa nhỏ nhất
Chèn 27 2 35 79 8 0 1 2 3 4 5 Min Heap – Xóa Nhỏ Nhất
Thay thế gốc bằng đỉnh cuối cùng
Giải phóng đỉnh cuối cùng
Khôi phục tính chất thứ tự bộ phận của heap
Downheap khôi phục lại tính chất bằng cách đảo chỗ đỉnh có khóa & dọc theo đường đi từ gốc xuống
Downheap dừng khi & tiến tới một lá hay một đỉnh có khóa con lớn hơn &
Độ phức tạp: ((log ) 28 2 35 79 8 0 1 2 3 4 5 Min Heap – Xóa Nhỏ Nhất
Thay thế gốc bằng đỉnh cuối
Downheap 29 2 35 79 8 0 1 2 3 4 5 8 35 79 0 1 2 3 4 3 85 79 0 1 2 3 4 8 35 79 0 1 2 3 4 5 Min Heap – Chèn
Tìm tới vị trí để đưa phần tử mới vào
Lưu phần tử có khóa & vào đỉnh đó
Khôi phục tính chất thứ tự bộ phận của heap
Upheap khôi phục lại tính chất bằng cách đảo chỗ đỉnh có khóa & dọc theo đường đi từ đỉnh tới gốc
Upheap dừng khi & tiến tới gốc hay một đỉnh có khóa cha nhỏ hơn &
Độ phức tạp: ((log ) 30 2 35 79 1 0 1 2 3 4 5 Min Heap – Chèn
Thêm đỉnh cuối mới
Upheap 31 2 35 79 0 1 2 3 4 5 2 35 79 0 1 2 3 4 15 2 35 79 0 1 2 3 4 15 2 15 79 0 1 2 3 4 35 Sắp Xếp Cây Thứ Tự Bộ Phận
Liên tục xóa nhỏ nhất của Min heap sẽ được một dãy tăng dần
Độ phức tạp: (( log )
Xây dựng Min heap
Lần lượt chèn các khóa vào cây Min heap, bắt đầu từ cây Min heap rỗng
Độ phức tạp: (( log ) 32 2 35 79 8 0 1 2 3 4 5 Xây Dựng Min Heap – Cách Khác
Chèn liên tục vào Min Heap, nhưng không khôi phục tính chất thứ tự bộ phận.
Khôi phục tính chất thứ tự bộ phận (sử dụng downheap) bắt đầu từ đỉnh chính giữa
Xem tr.158 33 Sắp Xếp Cây Thứ Tự Bộ Phận – So Sánh
Giống sắp xếp gộp (merge sort)
Độ phức tạp (  log 
Giống sắp xếp chèn (insertion sort)
In-place algortihm 34