Cây nhị phân tìm kiếm

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. 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. Ta tiến hành xoá hủy nút Y (xoá Y giống 2 trường hợp đầu).
Nội dung trích xuất từ tài liệu:
Cây nhị phân tìm kiếm NỘI DUNG Click To Edit Master Title Style CÂY NHỊ PHÂN TÌM KIẾM Cấu trúc dữ liệu và thuật giảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 1 Click To Edit Master Title Style Ðịnh nghĩa cây nhị phân tìm kiếm • 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ảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Ví dụ: 18 13 37 15 23 40 2 Ưu ClickcTo cây nhị phân tìm kiếm điểm ủa Edit Master 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 Cấu trúc dữ liệu và thuật giải – Trường hợp xấu nhất h = LnCẤ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ấu trúc dTo ệu của cây nhị Title tìm kiếm Click ữ li Edit Master phân Style • 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ảiCẤ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ácClicktác trên cây nhị phân tìm Style thao To Edit Master 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ảiCẤ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 Click To Edit Master Title Style Tạo cây rỗng • 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ảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 6 Click To Edit Master Title Style Tạo 1 nút có Key bằng x 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 elseCẤ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 Edit Click nút 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ảiCẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 ...