To implement an AVL tree, a concept balance factor is introduced (bal = height(right)-height(left)). Suppose an AVL tree is created by inserting to the tree the following keys sequentially: 5, 3, 6, 2, 4, 1 What is the balance factor of the node 2? (please note that the tree is still AVL)

Đáp án đúng: "-1". Chèn lần lượt 5, 3, 6, 2, 4, 1: 5 làm gốc, 3 sang trái, 6 sang phải, 2 là con trái của 3, 4 là con phải của 3. Khi chèn 1 xuống làm con trái của 2, nhánh trái của gốc cao ba tầng còn nhánh phải chỉ một tầng, nên hệ số cân bằng của 5 thành -2 và cây mất cân bằng kiểu trái-trái; phép quay phải tại 5 đưa 3 lên làm gốc, con trái là 2 (vẫn giữ con trái 1) và con phải là 5 (với con trái 4, con phải 6). Sau quay, nút 2 có cây con trái là nút 1 cao một tầng và cây con phải rỗng cao không tầng, nên hệ số bằng 0 trừ 1, tức -1. "1" là dấu ngược lại, chỉ đúng nếu 1 là con phải của 2, nhưng 1 nhỏ hơn 2 nên phải nằm bên trái. "0" đòi hai cây con của 2 cao bằng nhau, tức 2 phải có cả hai con hoặc không có con nào. "2" không thể xuất hiện khi cây vẫn là AVL, vì hệ số cân bằng ở mọi nút chỉ nhận -1, 0 hoặc 1.