Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - Trường ĐH Công nghệ Thông tin
lượt xem 4
download
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 trình bày nội dung về cây nhị phân tìm kiếm, cây nhị phân tìm kiếm cân bằng: định nghĩa, cấu trúc dữ liệu, các thao tác trên cây nhị phân tìm kiếm, Các trường hợp mất cân bằng. Kính mời quý đọc giả tham khảo nội dung chi tiết.
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 7 - Trường ĐH Công nghệ Thông tin
- NỘIMaster Click To Edit DUNGTitle Style CÂY NHỊ PHÂN TÌM KIẾM Cấu trúc dữ liệu và thuật giải CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 1
- Ðịnh nghĩaTo Click cây nhị Master Edit phân tìm Title kiếm Style • Cây nhị phân • Bảo đảm nguyên tắc bố trí khoá tại mỗi nút: – Các nút trong cây trái nhỏ hơn nút hiện hành – Các nút trong cây phải lớn hơn nút hiện hành Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Ví dụ: 18 13 37 15 23 40 2
- Ưu Click điểm của To cây Editnhị phân tìm Master kiếm Title Style • Nhờ trật tự bố trí khóa trên cây : – Định hướng được khi tìm kiếm • Cây gồm N phần tử : – Trường hợp tốt nhất h = log2N – Trường hợp xấu nhất h = Ln Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 – Tình huống xảy ra trường hợp xấu nhất ? 3
- CấuClick trúc dữ Toliệu củaMaster Edit cây nhị Title phân Style tìm kiếm • Cấu trúc dữ liệu của 1 nút typedef struct tagTNode { int Key; //trường dữ liệu là 1 số nguyên struct tagTNode *pLeft; Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 struct tagTNode *pRight; }TNode; • Cấu trúc dữ liệu của cây typedef TNode *TREE; 4
- CácClick thao tác To trên Editcây nhị phân Master tìmStyle Title kiếm Tạo 1 cây rỗng Tạo 1 nút có trường Key bằng x Thêm 1 nút vào cây nhị phân tìm kiếm Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Xoá 1 nút có Key bằng x trên cây Tìm 1 nút có khoá bằng x trên cây 5
- TạoClick cây rỗng To Edit Master Title Style • Cây rỗng -> địa chỉ nút gốc bằng NULL void CreateTree(TREE &T) { T=NULL; } Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 6
- TạoClick 1 nút To có Key Editbằng x Master Title Style TNode *CreateTNode(int x) { TNode *p; p = new TNode; //cấp phát vùng nhớ động if(p==NULL) exit(1); // thoát Cấu trúc dữ liệu và thuật giải else CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 { p->key = x; //gán trường dữ liệu của nút = x p->pLeft = NULL; p->pRight = NULL; } return p; } 7
- Thêm mộtTo Click nútEdit x Master Title Style • Rằng buộc: Sau khi thêm cây đảm bảo là cây nhị phân tìm kiếm. int insertNode(TREE &T, Data X) { if(T) { if(T->Key == X) return 0; if(T->Key > X) return insertNode(T->pLeft, X); Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 else return insertNode(T->pRight, X);} T = new TNode; if(T == NULL) return -1; T->Key = X; T->pLeft =T->pRight = NULL; return 1; } 8
- Minh họa thêm Click 1 phần To Edit tử vàoTitle Master cây Style 44 44 < X Theâm X=50 18 88 > X 88 Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 13 37 59 108 59 > X 15 23 40 55 71 55 > X 50 9
- TìmClick nút có khoá To EditbằngMaster x (không dùng TitleđệStyle quy) TNode * searchNode(TREE Root, Data x) { Node *p = Root; while (p != NULL) { if(x == p->Key) return p; else Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 if(x < p->Key) p = p->pLeft; else p = p->pRight; } return NULL; } 10
- TìmClick nút cóTo khoá bằng Edit x (dùng Master đệ quy) Title Style TNode *SearchTNode(TREE T, int x) { if(T!=NULL) { if(T->key==x) return T; Cấu trúc dữ liệu và thuật giải else CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 if(x>T->key) return SearchTNode(T->pRight,x); else return SearchTNode(T->pLeft,x); } return NULL; } 11
- Minh hoạ tìm Click To một Editnút Master Title Style 44 Tìm X=55 55 18 88 Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 13 37 59 108 15 23 40 55 71 Tìm thấy X=55 12
- Minh hoạ thành Click lập Master To Edit 1 cây từ Title dãy sốStyle 9, 5, 4, 8, 6, 3, 14,12,13 9 5 14 Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 4 8 12 3 6 13 13
- HủyClick 1 nút To có khoá Edit bằng X trên Master câyStyle Title Hủy 1 phần tử trên cây phải đảm bảo điều kiện ràng buộc của Cây nhị phân tìm kiếm Có 3 trường hợp khi hủy 1 nút trên cây TH1: X là nút lá TH2: X chỉ có 1 cây con (cây con trái hoặc cây con phải) Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 TH3: X có đầy đủ 2 cây con TH1: Ta xoá nút lá mà không ành hưởng đến các nút khác ttrên cây TH2: Trước khi xoá x ta móc nối cha của X với con duy nhất cùa X. TH3: Ta dùng cách xoá 14 gián tiếp
- Minh hoạ hủy Click phần Master To Edit tử x có 1Title cây con Style Hủy X=37 44 18 88 Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 13 37 59 108 15 23 55 71 15
- HủyClick 1 nút To có 2Edit cây Master con Title Style Ta dùng cách hủy gián tiếp, do X có 2 cây con Thay vì hủy X ta tìm phần tử thế mạng Y. Nút Y có tối đa 1 cây con. Thông tin lưu tại nút Y sẽ được chuyển lên lưu tại X. Ta tiến hành xoá hủy nút Y (xoá Y giống 2 trường Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 hợp đầu) Cách tìm nút thế mạng Y cho X: Có 2 cách C1: Nút Y là nút có khoá nhỏ nhất (trái nhất) bên cây con phải X C2: Nút Y là nút có khoá lớn nhất (phải nhất) bên cây con trái của X 16
- Minh họa hủy Click phần Master To Edit tử X có 2Title cây con Style Xoá nút có trường 44 Key = 18, lúc đó nút có khoá 23 là nút thế mạng 18 88 Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 13 37 59 108 15 23 40 55 71 30 17
- CàiClick đặt thao Totác xoáMaster Edit nút có trường Key = x Title Style void DeleteNodeX1(TREE &T,int x) { if(T!=NULL) { if(T->KeyRight,x); else { if(T->Key>x) DeleteNodeX1(T->Left,x); else //tim thấy Node có trường dữ liệu = x { TNode *p; Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 p=T; if (T->Left==NULL) T = T->Right; else { if(T->Right==NULL) T=T->Left; else ThayThe1(p, T->Right);// tìm bên cây con phải } delete p; } } } else printf("Khong tim thay phan 18 can xoa tu");}
- Hàm tìm phần Click tử thế To Edit mạng Master Title Style void ThayThe1(TREE &p, TREE &T) { if(T->Left!=NULL) ThayThe1(p,T->Left); else { Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 p->Key = T->Key; p=T; T=T->Right; } } 19
- CâyClick nhị phân tìm kiếm To Edit cân bằng Master Title Style Định nghĩa Tổ chức dữ liệu Các trường hợp mất cân bằng Cấu trúc dữ liệu và thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Các thao tác trên cây cân bằng 20
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 175 | 17
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 77 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 116 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 81 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 58 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 159 | 6
-
Bài giảng Cấu trúc dữ liệu - Chương 3: Cấu trúc cây
65 p | 58 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AA - Bùi Tiến Lên
30 p | 35 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 106 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây - Bùi Tiến Lên
68 p | 40 | 4
-
Bài giảng Cấu trúc dữ liệu: Chương 1 - ThS. Thiều Quang Trung (2018)
44 p | 43 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây AVL - Bùi Tiến Lên
38 p | 47 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - Ngô Quang Thạch
24 p | 58 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 68 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 50 | 2
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