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

Chương này trang bị cho người học những hiểu biết về cây tìm kiếm nhị phân cân bằng. Thông qua chương này người học có thể biết được đặc điểm của cấu trúc cây tìm kiếm nhị phân, biết được cây tìm kiếm nhị phân cân bằng – AVL tree là gì, biết cách khai báo cấu trúc 1 nút cây AVL,. Mời các bạn ùng tham khảo. | 0 2S Search 5 K. J CawiM If Ht fa8 Ow service results 2 last F bleni t article LŨL- ư 3 business te. Jar erem0ved wrponih world _a _ wofcn 5taSns. I K f news 3Qh M i 2 wa i hriHuuz 5 Kw Chương 4. Tìm kiếm tiếp nguyenduyhiep@ hiepnd@ Tìm kiếm Đặc điểm của cấu trúc cây tìm kiếm nhị phân Kiểu cấu trúc liên kết Thao tác tìm kiếm thêm xóa thực hiện dễ dàng Thời gian thực hiện các thao tác trong trường hợp tốt nhất O log n tôi nhất 0 n Trường hợp tôi khi cây bị suy biến Cây cân bằng cho thời gian thực hiện tốt nhất Cải tiến cấu trúc cây tìm kiếm nhị phân để luôn thu được thời gian thực hiện tối ưu 3 24 2011 AVL tree Cây tìm kiếm nhị phân cân bằng - AVL tree Là cây tìm kiếm nhị phân Chiêu cao của cây con trái và cây con phải của gốc chênh nhau không quá 1 Cây con trái và cây con phải cũng là các cây AVL 1 AV L tree Quản lý trạng thái cân bằng của cây Mỗi nút đưa thêm 1 thông tin là hệ số cân bằng balance factor có thể nhận 3 giá trị Left_higher hoặc -1 Equal_height hoặc 0 Right_higher hoặc 1 12 1 Hai thao tác làm thay đổi s- f hệ số cân bằng của nút 0 21 -1 Thêm nút Xóa nút ÍE AVLtree Khai báo cấu trúc 1 nút cây AVL enum Balance_factor left_higher equal_height right_higher typedef struct AVLNode int data Balance_factor balance struct TreeNode leftchild struct TreeNode rightchild AVLNODE 3 24 2011 AVL tree Thêm các nút 3 2 1 4 5 6 7 vào cây AVL ban đầu rỗng Thêm 1 xử lý bằng phép xoay nút 2 3 24 2011 AVLtree Phép xoay đơn - single rotation Dùng để điều chỉnh khi mà nút mới thêm vào trong trường hợp i Cây con trái của nút con trái hoặc ii Cây con phải của nút con phải của nút Thực hiện tại nút vi phạm đầu tiên trên đường từ vị trí mới thêm trở về gốc Xoay giữa nút vi phạm và nút con trái xoay phải - TH i hoặc con phải xoay trái - TH ii Sau khi xoay các nút trở nên cân bằng