c++ : AVL tree insertion pseudocode

void insert (current, item) {

<___ find the right position and insert___>

if (it is the first node of the tree)

let it be the root, bf=0;

return;

// compare with the current node

//--- item has already in the tree

if (item’s key == current node’s key)  return;

//--- go to left

else if (item’s key is smaller)

if (left is not empty)  Insert (current_node_left_child, item);

else

set current_node’s left child to be item;

item’s bf = 0;

if (current_node’ bf is 0)  height_inc=TRUE;

<___Balance the tree___>

if (height_inc is TRUE)

if (current_node’s bf == 0)

current_node’s bf =1;

//height_inc = TRUE;

else if (current_node’s bf == -1)

current_node’s bf = 0;

height_inc = FALSE;

else if (current_node’s bf == 1)
if (current_node’s left child’s bf =1)
L_rotate (current_node);

current_node’s bf = current_node’s parent’s bf =0;

height_inc = FALSE;

else if (current_node’s left child’s bf =-1)

LR_rotate (current_node’s left child);

height_inc = FALSE;

return;

//--- go to right

else if (item’s key is larger)
if (right is not empty) Insert (current_node_right_child, item);
else

set current_node’s right child is item;

item’s bf = 0;

current_node’s bf ++;

if (current_node’s bf is +1) height_inc=TRUE;

<___Balance the tree___>

if (height_inc is TRUE)

if (current_node’s bf == 0)

current_node’s bf =-1;

//height_inc = TRUE;

else if (current_node’s bf == 1)

current_node’s bf = 0;

height_inc = FALSE;

else if (current_node’s bf == -1)
if (current_node’s left child’s bf =-1)
R_rotate (current_node);

current_node’s bf = current_node’s parent’s bf =0;

height_inc = FALSE;

else if (current_node’s left child’s bf = 1)

RL_rotate (current_node’s left child);

height_inc = FALSE;

return;

}