In the previous section, we presented the basic algorithms on the new proposed structure. In order to consolidate it, it is possible to consider several options for the algorithms.
In the insertion phase, we can control, increase or decrease the number of extra nodes. Control is achieved by maintaining a given percentage of extra nodes. Increasing the number of extra nodes can be done during rotations. Decreasing the number of extra nodes is done by simulating the tree insertion operation before creating them. In the deletion phase, we can preserve some extra nodes. Finally, in the transformation phase, we can partially transform the tree. We develop all these options in the following sections.
Option 1 : Controling the presence of extra nodes (Insert operation)
We may not systematically create extra nodes as mentioned in the insert algorithm. For example, we may decide not to exceed a given threshold (percentage) or/and we may not to create them in the first few levels of the tree.
Option 2 : Adding extra nodes while rotating nodes (Insert operation)
Extra nodes are first created as leaves. Then, after insert and/or delete operations they can appeared in any level of the tree, except the root. During rotation operations, conditions can become favorable to create other extra nodes. This occurs either after a right rotation or a double rotation. After a right rotation of node A having node B as a left child, node A is converted into an extra node if the left child of node A is a missing node and both nodes A and B are not parents of extra nodes. Since an ordinary node disappears, we have to go back up the tree to check the balance factors of the ancestors of this ordinary node and if necessary perform rotations. In other words, it's like we are removing an ordinary node. A similar treatment is done while performing a right rotation in a double rotation. Figure 10 shows all the cases. The predicate Ordinary (Node) is true is Node is an ordinary node.
Option 3 : Simulating AVL-insert while creating extra nodes(Insert operation).
While inserting items, an ordinary node is only transformed into an extra node if it does not trigger a restructuring. An AVL-2 tree insertion simulation is then performed. Figure 11 shows two examples. The insert of value 15 in AVL-2 tree (a) gives a negative simulation, i.e., no restructuring is required. Value 15 is then inserted as an extra node. The insert of value 10 in AVL-2 tree (b) gives a positive simulation, i.e., restructuring is required. Value 10 is not inserted as an extra node. It is then inserted as in an AVL tree.
The simulation consists in browsing the stack as a list without updating the 'Balance' fields of the nodes of the tree. The simulation stops as soon as the balance of a node becomes equal to 0, -2 or + 2. For 0, the simulation is negative. For + 2 and − 2, it is positive.
Note that the simulation does not rotate nodes and that it is performed in O(lg2(N)).
Option 4 : Simulating AVL tree insert while creating extra nodes and Simulating AVL tree delete when creating extra node during rotation (Insert operation).
Each time an extra node is about to be created, including during rotations, a simulation is made. If this is negative, an extra node is created.
As mentioned in option 2, during a rotation, an ordinary node can be converted into an extra node if the conditions are met. This conversion may involve a restructuring of the tree. In this option, during a rotation, an extra node is generated only if it does not cause a restructuring. A simulation of the deletion algorithm is then made.
Option 5 : Preserving extra nodes (Delete operation)
Recall that there are two cases to delete an element (Section 4.3)
(i)Case of ordinary nodes that are not parents of extra nodes:
(ii)Case of extra nodes or ordinary nodes that are parents of extra nodes:
The algorithm presented in Section 4.3 addresses case (ii) by eliminating all extra nodes. Another variant of the delete algorithm consists of preserving them as far as possible.
It is the following:
Case (ii) of the new variant can be stated as follows:
(i) If the node to delete P is the parent of an extra node E then
- If the left child of P is a missing node, eliminate node P. The parent of node P points E. If the node P’s parent does not exist, E becomes the new root of the tree. E becomes an ordinary node and inherits the balance factor of P. In this case, the extra node is not preserved.
- If the left child of P is not a missing node, replace Item(P) by Item( Inorder_predecessor(P)). Two cases are to consider:
If the inorder predecessor of P is not an extra node, go up the tree to update the balance factors of the ancestors by incrementing the balance factor if we go up from the right and by decrementing it if we go up from the left. If necessary, make rotations.
If the inorder predecessor is an extra node, the process ends but an extra node disappears.
(ii) If the node to delete E is an extra node then
- If the right child of E is a missing node, eliminate node E. P points then that missing node. The extra node is not preserved.
- If the right child of E is not a missing node, replace Item(E) by Item (Inorder_successor(E)).E is then preserved. Then, according to the nature of the inorder successor make (a) or (b) as described hereafter:
If the inorder successor is the parent of an extra node, transform that extra node to an ordinary node. Furthermore, it inherits from configuration of its parent. In this case, the extra node is not preserved. The process ends.
If the inorder successor is not the parent of an extra node, go up the tree to update the balance factors of the ancestors by incrementing the balance factor if we go up from the right and by decrementing it if we go up from the left. If necessary, make rotations.
We give below a scenario for this another variant of the delete algorithm in an AVL-2 tree.
Recall that in this variant, we try to preserve extra nodes. Figure 12 − 1 shows the delete of two values from an AVL-2 tree.
a The AVL-2 tree in Fig. 12 − 1(a) is the tree before deleting values.
b The deleted value is 48. Value 48 is in range [44, 48]. It is an extra node. 48 is replaced by its inorder successor 67. The extra node is preserved.
c The deleted value is 29. Node with value 33 points node with value 20. The balance factor of the root becomes − 2. A left rotation of node with value 33 is performed.
Figure 12 − 2 shows the delete of three other values from the AVL-2 tree of Fig. 12 − 1 (c).
d The deleted value is 33. Value 33 is in range [33, 42]. It is the parent an extra node. Value 33 is replaced by its inorder predecessor 20. Bf(20) becomes 1. The balance factor of the root remains unchanged.
e The deleted value is 95 that is an ordinary node. Value 93 replaces value 95.
f The deleted value is 67 that is an extra node. An extra node disappears.
Figure 12 − 3 shows the delete of all the values from the AVL-2 tree of Fig. 12 − 2 (f).
(g) The deleted value is 76. Value 76 is in range [68, 76]. Value 76 est replaced by 93. An extra node is preserved. The balance factor of node with value 68 becomes − 2. A left rotation of node with value 20 is performed followed by a right rotation of node with value 68.
(h) and (i) The deleted values are 93 and 42. Two extra nodes disappear.
(j) and (k) The deleted value are 68 and 44. they are deleted as ordinary nodes.
Option 6 : Transforming partially the AVL-2 tree (Transformation operation)
Recall that the goal of the transformation is to eliminate all extra nodes in order to have an AVL tree. However, the transformation can be partial, i.e., it can remove either only a percentage of the extra nodes present in the AVL-2 tree, or lower-level nodes. Indeed, the elimination of extra nodes in the low levels of the tree improves the quality of the AVL-2 tree.