Cây nhị phân tìm kiếm cân bằng (AVL)

Cây AVL là cây nhị phân tìm kiếm sao cho tại mỗi node, chiều cao của nhánh phải và nhánh trái chênh lệch nhau không quá 1.
Chỉ số cân bằng bf = Chiều cao nhánh trái  - Chiều cao nhánh phải
=> bf = { 0; 1; -1}
Vì tính chất như vậy nên mỗi khi chèn node vào ta phải chỉnh sửa lại chỉ số cân bằng của các node, và nếu như tại node nào đó chỉ số bf không thỏa (cây bị lệch sang 1 bên) thì ta tiến hành xoay cây về bên còn lại.
Ta sẽ có lệch trái và lệch phải, tương ứng với xoay phải, xoay trái.
- Lệch trái gồm 3 trường hợp: lệch trái - trái, lệch trái - phải, lệch trái - cân  bằng.
- Lệch phải gồm 3 trường hợp: lệch phải - phải, lệch phải - trái, lệch phải - cân bằng.
Ta xét các ví dụ về lệch phải:
- Lệch phải - phải: p->bf = -2  &&  q->bf = -1

- Lệch phải - trái: p->bf = -2 && q->bf = 1

- Lệch phải - cân bằng: p->bf = -2 && q->bf = 0


Ta xét thêm 2 ví dụ nữa:

Cài đặt cây AVL
          1. Định nghĩa lại node:
struct Node
{
int Info, bf;
Node *pLeft, *pRight;
};
          2. Các hàm xoay trái và phải:
              Để hiểu được code, ta cần xem kĩ lại những ví dụ ở trên.
void RotateLeft(Tree &p)
{
Tree q = p->pRight;
Tree r = q;
if(q->bf == 1)
{
r = q->pLeft;
q->pLeft = r->pRight;
r->pRight = q;
}
p->pRight = r->pLeft;
r->pLeft = p;
p = r;
if(r == q)
p->pLeft->bf = p->pRight->bf = 0;
else
{
switch(p->bf)
{
case 0:
p->pLeft->bf = p->pRight->bf = 0;
break;
case 1:
p->pLeft->bf = 0;
p->pRight->bf = -1;
break;
case -1:
p->pLeft->bf = 1;
p->pRight->bf = 0;
break;
}
}
p->bf = 0;
}

void RotateRight(Tree &p)
{
Tree q = p->pLeft;
Tree r = q;
if(q->bf == -1)
{
r = q->pRight;
q->pRight = r->pLeft;
r->pLeft = q;
}
p->pLeft = r->pRight;
r->pRight = p;
p = r;
if(r == q)
p->pLeft->bf = p->pRight->bf = 0;
else
{
switch(p->bf)
{
case 0:
p->pLeft->bf = p->pRight->bf = 0;
break;
case 1: 
p->pLeft->bf = 0;
p->pRight->bf = -1;
break;
case -1:
p->pLeft->bf = 1;
p->pRight->bf = 0;
break;
}
}
p->bf = 0;
}
             Dù là lệch bên nào thì sau khi xoay xong: p->bf = 0;

          3. Chèn node:

int InsertNode(Tree &tree, int x)
{
int k;
if(tree)
{
if(x == tree->Info)
return -1;
if(x < tree->Info)
{
k = InsertNode(tree->pLeft, x);
if(k == 1)
{
switch(tree->bf)
{
case 0: tree->bf = 1; return 1;
case -1: tree->bf = 0; return 0;
case 1: RotateRight(tree); return 0;
}
}
}
else
{
k = InsertNode(tree->pRight, x);
if(k == 1)
{
switch(tree->bf)
{
case 0: tree->bf = -1; return 1;
case 1: tree->bf = 0; return 0;
case -1: RotateLeft(tree); return 0;
}
}
}
}
else
{
tree = GetNode(x);
if(tree == NULL)
return -1;
return 1;
}
}