CAO HỌC KHÓA 22 - HVKTQS

LỚP CAO HỌC K22 - KHOA CÔNG NGHỆ THÔNG TIN
 
Trang ChínhTrang Chính  CalendarCalendar  Trợ giúpTrợ giúp  Tìm kiếmTìm kiếm  Thành viênThành viên  NhómNhóm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

Share | 
 

 Ứng dụng của cây AVL ?

Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
Admin
Admin


Tổng số bài gửi : 57
Join date : 28/05/2010
Age : 34
Đến từ : Hà Nội

Bài gửiTiêu đề: Ứng dụng của cây AVL ?   Wed Sep 08, 2010 11:45 am

Xin chào các bạn!
Các bạn cho mình hỏi các ứng dụng cụ thể của cây AVL (cây nhị phân cân bằng)là gì ?

Trả lời:

Cân bằng AVL
Do Adel’son Vel’skki và Landis
AVL: Cây TKNP mà chiều cao của hai cây con của mọi nút chênh lệch nhiều nhất là 1.
*thêm một nút vào cây TKNP. Cây có thể mất cân bằng.
Cân bằng lại
r = root, tl = tree lelft, tr = tree right, h = high
* Xét cây AVL: tree T=(r,Tl,Tr) trong đó Tl có chiều cao hl và Tr có chiều cao hr
Giả sử nút thêm vào trên Tr.
Nếu hl=hr+1: sau khi thêm vẫn cân bằng
Nếu hl=hr : sau khi thêm vẫn cân bằng
Nếu hl=hr-1 thì sau khi thêm sẽ mất cân bằngcân bằng lại.
Tương tự nếu thêm nút vào Tl.
Nếu không cần bằng thì sử dụng 1 trong 4 phép quay là có thể cân bằng
Về Đầu Trang Go down
Xem lý lịch thành viên http://chk22hvktqs.allgoo.net
 
Ứng dụng của cây AVL ?
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
CAO HỌC KHÓA 22 - HVKTQS :: LẬP TRÌNH :: Data Structures + Algorithms-
Chuyển đến