Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 7: Cây nhị phân tìm kiếm

Nội dung text: Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 7: Cây nhị phân tìm kiếm

1. CẤCấuU TRÚ trúCc DỮ dữ L IỆUliệu V À và GIẢI thu THUẬTật giải 1 Click Click To Master Edit Title Style CÂY NHỊ PHÂN TÌM KIẾM NỘI DUNG NỘI 1
2. ÐịnhClick nghĩa To cây Edit nhị phânMaster tìm Titlekiế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 1 iải 18 ật g ật Ví dụ: THUẬT thu À GIẢI À GIẢI và 13 37 IỆU V c dữ liệu C DỮ L trú 15 23 40 U TRÚ Cấu CẤ 2
3. Ưu Clickđiểm của To câyEdit nhị Master phân tìm Title kiếm 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 1 iải – Trường hợp xấu nhất h = Ln ật g ật THUẬT – Tình huống xảy ra trường hợp xấu nhất ? thu À GIẢI À GIẢI và IỆU V c dữ liệu C DỮ L trú U TRÚ Cấu CẤ 3
4. CấuClick trúc dữ To liệu Edit của Master cây nhị Titlephân Styletì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 1 iải struct tagTNode *pLeft; ật g ật THUẬT struct tagTNode *pRight; thu À GIẢI À GIẢI và }TNode; IỆU V • Cấu trúc dữ liệu của cây c dữ liệu C DỮ L typedef TNode *TREE; trú U TRÚ Cấu CẤ 4
5. CẤCấuU TRÚ trúCc DỮ dữ L IỆUliệu V À và GIẢI thu THUẬTật giải 1 Cáctác thaotrên câyphân nhịtìm kiếm      Tìm có 1 nút trên khoá bằngxcây Xoá 1 nút có Key xtrên cây bằng Thêmnút 1 vàocâyphân tìm kiếm nhị Tạo 1nútcótrường Keybằng x Tạo 1cây rỗng Click Click To Master Edit Title Style 5
6. CẤCấuU TRÚ trúCc DỮ dữ L IỆUliệu V À và GIẢI thu THUẬTật giải 1 Tạo Tạo câyrỗng • { &T) CreateTree(TREEvoid rỗng Cây } Click Click To Master Edit Title Style T=NULL; - > địa chỉ bằngNULL nút gốc chỉ > địa 6
7. TạoClick 1 nút Tocó KeyEdit bằng Master x 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 1 iải else ật g ật { THUẬT thu p->key = x; //gán trường dữ liệu của nút = x À GIẢI À GIẢI và p->pLeft = NULL; IỆU V p->pRight = NULL; c dữ liệu } C DỮ L trú return p; U TRÚ Cấu CẤ } 7
8. ThêmClick một To nút Edit 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); 1 iải else return insertNode(T->pRight, X);} ật g ật THUẬT T = new TNode; thu À GIẢI À GIẢI if(T == NULL) return -1; và T->Key = X; IỆU V T->pLeft =T->pRight = NULL; c dữ liệu C DỮ L return 1; trú U TRÚ } Cấu CẤ 8
9. MinhClick họa thêmTo Edit 1 phần Master tử vào Title cây Style 44 44 X 88 1 iải ật g ật 13 37 59 108 THUẬT 59 > X thu À GIẢI À GIẢI và IỆU V 15 23 40 55 71 55 > X c dữ liệu C DỮ L trú 50 U TRÚ Cấu CẤ 9
10. TìmClick nút có khoáTo Edit bằng Master x (không dùngTitle đệ Style quy) TNode * searchNode(TREE Root, Data x) { Node *p = Root; while (p != NULL) { if(x == p->Key) return p; else 1 iải ật g ật if(x Key) p = p->pLeft; THUẬT thu else p = p->pRight; À GIẢI À GIẢI và IỆU V } c dữ liệu C DỮ L return NULL; trú U TRÚ } Cấu CẤ 10
11. TìmClick nút có To khoá Edit bằng Master x (dùng Title đệ quy)Style TNode *SearchTNode(TREE T, int x) { if(T!=NULL) { if(T->key==x) return T; 1 iải else ật g ật if(x>T->key) THUẬT thu return SearchTNode(T->pRight,x); À GIẢI À GIẢI và else IỆU V return SearchTNode(T->pLeft,x); c dữ liệu } C DỮ L trú return NULL; U TRÚ Cấu CẤ } 11
12. MinhClick hoạ tìmTo mộtEdit nút Master Title Style 44 Tìm X=55 55 18 88 1 iải ật g ật 13 37 59 108 THUẬT thu À GIẢI À GIẢI và IỆU V 15 23 40 55 71 c dữ liệu C DỮ L Tìm thấy X=55 trú U TRÚ Cấu CẤ 12
13. CẤCấuU TRÚ trúCc DỮ dữ L IỆUliệu V À và GIẢI thu THUẬTật giải 1 Minh hoạMinh1 cây thànhlập từdãysố Click Click To Master Edit Title Style 3 4 9, 5, 4, 8, 6, 3, 14,12,13 9, 5,4,8,6, 5 6 8 13 9 12 13 4 1
14. HủyClick 1 nút Tocó khoáEdit bằngMaster X trên Title cây Style  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) 1 iải . TH3: X có đầy đủ 2 cây con ật g ật THUẬT thu  TH1: Ta xoá nút lá mà không ành hưởng đến các À GIẢI À GIẢI và nút khác ttrên cây IỆU V  TH2: Trước khi xoá x ta móc nối cha của X với con c dữ liệu C DỮ L duy nhất cùa X. trú U TRÚ Cấu CẤ  TH3: Ta dùng cách xoá14 gián tiếp
15. MinhClick hoạ hủyTo Editphần Mastertử x có 1 Title cây con Style Hủy X=37 44 18 88 1 iải ật g ật 13 37 59 108 THUẬT thu À GIẢI À GIẢI và IỆU V 15 23 55 71 c dữ liệu C DỮ L trú U TRÚ Cấu CẤ 15
16. HủyClick 1 nút Tocó 2Edit cây conMaster 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 1 iải hợp đầu) ật g ật THUẬT  Cách tìm nút thế mạng Y cho X: Có 2 cách thu À GIẢI À GIẢI và . C1: Nút Y là nút có khoá nhỏ nhất (trái nhất) bên IỆU V cây con phải X c dữ liệu . C2: Nút Y là nút có khoá lớn nhất (phải nhất) bên C DỮ L cây con trái của X trú U TRÚ Cấu CẤ 16
17. MinhClick họa hủyTo Editphần Mastertử X có 2 Title cây conStyle Xoá nút có trường 44 Key = 18, lúc đó nút có khoá 23 là nút thế mạng 18 88 1 iải ật g ật 13 37 59 108 THUẬT thu À GIẢI À GIẢI và 15 2323 40 55 71 IỆU V c dữ liệu C DỮ L trú 30 U TRÚ Cấu CẤ 17
18. Cài Clickđặt thao To tác Edit xoá Master nút có trường Title StyleKey = x void DeleteNodeX1(TREE &T,int x) { if(T!=NULL) { if(T->Key Right,x); else { if(T->Key>x) DeleteNodeX1(T->Left,x); else //tim thấy Node có trường dữ liệu = x { TNode *p; 1 iải p=T; ật g ật if (T->Left==NULL) T = T->Right; THUẬT else thu { if(T->Right==NULL) T=T->Left; À GIẢI À GIẢI và else ThayThe1(p, T->Right);// tìm bên cây con phải IỆU V } delete p; c dữ liệu C DỮ L } } trú U TRÚ } Cấu CẤ else printf("Khong tim thay phan 18can xoa tu");}
19. HàmClick tìm phần To Edit tử thế Master mạng Title Style void ThayThe1(TREE &p, TREE &T) { if(T->Left!=NULL) ThayThe1(p,T->Left); else 1 iải { ật g ật THUẬT p->Key = T->Key; thu À GIẢI À GIẢI và p=T; IỆU V T=T->Right; c dữ liệu C DỮ L } trú U TRÚ Cấu } CẤ 19