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
Không có tóm lược sửa đổi Thẻ: Xuống 1 dòng thành đoạn mới Sửa đổi di động Sửa đổi từ trang di động |
Không có tóm lược sửa đổi Thẻ: Trình soạn thảo mã nguồn 2017 |
||
Dòng 1:
Trong [[khoa học máy tính]], một '''Cây AVL''' là một [[cây tìm kiếm nhị phân]] [[Cây tìm kiếm nhị phân tự cân bằng|tự cân bằng]], và là cấu trúc dữ liệu đầu tiên có khả năng này. Trong một cây AVL, tại mỗi nút [[chiều cao của cây|chiều cao]] của hai cây con sai khác nhau không quá một. Hiệu quả là các phép chèn (insertion), và xóa (deletion) luôn chỉ tốn thời gian [[ký hiệu O lớn|O]](log ''n'') trong cả trường hợp trung bình và trường hợp xấu nhất. Phép bổ sung và loại bỏ có thể cần đến việc tái cân bằng bằng một hoặc nhiều [[Phép quay cây nhị phân|phép quay]].
[[Tập tin:TreeBSTAndAVL.jpg|600px|giữa|Cây tìm kiếm nhị phân và cây AVL]]
Cây AVL được gọi theo tên của hai người đề xuất chúng, [[Georgii Adelson-Velsky|G.M. Adelson-Velsky]] và [[Yevgeniy Landis|E.M. Landis]], được công bố trong bài báo của họ vào năm [[1962]]: "An algorithm for the organization of information." (''Một thuật toán về tổ chức thông tin'')
| |||