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

Chia sẻ: Hấp Hấp | Ngày: | Loại File: PDF | Số trang:22

Thêm vào BST

Báo xấu

68
lượt xem 1
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng "Cấu trúc dữ liệu và giải thuật: Cây nhị phân tìm kiếm" trình bày các định nghĩa về 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,...Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: 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 2 6 0 1 3 9 1 5 2 3 8 4 7 6
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) 6 7 2 9 2 7 1 5 2 1 5 9 8 3 11 8
Chứng minh d = O(logN) (3) Tính giá trị trung bình của D(N) theo kiểu đệ quy: •D(1) = 0 •D(N) = 1/N i=0N-1 [ D(i) + D(N-i-1) ] + N - 1 • = 2/N i=0N-1 D(i) + N - 1 Gốc Gốc Gốc Cây con Cây con Cây con Cây con Cây con có N-1 có 1 nút có N-2 có 2 nút có N-3 nút nút nút
Chứng minh d = O(logN) (4) •D(N) = 2/N i=0N-1 D(i) + N - 1 •ND(N) = 2 i=0N-1 D(i) + N(N-1) (1) •(N-1)D(N-1) = 2 i=0N-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