Khác biệt giữa bản sửa đổi của “Cây AVL”
Nội dung được xóa Nội dung được thêm vào
n replaced: <references/> → {{tham khảo}} using AWB |
n →Cân bằng AVL và cây AVL: clean up, replaced: ( → ( using AWB |
||
Dòng 13:
=== Cân bằng AVL và cây AVL===
Các [[cây tìm kiếm nhị phân]] được xây dựng theo phương pháp chèn thông thường có thể có những biến dạng mất cân đối nghiêm trọng, chẳng hạn có thể hoàn toàn lệch phải (tất cả các nút trong chỉ có con phải) hoặc lệch trái (tất cả các nút trong chỉ có con trái). Trong các trường hợp này chi phí cho việc tìm kiếm trong trường hợp xấu nhất đạt tới n (
Cây T được gọi là cân bằng AVL nếu tại mỗi nút u của nó hệ số cân bằng có trị số tuyệt đối không vượt quá 1. Điều đó cũng có nghĩa là với mọi nút u của T, '''balance'''(u) chỉ nhận một trong ba giá trị -1, 0, 1.
Khi đó cây T cũng được gọi là cây AVL. Nếu cây con gốc tại đỉnh u là cân bằng AVL, ta cũng gọi đỉnh u là cân bằng AVL.
| |||