Overriding the insert Method

Inserting an element into an AVL tree is the same as inserting it to a BST, except that the tree may need to be rebalanced. A new element is always inserted as a leaf node. As a result of adding a new node, the heights of the new leaf node’s ancestors may increase. After inserting a new node, check the nodes along the path from the new leaf node up to the root. If an unbalanced node is found, perform an appropriate rotation using the algorithm in the code below.

1 balancePath(E e) {
2 Get the path from the node that contains element e to the root,
3 as illustrated in Figure 26.9;
4 for each node A in the path leading to the root {
5 Update the height of A;
6 Let parentOfA denote the parent of A,
7 which is the next node in the path, or null if A is the root;
8
9 switch (balanceFactor(A)) {
10 case -2: if balanceFactor(A.left) == -1 or 0
11 Perform LL rotation; // See Figure 26.2
12 else
13 Perform LR rotation; // See Figure 26.4
14 break;
15 case +2: if balanceFactor(A.right) == +1 or 0
16 Perform RR rotation; // See Figure 26.3
17 else
18 Perform RL rotation; // See Figure 26.5
19 } // End of switch
20 } // End of for
21 } // End of method

The algorithm considers each node in the path from the new leaf node to the root. Update the height of the node on the path. If a node is balanced, no action is needed. If a node is not balanced, perform an appropriate rotation

The above is the detailed content of Overriding the insert Method. For more information, please follow other related articles on the PHP Chinese website!