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

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.
Nội dung trích xuất từ tài liệu:
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ểnCây nhị phân tìm kiếm(Binary Search Trees)Nguyễn Mạnh HiểnKhoa Công nghệ thông tinhiennm@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ếmCài đặt cây nhị phân tìm kiếmPhươ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ấtTì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ènPhươ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 2Cách xóa: Thay nút bị xóa (2) bằng nút nhỏ nhất (3) của cây con phảiPhươ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 6Chứ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útChứ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