intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Năm Tháng Tĩnh Lặng | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST
Báo xấu
62
lượt xem 3
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

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 1: Chương 5 - Lương Trần Hy Hiến

  1. ðạ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.
  2. 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
  3. 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))
  4. 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ớ. ðịa chỉ nút gốc của cây con phả Biểu diễn cây nhị phân 2h-1=2h-1+2h-2+…+1 5.2. Cây nhị phân 5.2. Cây nhị phân struct TNODE { DataType Key; TNODE *pLeft, *pRight; }; typedef TNODE* pTNODE; struct Tree{ pTNODE Root; }; Trong ñó DataType là kiểu dữ liệu ứng với thông tin lưu tại nút Biểu diễn cây nhị phân Biểu diễn cây nhị phân
  5. 5.2. Cây nhị phân 5.2. Cây nhị phân struct TNODE { DataType Key; TNODE* pParent; TNODE* pLeft; TNODE* pRight; }; typedef TNODE* TREE; Biểu diễn cây nhị phân Biểu diễn cây nhị phân 5.2. Cây nhị phân 5.2. Cây nhị phân • Duyệt theo thứ tự trước void NLR(TREE Root) { (Node-Left-Right) - NLR if (Root != NULL) • Duyệt theo thứ tự giữa { ;//Xử lý theo nhu cầu (Left- Node-Right) - LNR NLR(Root->pLeft); • Duyệt theo thứ tự sau NLR(Root->pRight); } (Left-Right-Node) - LRN } Duyệt cây nhị phân Duyệt cây nhị phân - NLR
  6. 5.2. Cây nhị phân (3 + 1)×3/(9 – 5 + 2) – (3×(7 – 4) + 6) = –13 5.2. Cây nhị phân -,/,x,+,3,1,3,+,-,9,5,2,+,x,3,-,7,4,6 void LNR(TREE Root) { if (Root != NULL) { LNR(Root->Left); ; //Xử lý theo nhu cầu LNR(Root->Right); } } Duyệt cây nhị phân - NLR Duyệt cây nhị phân - LN NR 5.2. Cây nhị phân (3 + 1)×3/(9 – 5 + 2) – (3×(7 – 4) + 6) = –13 5.2. Cây nhị phân 3,+,1,x,3,/,9,-,5,+,2,-,3,x,7,-,4,+,6 void LRN (TREE Root) { if (Root != NULL) { LRN(Root->Left); LRN(Root->Right); ; //Xử lý theo nhu cầu } } Duyệt cây nhị phân - LN NR Duyệt cây nhị phân - LRN N
  7. 5.2. Cây nhị phân (3 + 1)×3/(9 – 5 + 2) – (3×(7 – 4) + 6) = –13 5.2. Cây nhị phân 3,1,+,3,x,9,5,-,2,+,/,3,7,4,-,x,6,+,- • Hãy so sánh thời gian tìm kiếm cho ba loại cấu trúc dữ liệu: – Mảng – Danh sách liên kết – Cây nhị phân Duyệt cây nhị phân - LRN N 5.3. Cây nhị phân tìm kiếm 5.3. Cây nhị phân tìm kiếm • ðịnh nghĩa • Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong ñó tại mỗi nút, khóa của • Các thao tác trên cây nút ñang xét lớn hơn khóa của tất cả các – Duyệt cây nút thuộc cây con trái và nhỏ hơn khóa – Tìm một phần tử trên cây của tất cả các nút thuộc cây con phải – Thêm một phần tử vào cây • Nhờ ràng buộc về khóa trên CNPTK, việc – Hủy một phần tử trên cây tìm kiếm trở nên có ñịnh hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở – Tạo một cây nhị phân tìm kiếm nên nhanh ñáng kể. Nếu số nút trên cây – Hủy toàn bộ cây nhị phân tìm kiếm là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N ðịnh nghĩa Cây nhị phân tìm kiếm
  8. 5.3. Cây nhị phân tìm kiếm Dựng cây nhị phân LNR: B C D F A G I H E NLR: A C B F D H G I E A C H B F G E Ví dụ về Cây nhị phân tìm kiếm D I 5.3. Cây nhị phân tìm kiếm 5.3. Cây nhị phân tìm kiếm • Thao tác duyệt cây trên cây nhị phân tìm kiếm hoàn toàn giống như trên cây nhị phân. • Khi duyệt theo thứ tự giữa, trình tự các nút duyệt qua sẽ cho ta một dãy các nút theo thứ tự tăng dần của khóa. Thao tác – Duyệt cây Thao tác – Tìm một phần tử trên cây
  9. 5.3. Cây nhị phân tìm kiếm 5.3. Cây nhị phân tìm kiếm TNODE * searchNode(TREE Root, DataType x) TNODE* SearchNode(TREE T, DataType X) { { TNODE *p = Root; if(T) while (p!= NULL) { ðệ quy { if(T->Key == X) if(x == p->Key) return T; return p; Sử dụng vòng lặp if(XKey) else ñể tìm kiếm return SearchNode(T->pLeft, X); if(x < p->Key) else p = p->pLeft; return SearchNode(T->pRight, X); else } p = p->pRight; return NULL; } } return NULL; Thao tác – Tìm một phần tử trên cây } Thao tác – Tìm một phần tử trên cây 5.3. Cây nhị phân tìm kiếm 5.3. Cây nhị phân tìm kiếm • Việc thêm một phần tử X vào cây phải Lưu ý phần tử có khóa 55 Còn có 2 thành phần left,right bảo ñảm ñiều kiện ràng buộc của left==right==NULL (nút lá) CNPTK. • Ta có thể thêm vào nhiều chỗ khác nhau trên cây, nhưng nếu thêm vào một nút lá sẽ là tiện lợi nhất do ta có thể thực hiên quá trình tương tự thao tác tìm kiếm. • Khi chấm dứt quá trình tìm kiếm cũng chính là lúc tìm ñược chỗ cần thêm. Thao tác – Thêm một phần tử vào cây Thao tác – Thêm một phần tử vào cây
  10. 5.3. Cây nhị phân tìm kiếm 5.3. Cây nhị phân tìm kiếm int insertNode(TREE &T, Data X) { • Có 3 trường hợp xảy ra if(T) { – X là nút lá. if(T->Key == X) – X chỉ có 1 con (trái hoặc phải). return 0; //ñã có if(T->Key > X) – X có ñủ cả 2 con. return insertNode(T->pLeft, X); else return insertNode(T->pRight, X); } //Khi T==NULL thì thêm vào T = new TNode; if(T == NULL) return -1; //thiếu bộ nhớ T->Key = X; T->pLeft =T->pRight = NULL; return 1; //thêm vào thành công } Thao tác – Thêm một phần tử vào cây Thao tác – Xóa một phần tử ra khỏi cây 5.3. Cây nhị phân tìm kiếm 5.3. Cây nhị phân tìm kiếm • X là nút lá: chỉ ñơn giản hủy X vì nó không móc i) trước khi hủy X ta • X chỉ có 1 con (trái hoặc phải): nối ñến phần tử nào khác móc nối cha của X với con duy nhất của nó Thao tác – Xóa một phần tử ra khỏi cây Thao tác – Xóa một phần tử ra khỏi cây
  11. 5.3. Cây nhị phân tìm kiếm 5.3. Cây nhị phân tìm kiếm con ta không thể hủy trực tiếp • X có ñủ cả 2 con: do X có ñủ 2 con ⇒ Ta sẽ hủy gián tiếp. Thay vì hủy X, ta sẽ tìm một phần tử thế mạng Y. Phần tử này có tối ña một con. Thông tin lưu tại Y sẽ ñược chuyển lên lưu tại X. Sau ñó, nút bị hủy thật sự sẽ là Y giống như 2 trường hợp ñầu • Vấn ñề là phải chọn Y sao cho khi lưu Y vào vị trí của X, cây vẫn là CNPTK. Có 2 phần tử thỏa mãn yêu cầu: – Phần tử nhỏ nhất (tr trá nhất) trên cây con phả ái nhấ phải. Có thể dùng 15 – Phần tử lớn nhất (ph phả nhất) trên cây con trá ải nhấ trái. ñể thế mạng Thao tác – Xóa một phần tử ra khỏi cây Thao tác – Xóa một phần tử ra khỏi cây 5.3. Cây nhị phân tìm kiếm 5.3. Cây nhị phân tìm kiếm • Ta có thể tạo một cây nhị phân tìm kiếm • Việc toàn bộ cây bằng cách lặp lại quá trình thêm 1 phần có thể ñược thực void removeTree(TREE T) tử vào một cây rỗng hiện thông qua { thao tác duyệt if(T) 44,18,88,13,37,59,108,15,23,40,55,71 cây theo thứ tự { sau. Nghĩa là ta removeTree(T->pLeft); sẽ hủy cây con removeTree(T->pRight); trái, cây con delete(T); phải rồi mới hủy } } nút gốc. Thao tác – Hủy toàn bộ cây Thao tác – Tạo cây nhị phân tìm kiếm
  12. 5.3. Cây nhị phân tìm kiếm 5.4. Cây nhị phân cân bằng • Cây nhị phân cân bằng hoàn toàn 1. Khi nào thì cây thì cây suy – ðịnh nghĩa – ðánh giá biến thành danh sách liên kết? • Cây nhị phân cân bằng (AVL) Adelson-Velskii và Landis (Nga - 1962) – ðịnh nghĩa 2. ðể khắc phục ñiều này ta cần – Chiều cao cây AVL làm gì? – Cấu trúc dữ liệu – ðánh giá cây AVL 5.4. Cây nhị phân cân bằng 5.4. Cây nhị phân cân bằng • ðịnh nghĩa: Cây cân bằng hoàn toàn là cây nhị • ðánh giá phân tìm kiếm mà tại mỗi nút của nó, số nút – Một cây rất khó ñạt ñược trạng thái cân bằng hoàn toàn và cũng rất dễ mất cân bằng vì khi của cây con trái chênh lệch không quá một so thêm hay hủy các nút trên cây có thể làm cây với số nút của cây con phải mất cân bằng (xác suất rất lớn), chi phí cân bằng lại cây lớn vì phải thao tác trên toàn bộ cây. – Trong trường hợp xấu nhất ta chỉ phải tìm Cây Cân Bằ Bằng Hoà Hoàn Toà Toàn qua log2n phần tử (n là số nút trên cây). – Do CCBHT là một cấu trúc kém ổn ñịnh nên Cây CCBHT thì h ~ log2n trong thực tế không thể sử dụng. Nhưng ưu ñiểm của nó lại rất quan trọng. Vì vậy, cần ñưa ra một CTDL khác có ñặc tính giống CCBHT nhưng ổn ñịnh hơn. Cây nhị phân tìm kiếm cân bằ bằng hoà hoàn toà toàn Cây nhị phân tìm kiếm cân bằ bằng hoà hoàn toà toàn
  13. 5.4. Cây nhị phân cân bằng 5.4. Cây nhị phân cân bằng • ðịnh nghĩa: Cây nhị phân tìm kiếm cân bằng là cây mà tại mỗi nút của nó ñộ cao của cây con Cây CBHT???? trái và của cây con phải chênh lệch không quá một. Cây AVL Cây nhị phân tìm kiếm cân bằng AVL Cây nhị phân tìm kiếm cân bằng AVL 5.4. Cây nhị phân cân bằng 5.4. Cây nhị phân cân bằng • Chiều cao cây AVL • Chiều cao cây AVL – Ta phải khẳng ñịnh cây AVL n nút phải có – Gọi N(h) là số nút tối thiểu của cây AVL có chiều cao khoảng log2(n). chiều cao h. – Ta có N(0) = 0, N(1) = 1 và N(2) = 2. – ðể ñánh giá chính xác về chiều cao của cây – Cây AVL tối thiểu có chiều cao h sẽ có: AVL, ta xét bài toán: cây AVL có chiều cao • 1 cây con AVL tối thiểu chiều cao h-1 h sẽ phải có tối thiểu bao nhiêu nút? • 1 cây con AVL tối thiểu chiều cao h-2 – Như vậy: N(h) = 1 + N(h-1) + N(h-2) Cây nhị phân tìm kiếm cân bằng AVL Cây nhị phân tìm kiếm cân bằng AVL
  14. 5.4. Cây nhị phân cân bằng 5.4. Cây nhị phân cân bằng • Chiều cao cây AVL Cây AVL tối thiểu có chiều cao 4 – Ta lại có: N(h-1) > N(h-2) nên: • N(h) > 2N(h-2) • N(h) > 22N(h-4) • … ðể h-2i=1 thì i=(h-1)/2 • N(h) > 2iN(h-2i) – Suy ra: N(h) > 2 (h-1)/2 – Hay h-1 < 2*log2(N(h)) tức là h < 2*log2(N(h)) + 1= 2*log2(n)+1 – Vậy cây AVL có chiều cao O(log2(n)) Cây nhị phân tìm kiếm cân bằng AVL Cây nhị phân tìm kiếm cân bằng AVL 5.4. Cây nhị phân cân bằng 5.4. Cây nhị phân cân bằng struct AVLNode • CSCB(p) = 0 • ðánh giá ðộ cao cây trái (p) = ðộ { – Cây cân bằng là CTDL ổn ñịnh hơn hẳn cao cây phải (p) char balFactor; CCBHT vì chỉ khi thêm hủy làm cây thay ñổi • CSCB(p) = 1 ðộ cao cây trái (p) < ðộ chiều cao các trường hợp mất cân bằng Data key; cao cây phải (p) mới có khả năng xảy ra. AVLNode* pLeft; • CSCB(p) =-1 – Cây AVL với chiều cao ñược khống chế sẽ AVLNode* pRight; ðộ cao cây trái (p) > ðộ cho phép thực thi các thao tác tìm thêm }; cao cây phải (p) hủy với chi phí O(log2(n)) và bảo ñảm typedef AVLNode *AVLTree; không suy biến thành O(n). balFactor ==CSCB(p) Cấu trúc dữ liệu cho cây AVL
  15. 5.4. Cây nhị phân cân bằng 5.4. Cây nhị phân cân bằng • Trườ Trường hợ 1 cây T lệch về bên trái(có 3 khả hợp 1: • Các trường hợp mất cân bằng năng) – Ta sẽ không khảo sát tính cân bằng của 1 cây nhị phân bất kỳ mà chỉ quan tâm ñến các khả năng mất cân bằng xảy rakhi thêm hoặc hủy một nút trên cây AVL. – Như vậy, khi mất cân bằng, ñộ lệch chiều cao giữa 2 cây con sẽ là 2. Ta có 6 khả năng (chia làm 2 trường hợp). Cây nhị phân tìm kiếm cân bằng AVL Cây nhị phân tìm kiếm cân bằng AVL 5.4. Cây nhị phân cân bằng 5.4. Cây nhị phân cân bằng • Hướ Hướng giả quyết của 2 trường hợp là tương tự giải quyế • Trườ Trường hợ 2 cây T lệch về bên phải(có 3 khả hợp 2: nhau nên ta chỉ giải quyết trườ trường hợ hợp 1 năng) Quay ñơn Left - Left Cây nhị phân tìm kiếm cân bằng AVL Cây nhị phân tìm kiếm cân bằng AVL
  16. 5.4. Cây nhị phân cân bằng 5.4. Cây nhị phân cân bằng Quay kép Left - Right Quay ñơn Left - Left Cây nhị phân tìm kiếm cân bằng AVL Cây nhị phân tìm kiếm cân bằng AVL Nội dung ôn thi Nội dung ôn thi • Lý thuyết • Thực hành – Thuật toán sắp xếp, tìm kiếm – Thêm code vào các thuật toán ñể thực hiện • Tìm kiếm • Thực hiện từng bước kết quả của thuật toán một yêu cầu nào ñó (HeapSort,MergeSort, …) – Danh sách liên kết • ShakerSort có những cải tiến gì so với BubleSort – Danh sách liên kết • Tổ chức CTDL: phân số, ña thức 1 biến, quản lý • Lý do sử dụng CTDL ñộng sinh viên • Tổ chức dữ liệu cho một bài toán nào nào ñó -> nêu hướng giải quyết (từ ñiển, ña thức, …) • Sắp xếp theo một thứ tự nào ñó • Chuyển trung tố  hậu tố, ñịnh trị hậu tố – Cây • Dựng cây, Duyệt Cây • Thêm, Xóa phần tử cho cây • Hỏi cây
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2