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.
Nội dung trích xuất từ tài liệu:
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 3/24/2011 Chương4. Câytìmkiếmnhịphâncânbằng Tìmkiếm(tiếp) AVLTree nguyenduyhiep@gmail.com G.M.ADELSON‐VELSKIIvàE.M.LANDIS hiepnd@soict.hut.edu.vn Tìmkiếm AVLtree  Câytìmkiếmnhịphâncânbằng– AVLtree: Đặcđiểmcủacấutrúccâytìmkiếmnhịphân  Làcâytìmkiếmnhịphân  Kiểucấutrúcliênkết  Chiềucaocủacâycontráivàcâyconphảicủagốcchênhnhau khôngquá1  Thaotáctìmkiếm,thêm,xóathựchiệndễdàng  CâycontráivàcâyconphảicũnglàcáccâyAVL  Thờigianthựchiệncácthaotáctrongtrườnghợptốtnhất log ,tồinhất  Trườnghợptồikhicâybịsuybiến 12 12 12  Câycânbằngchothờigianthựchiệntốtnhất 21 9 21 9 21 Cảitiếncấutrúccâytìmkiếmnhịphânđể luônthuđượcthờigianthựchiệntốiưu 5 10 15 30 1 3/24/2011 AVLtree AVLtree  Quảnlýtrạngtháicânbằngcủacây  Thêmcácnút3,2,1,4,5,6,7vàocâyAVLbanđầurỗng  Mỗinútđưathêm1thôngtinlàhệsốcânbằng(balance Xoayphải factor)cóthểnhận3giátrị 3 3 ‐2 3 2  Left_higher(hoặc‐1)  Equal_height(hoặc0) 2 ‐1 2 1 3  Right_higher(hoặc+1) 12 1 Thêm3 Thêm2 Viphạmtính chấtcủacây  Haithaotáclàmthayđổi 0 1 AVL 0 9 21 ‐1 hệsốcânbằngcủanút: Thêm1  Thêmnút  Xóanút 15 0 Xửlýbằngphépxoaynút AVLtree AVLtree  Khaibáocấutrúc1nútcâyAVL 2 2 2 2 ...