Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 10: Cây nhị phân tìm kiếm - Nguyễn Mạnh Hiển

Cây nhị phân tìm kiếm (Binary Search Trees) Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn Định nghĩa • Xét trường hợp giá trị trên các nút khác nhau • Nút X có cây con trái TL và cây con phải TR − Các giá trị trên TL < X − Các giá trị trên TR > X Đây có phải là cây nhị phân tìm kiếm? Cài đặt cây nhị phân tìm kiếm Cài đặt cây nhị phân tìm kiếm Phương thức “public” gọi phương thức “private” Tìm một phần tử Tìm phần tử nhỏ nhất Tìm phần tử lớn nhất (không dùng đệ quy) Chèn phần tử Trước khi chèn Sau khi chèn Phương thức “insert” Xóa nút lá Trước khi xóa 3 Sau khi xóa 3 Cách xóa: Chỉ đơn giản xóa nút đó Xóa nút chỉ có một con Trước khi xóa 4 Sau khi xóa 4 Cách xóa: Cho nút cha (2) trỏ tới con (3) của nút bị xóa (4) Xóa nút có hai con Trước khi xóa 2 Sau khi xóa 2 Cách xóa: Thay nút bị xóa (2) bằng nút nhỏ nhất (3) của cây con phải Phương thức “remove” Độ phức tạp tính toán trên cây nhị phân tìm kiếm • Gọi N là tổng số nút trong cây • Gọi d là độ sâu trung bình của các nút • Các thao tác có độ phức tạp O(N), tức là tỉ lệ với số nút: − Xóa rỗng cây (makeEmpty) − Sao chép cây (toán tử gán =) • Các thao tác còn lại (tìm, chèn, xóa) có độ phức tạp trung bình O(d) vì: − Thời gian xử lý tại một nút (đọc giá trị, chèn, xóa) là O(1), nên độ phức tạp chỉ phụ thuộc vào thời gian định vị nút (tỉ lệ với độ sâu của nút, tức là d) • Ta sẽ chứng minh d = O(logN) ! Chứng minh d = O(logN) (1) • Độ sâu trung bình của nút (d): − d = tổng-độ-sâu-của-các-nút / số-nút = D/N − Tổng độ sâu của các nút được gọi là độ dài đường đi bên trong (internal path length) • Hãy tính độ dài đường đi bên trong của các cây sau: 2 2 3 1 2 5 3 1 6 9 8 7 0 6 4 2 Chứng minh d = O(logN) (2) • Nếu cây con trái của nút gốc R có i nút: D(N) = D(i) + D(N-i-1) + N-1 − Vì: + D(i) là độ dài đường đi bên trong của cây con trái + D(N-i-1) là độ dài đường đi bên trong của cây con phải + Độ dài đường đi của mỗi nút (trong N-1 nút ở hai cây con) phải được cộng thêm 1 (khi đi từ nút gốc R) 2 5 1 7 9 8 3 2 2 5 1 7 9 8 11 6 Chứng minh d = O(logN) (3) Gốc Cây con có N-1 nút Tính giá trị trung bình của D(N) theo kiểu đệ quy: •D(1) = 0 •D(N) = 1/N i=0 N-1 [ D(i) + D(N-i-1) ] + N - 1 • = 2/N i=0 N-1 D(i) + N - 1 Gốc Cây con có N-2 nút Cây con có 1 nút Gốc Cây con có N-3 nút Cây con có 2 nút Chứng minh d = O(logN) (4) •D(N) = 2/N i=0 N-1 D(i) + N - 1 •ND(N) = 2 i=0 N-1 D(i) + N(N-1) (1) •(N-1)D(N-1) = 2 i=0 N-2 D(i) + (N-1)(N-2) (2) Lấy (1) trừ (2) theo từng vế, ta có: •ND(N) - (N-1)D(N-1) = 2D(N-1) + 2(N-1) •ND(N) = (N+1)D(N-1) + 2(N-1) •D(N)/(N+1) = D(N-1)/N + 2(N-1)/[N(N+1)] • < D(N-1)/N + 2/N •D(N)/(N+1) < D(N-1)/N + 2/N •D(N-1)/(N) < D(N-2)/(N-1) + 2/(N-1) •D(N-2)/(N-1) < D(N-3)/(N-2) + 2/(N-2) •... •D(2)/3 < D(1)/2 + 2/2 Chứng minh d = O(logN) (5) •D(N)/(N+1) < D(N-1)/N + 2/N • < D(N-2)/(N-1) + 2/(N-1) + 2/N • < D(N-3)/(N-2) + 2/(N-2) + 2/(N-1) + 2/N • ... • < D(1)/(2) + 2/2 + ... + 2/(N-2) + 2/(N-1) + 2/N • = 2 i=2 N 1/i Nếu ta chứng minh được i=2 N 1/i = O(logN) thì sẽ suy ra độ sâu trung bình của một nút là d = D(N)/N  D(N)/(N+1) = O(log N) •D(N)/(N+1) < D(N-1)/N + 2/N •D(N-1)/(N) < D(N-2)/(N-1) + 2/(N-1) •D(N-2)/(N-1) < D(N-3)/(N-2) + 2/(N-2) •... •D(2)/3 < D(1)/2 + 2/2 Chứng minh d = O(logN) (6) 1 2 3 4 1/ 2 f(x) = 1/x 1/ 3 1/ 4 • Diện tích của các hình chữ nhật < diện tích dưới 1/x • i=2 4 1/i < ∫1 4 1/x dx • i=2 N 1/i < ∫1 N 1/x dx = ln(N) - ln (1) = O(logN)