Bài giảng Cấu trúc dữ liệu 1: Chương 5 - Lương Trần Hy Hiến

Chương 5 của bài giảng Cấu trúc dữ liệu 1 giới thiệu về cây. Các nội dung cụ thể được trình bày trong chương này gồm có: Cây, cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng. Mời các bạn cùng tham khảo để tìm hiểu thêm các 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 1: Chương 5 - Lương Trần Hy Hiến ðại Họ Học Sư Phạ Phạm Tp. Hồ Hồ Chí Chí Minh Nội dung 1. Cây CẤU TRÚC DỮ LIỆU 1 2. Cây nhị phân 3. Cây nhị phân tìm kiếm 4. Cây cân bằng Chương 5: CÂY 5. 1. Cây 5.1. Cây 1 Cây là một tập hợp T các • ðịnh nghĩa 1: phần tử (gọi là nút của cây) trong ñó: – Có 1 nút ñặc biệt ñược gọi là gốc – Các nút còn lại ñược chia thành những tập rời nhau T1, T2 , ... , Tn theo quan hệ phân cấp trong ñó Ti cũng là một cây. – Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta còn gọi là quan hệ cha-con. Ví dụ về cây 5.1. Cây vn 2 cấu trúc cây với kiểu cơ • ðịnh nghĩa 2: sở T là: – Một nút cấu trúc rỗng ñược gọi là cây net edu org com rỗng (NULL). – Một nút mà thông tin chính của nó có kiểu T, nó liên kết với một số hữu hạn các cấu trúc cây khác cũng có kiểu cơ fpt hcmup java linux tuoitre sở T. Các cấu trúc này ñược gọi là những cây con của cây ñang xét. Một số thuật ngữ Một số thuật ngữ Bậc của nút là số cây con của Mức của một nút: một nút
Nút gốc (T) =0 Bậc của một cây là bậc lớn nhất 9
Gọi T1, T2,…,Tn là các cây con của T0 của các nút trên cây. 8 6
Mức(T1) = Mức(T2) = … = Mức(Tn) = Nút gốc là nút không có nút Mức(T0)+1 cha 5 4 3 2 9 Nút lá là nút có bậc bằng 0 Nút nhánh là nút có bậc khác 8 6 0 và không phải là nút gốc 5 4 3 2 Một số thuật ngữ 5.2. Cây nhị phân • ðộ dài ñường ñi từ gốc ñến nút x: là số • ðịnh nghĩa: Cây nhị phân là cây mà mỗi nhánh cần ñi qua kể từ gốc ñến x. • ðộ dài ñường ñi tổng của cây: nút có tối ña 2 cây con trong ñó Px là ñộ dài ñường ñi từ gốc ñến X. • ðộ dài ñường ñi trung bình: PI = PT/n (n là số nút trên cây T). • Rừng cây: là tập hợp nhiều cây trong ñó thứ tự các cây là quan trọng. 5.2. Cây nhị phân Ví dụ về ứng dụng của cây nhị phân * Cây con phải - - Cây con trái * 5 * + + 2 2 1 3 6 2 4 ((2+4)*2-5)*(2*1-(3+6)) 5.2. Cây nhị phân 5.2. Cây nhị phân Mức • Chiều cao h • Cách 1 h=Max(mức)+1 – Thông tin lưu trữ trữ tại nút. • Tính chất trái trong bộ nhớ. – ðịa chỉ nút gốc của cây con trá – Số nút nằm ở mức i ≤ 2i. – ðịa chỉ nút gốc của cây con phả phải trong bộ nhớ. – Số nút lá ≤ 2h-1, với h là chiều cao của cây. • Cách 2 – Số nút trong cây ≤ 2h-1. – Thông tin lưu trữ trữ tại nút. – Chiều cao của cây h > – ðịa chỉ nút cha của cây log2(số nút trong cây). – ðịa chỉ nút gốc của cây con trá trái trong bộ nhớ. – phải trong bộ nhớ. ...