Yếu tố cân bằng là một khái niệm quan trọng trong cây AVL, một loại cây tự học tự bảo vệ bản thân. nó giúp bảo trì chiều cao của cây và đảm bảo các hoạt động hiệu quả như tìm kiếm, chèn và xóa bỏ. Hiểu cách tính toán và áp dụng yếu tố cân bằng là thiết yếu để quản lý hiệu quả cây AVL.

Yếu tố thăng bằng là gì?

Yếu tố cân bằng của một nút trong một cây AVL là sự khác biệt giữa độ cao của các cây con bên trái và bên phải.

Hệ số phát sinh = chiều cao của mạn trái - chiều cao của cây con bên phải

Hệ số cân bằng của nút có thể là -1, 0, 0 hoặc 1 cho cây cân bằng. Nếu yếu tố cân bằng vượt qua các giá trị này, cây cần thiết tái sử dụng thông qua quay.

Tính toán về yếu tố thăng bằng

Để xác định yếu tố cân bằng, trước tiên tìm chiều cao của mỗi cây con dưới gốc tại các nút con. Chiều cao là số cạnh trên con đường dài nhất từ nút đến một lá. trừ chiều cao của cây con bên phải từ chiều cao của cây dưới bên trái để có được yếu tố cân bằng.

Ví dụ, nếu các cây dưới bên trái có chiều cao 3 và các cây con bên phải có chiều cao 1, sau đó các yếu tố cân bằng là 2, cho thấy các nút là không cân bằng và cần quay.

Những ứng dụng của yếu tố thăng bằng

Yếu tố cân bằng được sử dụng trong khi chèn và xoá để duy trì sự cân bằng của cây AVL. Khi yếu tố cân bằng của nút trở thành bên ngoài phạm vi - 1 đến 1, quay được thực hiện để phục hồi cân bằng.

  • Xoay phải đơn
  • Xoay trái đơn
  • Xoay trái- phải
  • Xoay phải- trái

Những hoạt động này giúp giữ cho chiều cao của cây được tối thiểu, đảm bảo hiệu suất tối ưu cho các hoạt động tìm kiếm.