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

NỘI DUNGCÂY NHỊ PHÂN TÌM KIẾMÐịnh nghĩa cây nhị phân tìm kiếmCâ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ànhCác nút trong cây phải lớn hơn nút hiện hành181337152340Ví dụ:Ưu điểm của cây nhị phân tìm kiếmNhờ trật tự bố trí khóa trên cây :Định hướng được khi tìm kiếmCây gồm N phần tử :Trường hợp tốt nhất h = log2NTrường hợp xấu nhất h = LnTình huống xảy ra trường hợp xấu nhất ?Cấu trúc dữ liệu của cây nhị phân tìm kiếmCấ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; struct tagTNode *pRight; }TNode;Cấu trúc dữ liệu của cây typedef TNode *TREE;Các thao tác trên cây nhị phân tìm kiếmTạo 1 cây rỗngTạo 1 nút có trường Key bằng xThêm 1 nút vào cây nhị phân tìm kiếmXoá 1 nút có Key bằng x trên câyTìm 1 nút có khoá bằng x trên câyTạo cây rỗngCây rỗng -> địa chỉ nút gốc bằng NULL void CreateTree(TREE &T) { T=NULL; }Tạo 1 nút có Key bằng xTNode *CreateTNode(int x){ TNode *p; p = new TNode; //cấp phát vùng nhớ động if(p==NULL) exit(1); // thoát else { p->key = x; //gán trường dữ liệu của nút = x p->pLeft = NULL; p->pRight = NULL; } return p;} Thêm một nút xRằ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); else return insertNode(T->pRight, X);} T = new TNode; if(T == NULL) return -1; T->Key = X; T->pLeft =T->pRight = NULL; return 1; }Minh họa thêm 1 phần tử vào cây4418881337591081523405571Theâm X=5044 X59 > X5055 > XTìm nút có khoá bằng x (không dùng đệ quy)TNode * searchNode(TREE Root, Data x){ Node *p = Root;  while (p != NULL) { if(x == p->Key) return p; else if(x Key) p = p->pLeft; else p = p->pRight; } return NULL;}Tìm nút có khoá bằng x (dùng đệ quy)TNode *SearchTNode(TREE T, int x){ if(T!=NULL) { if(T->key==x) return T; else if(x>T->key) return SearchTNode(T->pRight,x); else return SearchTNode(T->pLeft,x); } return NULL;}Minh hoạ tìm một nút4418881337591081523405571Tìm X=55Tìm thấy X=555555Minh hoạ thành lập 1 cây từ dãy số9, 5, 4, 8, 6, 3, 14,12,13951484631213Hủy 1 nút có khoá bằng X trên câyHủ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ếmCó 3 trường hợp khi hủy 1 nút trên câyTH1: 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)TH3: X có đầy đủ 2 cây conTH1: Ta xoá nút lá mà không ành hưởng đến các nút khác ttrên câyTH2: 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á gián tiếpMinh hoạ hủy phần tử x có 1 cây con44188813591083715235571Hủy X=37Hủy 1 nút có 2 cây conTa dùng cách hủy gián tiếp, do X có 2 cây conThay 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 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 XC2: 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 XMinh họa hủy phần tử X có 2 cây con44188813375910815234055713023Xoá nút có trường Key = 18, lúc đó nút có khoá 23 là nút thế mạngCài đặt thao tác xoá nút có trường Key = xvoid 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; 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 can xoa tu");}Hàm tìm phần tử thế mạng void ThayThe1(TREE &p, TREE &T){ if(T->Left!=NULL) ThayThe1(p,T->Left);else { p->Key = T->Key; p=T; T=T->Right; }}