Bài giảng Cấu trúc dữliệu và giải thuật: Cấu trúc cây - Đậu Ngọc Hà Dương

Bài giảng Cấu trúc dữliệu và giải thuật: Cấu trúc cây - Đậu Ngọc Hà Dương có nội dung trình bày về khái niệm, phép duyệt cây và biểu diễn cây, cây nhị phân và cây nhị phân tìm kiếm, cây AVL, cây AA,... Mời các bạn cùng tham khảo!
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ấu trúc cây - Đậu Ngọc Hà DươngCấutrúcdữliệuvàgiảithuật Cấu trúc cây Giảngviên: Đậu Ngọc Hà Dương Nội dung trình bày2 CấutrúcdữliệuvàgiảithuậtHCMUS20113 Khái niệm CấutrúcdữliệuvàgiảithuậtHCMUS2011 Một số thuật ngữ4  Tree  Search tree  Binary search tree  Balanced tree  AVL tree  AA tree  Red-Black tree  … CấutrúcdữliệuvàgiảithuậtHCMUS2011 Cây tổng quát5 CấutrúcdữliệuvàgiảithuậtHCMUS2011 Cây tổng quát6 Sơ đồ tổ chức Cây thư mục CấutrúcdữliệuvàgiảithuậtHCMUS2011 Định nghĩa7 Cây (cây có gốc) được xác định đệ quy như sau: 1. Tậphợpgồm1đỉnhlàmộtcây.Câynàycógốclà đỉnhduynhấtcủanó. 2. GọiT1,T2,…Tk(k≥1)làcáccâykhôngcắtnhau cógốctươngứngr1,r2,…rk. GiảsửrlàmộtđỉnhmớikhôngthuộccáccâyTi.Khi đó,tậphợpTgồmđỉnhrvàcáccâyTitạothành mộtcâymớivớigốcr.CáccâyT1,T2,…Tkđược gọilàcâyconcủagốcr. CấutrúcdữliệuvàgiảithuậtHCMUS2011 Định nghĩa8 r Nút gốc r r r 1 2 k T1 T2 Tk Cây con CấutrúcdữliệuvàgiảithuậtHCMUS2011 Các khái niệm9  node: đỉnh  root: gốc cây  leaf: lá  inner node/internal node: đỉnh trong  parent: đỉnh cha  child: đỉnh con  path: đường đi CấutrúcdữliệuvàgiảithuậtHCMUS2011 Các khái niệm10 r Nút gốc rk r r r 1 2 k k k 1 2 T1 T2 Tk k k k 3 4 5 Cây con Nút lá Đường đi k CấutrúcdữliệuvàgiảithuậtHCMUS2011 6 Các khái niệm11  degree/order: bậc  Bậccủanode:Sốconcủanode  Bậccủacây:bậclớnnhấttrongsốcáccon  depth/level: độ sâu/mức  Mức(độsâu)củanode:Chiềudàicủađườngđitừ nodegốcđếnnodeđócộngthêm1.  height: chiều cao  Chiềucaocây: CấutrúcdCây rỗng:ảithu 0 ậtHCMUS2011  ữliệuvàgi Các khái niệm12 Bậc = k r Nút gốc Bậc = 2 Độ cao = 4 rk r r r 1 2 k k k 1 2 T1 T2 Tk k k k 3 4 5 Cây con Nút lá Đường đi k CấutrúcdữliệuvàgiảithuậtHCMUS2011 613 Phép duyệt cây CấutrúcdữliệuvàgiảithuậtHCMUS2011 Phép duyệt cây14  Đảm bảo đến mỗi node trên cây chính xác một lần một cách có hệ thống.  Nhiều thao tác xử lý trên cây cần phải sử dụng đến phép duyệt cây.  Các phép cơ bản:  Duyệttrước(Preorder) CấutrúcdữliệuvàgiảithuậtHCMUS2011 Phép duyệt cây15 Parent(a)? Parent(b) = a Eldest- a Child(c) = g b c d e f g h ...