Chọn định nghĩa đúng nhất về cây cân bằng tương đối:

Cây cân bằng tương đối là một cây nhị phân thỏa mãn điều kiện là đối với mọi nút của cây thì số nút của cây con trái và số nút của cây con phải của nút đó hơn kém nhau không quá 1. Cây cân bằng tương đối còn được gọi là cây AVL (AVL tree)

Cây cân bằng tương đối là một cây N phân thỏa mãn điều kiện là đối với mọi nút của cây thì chiều cao của cây con trái và chiều cao của cây con phải của nút đó hơn kém nhau không quá 2. Cây cân bằng tương đối còn được gọi là cây AVL (AVL tree)

Cây cân bằng tương đối là một cây nhị phân thỏa mãn điều kiện là đối với mọi nút của cây thì chiều cao của cây con trái và chiều cao của cây con phải của nút đó hơn kém nhau không quá 1. Cây cân bằng tương đối còn được gọi là cây AVL (AVL tree)

Cây cân bằng tương đối cũng là cây cân bằng hoàn toàn

Đáp án đúng: C

Cây cân bằng tương đối, hay còn gọi là cây AVL, là một cây nhị phân đặc biệt. Điều kiện cân bằng của cây AVL là: với mọi nút trên cây, chiều cao của cây con trái và chiều cao của cây con phải của nút đó phải hơn kém nhau không quá 1. Điều này đảm bảo cây không bị lệch quá nhiều, giúp cho các thao tác tìm kiếm, thêm, xóa nút có độ phức tạp thời gian là O(log n), với n là số nút của cây. Phương án 1 sai vì điều kiện cân bằng của cây AVL dựa trên chiều cao, không phải số nút. Phương án 2 sai vì cây AVL là cây nhị phân, không phải cây N phân, và điều kiện chiều cao cũng sai. Phương án 4 sai vì cây cân bằng tương đối (AVL) không phải là cây cân bằng hoàn toàn. Cây cân bằng hoàn toàn là một trường hợp đặc biệt của cây nhị phân mà tất cả các mức đều được lấp đầy hoàn toàn, ngoại trừ có thể mức cuối cùng không đầy đủ và các nút ở mức cuối cùng được dồn về bên trái.