tailieunhanh - Cấu trúc dữ liệu : CÂY, CÂY NHỊ PHÂN, CÂY NHỊ PHÂN TÌM KIẾM) part 2

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 nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải. Dưới đây là một ví dụ về cây nhị phân tìm kiếm: | typedef struct tagTNode DataType Key struct tagTNode pParent struct tagTNode pLeft struct tagTNode pRight TNODE typedef TNODE TREE 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 nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải. Dưới đây là một ví dụ về cây nhị phân tìm kiếm Nhờ ràng buộc về khóa trên CNPTK việc 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ở nên nhanh đáng kể. Chi phí tìm kiếm trung bình chỉ khoảng log2N. 7 Trong thực tế khi xét đến cây nhị phân chủ yếu người ta xét CNPTK. . Các thao tác trên cây . Thăm các nút trên cây . Tìm một phần tử x trong cây TToán Dễ dàng thấy rằng số lần so sánh tối đa phải thực hiện để tìm phần tử X là bằng h với h là chiều cao của cây. Ví dụ Tìm phần tử 55 . Thêm một phần tử x vào cây Việc thêm một phần tử X vào cây phải bảo đảm điều kiện ràng buộc của CNPTK. Ta có thể thêm vào nhiều vị trí khác nhau trên cây nhưng nếu thêm vào một nút lá thì sẽ dễ 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 ta sẽ tìm được vị trí cần thêm. 8 Hàm insert trả về giá trị -1 0 1 khi không đủ bộ nhớ gặp nút cũ hay thành công int insertNode TREE T Data X if T if T- Key X return 0 đã có if T- Key X return insertNode T- pLeft X else return insertNode T- pRight X 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 . Hủy một phần tử có khóa x Việc hủy một phần tử X ra khỏi cây phải bảo đảm điều kiện ràng buộc của CNPTK. Có 3 trường hợp khi hủy nút X có thể xảy ra X - nút lá. X - chỉ có 1 cây con trái hoặc phải . X có đủ cả 2 cây con Trường hợp thứ nhất chỉ đơn giản hủy X vì nó không móc nối đến phần tử nào khác.