AVL tree

AVL tree
You are encouraged to solve this task according to the task description, using any language you may know.

This page uses content from Wikipedia. The original article was at AVL tree. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)

In computer science, an AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; at no time do they differ by more than one because rebalancing is done ensure this is the case. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree rotations. Note the tree of nodes comprise a set, so duplicate node keys are not allowed.

AVL trees are often compared with red-black trees because they support the same set of operations and because red-black trees also take O(log n) time for the basic operations. Because AVL trees are more rigidly balanced, they are faster than red-black trees for lookup-intensive applications. Similar to red-black trees, AVL trees are height-balanced, but in general not weight-balanced nor μ-balanced; that is, sibling nodes can have hugely differing numbers of descendants.

Task

Implement an AVL tree in the language of choice, and provide at least basic operations.

AArch64 Assembly

Works with: as version Raspberry Pi 3B version Buster 64 bits

<lang AArch64 Assembly> /* ARM assembly AARCH64 Raspberry PI 3B */ /* program avltree64.s */

/*******************************************/ /* Constantes file */ /*******************************************/ /* for this file see task include a file in language AArch64 assembly*/ .include "../includeConstantesARM64.inc"

.equ NBVAL, 12

/*******************************************/ /* Structures */ /********************************************/ /* structure tree */

   .struct  0

tree_root: // root pointer (or node right)

   .struct  tree_root + 8 

tree_size: // number of element of tree

   .struct  tree_size + 8 

tree_suite:

   .struct  tree_suite + 24           // for alignement to node

tree_fin: /* structure node tree */

   .struct  0

node_right: // right pointer

   .struct  node_right + 8 

node_left: // left pointer

   .struct  node_left + 8 

node_value: // element value

   .struct  node_value + 8 

node_height: // element value

   .struct  node_height + 8 

node_parent: // element value

   .struct  node_parent + 8

node_fin:

/*******************************************/ /* Initialized data */ /*******************************************/ .data szMessPreOrder: .asciz "PreOrder :\n" szCarriageReturn: .asciz "\n" /* datas error display */ szMessErreur: .asciz "Error detected.\n" szMessKeyDbl: .asciz "Key exists in tree.\n" szMessInsInv: .asciz "Insertion in inverse order.\n" /* datas message display */ szMessResult: .asciz "Ele: @ G: @ D: @ val @ h @ \npere @\n"

/*******************************************/ /* UnInitialized data */ /*******************************************/ .bss sZoneConv: .skip 24 stTree: .skip tree_fin // place to structure tree stTree1: .skip tree_fin // place to structure tree /*******************************************/ /* code section */ /*******************************************/ .text .global main main:

   mov x20,#1                           // node tree value

1: // loop insertion in order

   ldr x0,qAdrstTree                   // structure tree address
   mov x1,x20
   bl insertElement                    // add element value x1
   cmp x0,-1
   beq 99f
   add x20,x20,1                           // increment value
   cmp x20,NBVAL                       // end ?
   ble 1b                              // no -> loop

   ldr x0,qAdrstTree                   // structure tree address
   mov x1,11                           // verif key dobble
   bl insertElement                    // add element value x1
   cmp x0,-1
   bne 2f
   ldr x0,qAdrszMessErreur
   bl affichageMess

2:

   ldr x0,qAdrszMessPreOrder           // load verification
   bl affichageMess
   ldr x3,qAdrstTree                   // tree root address (begin structure)
   ldr x0,[x3,tree_root]
   ldr x1,qAdrdisplayElement           // function to execute
   bl preOrder
   

   ldr x0,qAdrszMessInsInv
   bl affichageMess
   mov x20,NBVAL                       // node tree value

3: // loop insertion inverse order

   ldr x0,qAdrstTree1                  // structure tree address
   mov x1,x20
   bl insertElement                    // add element value x1
   cmp x0,-1
   beq 99f
   sub x20,x20,1                           // increment value
   cmp x20,0                           // end ?
   bgt 3b                              // no -> loop

   ldr x0,qAdrszMessPreOrder           // load verification
   bl affichageMess
   ldr x3,qAdrstTree1                  // tree root address (begin structure)
   ldr x0,[x3,tree_root]
   ldr x1,qAdrdisplayElement           // function to execute
   bl preOrder

                                       // search value
   ldr x0,qAdrstTree1                  // tree root address (begin structure)
   mov x1,11                          // value to search
   bl searchTree
   cmp x0,-1
   beq 100f
   mov x2,x0
   ldr x0,qAdrszMessKeyDbl             // key exists
   bl affichageMess
                                       // suppresssion previous value
   mov x0,x2
   ldr x1,qAdrstTree1
   bl supprimer

   ldr x0,qAdrszMessPreOrder           // verification
   bl affichageMess
   ldr x3,qAdrstTree1                  // tree root address (begin structure)
   ldr x0,[x3,tree_root]
   ldr x1,qAdrdisplayElement           // function to execute
   bl preOrder

   b 100f

99: // display error

   ldr x0,qAdrszMessErreur
   bl affichageMess

100: // standard end of the program

   mov x8, #EXIT                       // request to exit program
   svc 0                               // perform system call

qAdrszMessPreOrder: .quad szMessPreOrder qAdrszMessErreur: .quad szMessErreur qAdrszCarriageReturn: .quad szCarriageReturn qAdrstTree: .quad stTree qAdrstTree1: .quad stTree1 qAdrdisplayElement: .quad displayElement qAdrszMessInsInv: .quad szMessInsInv /******************************************************************/ /* insert element in the tree */ /******************************************************************/ /* x0 contains the address of the tree structure */ /* x1 contains the value of element */ /* x0 returns address of element or - 1 if error */ insertElement: // INFO: insertElement

   stp x1,lr,[sp,-16]!               // save  registers
   mov x6,x0                         // save head
   mov x0,#node_fin                  // reservation place one element
   bl allocHeap
   cmp x0,#-1                        // allocation error
   beq 100f
   mov x5,x0
   str x1,[x5,#node_value]           // store value in address heap
   mov x3,#0
   str x3,[x5,#node_left]            // init left pointer with zero
   str x3,[x5,#node_right]           // init right pointer with zero
   str x3,[x5,#node_height]          // init balance with zero
   ldr x2,[x6,#tree_size]            // load tree size
   cmp x2,#0                         // 0 element ?
   bne 1f
   str x5,[x6,#tree_root]            // yes -> store in root
   b 4f

1: // else search free address in tree

   ldr x3,[x6,#tree_root]            // start with address root

2: // begin loop to insertion

   ldr x4,[x3,#node_value]           // load key 
   cmp x1,x4
   beq 6f                            // key equal
   blt 3f                            // key <
                                     // key >  insertion right
   ldr x8,[x3,#node_right]           // node empty ?
   cmp x8,#0
   csel x3,x8,x3,ne                  // current = right node if not
   //movne x3,x8                       // no -> next node
   bne 2b                            // and loop
   str x5,[x3,#node_right]           // store node address in right pointer
   b 4f

3: // left

   ldr x8,[x3,#node_left]            // left pointer empty ?
   cmp x8,#0
   csel x3,x8,x3,ne                  // current = left node if not
   //movne x3,x8                       //
   bne 2b                            // no -> loop
   str x5,[x3,#node_left]            // store node address in left pointer

4:

   str x3,[x5,#node_parent]          // store parent
   mov x4,#1
   str x4,[x5,#node_height]          // store height = 1
   mov x0,x5                         // begin node to requilbrate
   mov x1,x6                         // head address
   bl equilibrer

5:

   add x2,x2,#1                        // increment tree size
   str x2,[x6,#tree_size]
   mov x0,#0
   b 100f

6: // key equal ?

   ldr x0,qAdrszMessKeyDbl
   bl affichageMess
   mov x0,#-1
   b 100f

100:

   ldp x1,lr,[sp],16              // restaur  2 registers
   ret                            // return to address lr x30

qAdrszMessKeyDbl: .quad szMessKeyDbl /******************************************************************/ /* equilibrer after insertion */ /******************************************************************/ /* x0 contains the address of the node */ /* x1 contains the address of head */ equilibrer: // INFO: equilibrer

   stp x1,lr,[sp,-16]!           // save  registers
   stp x2,x3,[sp,-16]!           // save  registers
   stp x4,x5,[sp,-16]!           // save  registers
   stp x6,x7,[sp,-16]!           // save  registers
   mov x3,#0                     // balance factor

1: // begin loop

   ldr x5,[x0,#node_parent]      // load father
   cmp x5,#0                     // end ?
   beq 8f
   cmp x3,#2                     // right tree too long
   beq 8f
   cmp x3,#-2                    // left tree too long
   beq 8f
   mov x6,x0                     // s = current
   ldr x0,[x6,#node_parent]      // current = father
   ldr x7,[x0,#node_left]
   mov x4,#0
   cmp x7,#0
   beq 2f
   ldr x4,[x7,#node_height]     // height left tree 

2:

   ldr x7,[x0,#node_right]
   mov x2,#0
   cmp x7,#0
   beq 3f
   ldr x2,[x7,#node_height]     // height right tree 

3:

   cmp x4,x2
   ble 4f
   add x4,x4,#1
   str x4,[x0,#node_height]
   b 5f

4:

   add x2,x2,#1
   str x2,[x0,#node_height]

5:

   ldr x7,[x0,#node_right]
   mov x4,0
   cmp x7,#0
   beq 6f
   ldr x4,[x7,#node_height]

6:

   ldr x7,[x0,#node_left]
   mov x2,0
   cmp x7,#0
   beq 7f
   ldr x2,[x7,#node_height]

7:

   sub x3,x4,x2                    // compute balance factor
   b 1b

8:

   cmp x3,#2
   beq 9f
   cmp x3,#-2
   beq 9f
   b 100f

9:

   mov x3,x1
   mov x4,x0
   mov x1,x6
   bl equiUnSommet
                                     // change head address ?
   ldr x2,[x3,#tree_root]
   cmp x2,x4
   bne 100f
   str x6,[x3,#tree_root]

100:

   ldp x6,x7,[sp],16              // restaur  2 registers
   ldp x4,x5,[sp],16              // restaur  2 registers
   ldp x2,x3,[sp],16              // restaur  2 registers
   ldp x1,lr,[sp],16              // restaur  2 registers
   ret                            // return to address lr x30

/******************************************************************/ /* equilibre 1 sommet */ /******************************************************************/ /* x0 contains the address of the node */ /* x1 contains the address of the node */ equiUnSommet: // INFO: equiUnSommet

   stp x1,lr,[sp,-16]!           // save  registers
   stp x2,x3,[sp,-16]!           // save  registers
   stp x4,x5,[sp,-16]!           // save  registers
   stp x6,x7,[sp,-16]!           // save  registers
   mov x5,x0                             // save p
   mov x6,x1    // s
   ldr x2,[x5,#node_left]
   cmp x2,x6
   bne 6f
   ldr x7,[x5,#node_right]
   mov x4,#0
   cmp x7,#0
   beq 1f
   ldr x4,[x7,#node_height]

1:

   ldr x7,[x5,#node_left]
   mov x2,0
   cmp x7,#0
   beq 2f
   ldr x2,[x7,#node_height]

2:

   sub x3,x4,x2
   cmp x3,#-2
   bne 100f
   ldr x7,[x6,#node_right]
   mov x4,0
   cmp x7,#0
   beq 3f
   ldr x4,[x7,#node_height]

3:

   ldr x7,[x6,#node_left]
   mov x2,0
   cmp x7,#0
   beq 4f
   ldr x2,[x7,#node_height]

4:

   sub x3,x4,x2
   cmp x3,#1
   bge 5f
   mov x0,x5
   bl rotRight
   b 100f

5:

   mov x0,x6
   bl rotLeft
   mov x0,x5
   bl rotRight
   b 100f

6:

   ldr x7,[x5,#node_right]
   mov x4,0
   cmp x7,#0
   beq 7f
   ldr x4,[x7,#node_height]

7:

   ldr x7,[x5,#node_left]
   mov x2,0
   cmp x7,#0
   beq 8f
   ldr x2,[x7,#node_height]

8:

   sub x3,x4,x2
   cmp x3,2
   bne 100f
   ldr x7,[x6,#node_right]
   mov x4,0
   cmp x7,#0
   beq 9f
   ldr x4,[x7,#node_height]

9:

   ldr x7,[x6,#node_left]
   mov x2,0
   cmp x7,#0
   beq 10f
   ldr x2,[x7,#node_height]

10:

   sub x3,x4,x2
   cmp x3,#-1
   ble 11f
   mov x0,x5
   bl rotLeft
   b 100f

11:

   mov x0,x6
   bl rotRight
   mov x0,x5
   bl rotLeft

100:

   ldp x6,x7,[sp],16              // restaur  2 registers
   ldp x4,x5,[sp],16              // restaur  2 registers
   ldp x2,x3,[sp],16              // restaur  2 registers
   ldp x1,lr,[sp],16              // restaur  2 registers
   ret                            // return to address lr x30

/******************************************************************/ /* right rotation */ /******************************************************************/ /* x0 contains the address of the node */ rotRight: // INFO: rotRight

   stp x1,lr,[sp,-16]!           // save  registers
   stp x2,x3,[sp,-16]!           // save  registers
   stp x4,x5,[sp,-16]!           // save  registers
   //   x2                  x2
   //      x0                   x1
   //   x1                         x0
   //      x3                    x3
   ldr x1,[x0,#node_left]          // load left children
   ldr x2,[x0,#node_parent]        // load father
   cmp x2,#0                       // no father ???
   beq 2f
   ldr x3,[x2,#node_left]          // load left node father
   cmp x3,x0                       // equal current node ?
   bne 1f
   str x1,[x2,#node_left]        // yes store left children
   b 2f

1:

   str x1,[x2,#node_right]       // no store right

2:

   str x2,[x1,#node_parent]        // change parent
   str x1,[x0,#node_parent]
   ldr x3,[x1,#node_right]
   str x3,[x0,#node_left]
   cmp x3,#0
   beq 3f
   str x0,[x3,#node_parent]      // change parent node left

3:

   str x0,[x1,#node_right]

   ldr x3,[x0,#node_left]          // compute newbalance factor 
   mov x4,0
   cmp x3,#0
   beq 4f
   ldr x4,[x3,#node_height]

4:

   ldr x3,[x0,#node_right]
   mov x5,0
   cmp x3,#0
   beq 5f
   ldr x5,[x3,#node_height]

5:

   cmp x4,x5
   ble 6f
   add x4,x4,#1
   str x4,[x0,#node_height]
   b 7f

6:

   add x5,x5,#1
   str x5,[x0,#node_height]

7: //

   ldr x3,[x1,#node_left]         // compute new balance factor
   mov x4,0
   cmp x3,#0
   beq 8f
   ldr x4,[x3,#node_height]

8:

   ldr x3,[x1,#node_right]
   mov x5,0
   cmp x3,#0
   beq 9f
   ldr x5,[x3,#node_height]

9:

   cmp x4,x5
   ble 10f
   add x4,x4,#1
   str x4,[x1,#node_height]
   b 100f

10:

   add x5,x5,#1
   str x5,[x1,#node_height]

100:

   ldp x4,x5,[sp],16              // restaur  2 registers
   ldp x2,x3,[sp],16              // restaur  2 registers
   ldp x1,lr,[sp],16              // restaur  2 registers
   ret                            // return to address lr x30

/******************************************************************/ /* left rotation */ /******************************************************************/ /* x0 contains the address of the node sommet */ rotLeft: // INFO: rotLeft

   stp x1,lr,[sp,-16]!              // save  registers
   stp x2,x3,[sp,-16]!              // save  registers
   stp x4,x5,[sp,-16]!              // save  registers
   //   x2                  x2
   //      x0                   x1
   //          x1            x0
   //        x3                 x3
   ldr x1,[x0,#node_right]          // load right children
   ldr x2,[x0,#node_parent]         // load father (racine)
   cmp x2,#0                        // no father ???
   beq 2f
   ldr x3,[x2,#node_left]           // load left node father
   cmp x3,x0                        // equal current node ?
   bne 1f
   str x1,[x2,#node_left]         // yes store left children
   b 2f

1:

   str x1,[x2,#node_right]        // no store to right

2:

   str x2,[x1,#node_parent]         // change parent of right children
   str x1,[x0,#node_parent]         // change parent of sommet
   ldr x3,[x1,#node_left]           // left children 
   str x3,[x0,#node_right]          // left children pivot exists ? 
   cmp x3,#0
   beq 3f
   str x0,[x3,#node_parent]       // yes store in 

3:

   str x0,[x1,#node_left]

//

   ldr x3,[x0,#node_left]           // compute new height for old summit
   mov x4,0
   cmp x3,#0
   beq 4f
   ldr x4,[x3,#node_height]       // left height

4:

   ldr x3,[x0,#node_right]
   mov x5,0
   cmp x3,#0
   beq 5f
   ldr x5,[x3,#node_height]       // right height

5:

   cmp x4,x5
   ble 6f
   add x4,x4,#1
   str x4,[x0,#node_height]       // if right > left
   b 7f

6:

   add x5,x5,#1
   str x5,[x0,#node_height]       // if left > right

7: //

   ldr x3,[x1,#node_left]           // compute new height for new
   mov x4,0
   cmp x3,#0
   beq 8f
   ldr x4,[x3,#node_height]

8:

   ldr x3,[x1,#node_right]
   mov x5,0
   cmp x3,#0
   beq 9f
   ldr x5,[x3,#node_height]

9:

   cmp x4,x5
   ble 10f
   add x4,x4,#1
   str x4,[x1,#node_height]
   b 100f

10:

   add x5,x5,#1
   str x5,[x1,#node_height]

100:

   ldp x4,x5,[sp],16              // restaur  2 registers
   ldp x2,x3,[sp],16              // restaur  2 registers
   ldp x1,lr,[sp],16              // restaur  2 registers
   ret                            // return to address lr x30

/******************************************************************/ /* search value in tree */ /******************************************************************/ /* x0 contains the address of structure of tree */ /* x1 contains the value to search */ searchTree: // INFO: searchTree

   stp x2,lr,[sp,-16]!              // save  registers
   stp x3,x4,[sp,-16]!              // save  registers
   ldr x2,[x0,#tree_root]

1: // begin loop

   ldr x4,[x2,#node_value]           // load key 
   cmp x1,x4
   beq 3f                            // key equal
   blt 2f                            // key <
                                     // key >  insertion right
   ldr x3,[x2,#node_right]           // node empty ?
   cmp x3,#0
   csel x2,x3,x2,ne
   //movne x2,x3                       // no -> next node
   bne 1b                            // and loop
   mov x0,#-1                        // not find
   b 100f

2: // left

   ldr x3,[x2,#node_left]            // left pointer empty ?
   cmp x3,#0
   csel x2,x3,x2,ne
   bne 1b                            // no -> loop
   mov x0,#-1                        // not find
   b 100f

3:

   mov x0,x2                         // return node address

100:

   ldp x3,x4,[sp],16              // restaur  2 registers
   ldp x2,lr,[sp],16              // restaur  2 registers
   ret                            // return to address lr x30

/******************************************************************/ /* suppression node */ /******************************************************************/ /* x0 contains the address of the node */ /* x1 contains structure tree address */ supprimer: // INFO: supprimer

   stp x1,lr,[sp,-16]!           // save  registers
   stp x2,x3,[sp,-16]!           // save  registers
   stp x4,x5,[sp,-16]!           // save  registers
   stp x6,x7,[sp,-16]!           // save  registers
   ldr x1,[x0,#node_left]
   cmp x1,#0
   bne 5f
   ldr x1,[x0,#node_right]
   cmp x1,#0
   bne 5f
                                // is a leaf
   mov x4,#0
   ldr x3,[x0,#node_parent]     // father
   cmp x3,#0
   bne 11f
   str x4,[x1,#tree_root]
   b 100f

11:

   ldr x1,[x3,#node_left]
   cmp x1,x0
   bne 2f
   str x4,[x3,#node_left]       // suppression left children
   ldr x5,[x3,#node_right]
   mov x6,#0
   cmp x5,#0
   beq 12f
   ldr x6,[x5,#node_height]

12:

   add x6,x6,#1
   str x6,[x3,#node_height]
   b 3f

2: // suppression right children

   str x4,[x3,#node_right]
   ldr x5,[x3,#node_left]
   mov x6,#0
   cmp x5,#0
   beq 21f
   ldr x6,[x5,#node_height]

21:

   add x6,x6,#1
   str x6,[x3,#node_height]

3: // new balance

   mov x0,x3
   bl equilibrerSupp
   b 100f

5: // is not à leaf

   ldr x7,[x0,#node_right]
   cmp x7,#0
   beq 7f
   mov x2,x0
   mov x0,x7

6:

   ldr x6,[x0,#node_left]  // search the litle element
   cmp x6,#0
   beq 9f
   mov x0,x6
   b 6b

7:

   ldr x7,[x0,#node_left]        
   cmp x7,#0
   beq 9f
   mov x2,x0
   mov x0,x7

8:

   ldr x6,[x0,#node_right]        // search the great element
   cmp x6,#0
   beq 9f
   mov x0,x6
   b 8b

9:

   ldr x5,[x0,#node_value]         // copy value
   str x5,[x2,#node_value]
   bl supprimer                    // suppression node x0

100:

   ldp x6,x7,[sp],16              // restaur  2 registers
   ldp x4,x5,[sp],16              // restaur  2 registers
   ldp x2,x3,[sp],16              // restaur  2 registers
   ldp x1,lr,[sp],16              // restaur  2 registers
   ret                            // return to address lr x30

/******************************************************************/ /* equilibrer after suppression */ /******************************************************************/ /* x0 contains the address of the node */ /* x1 contains the address of head */ equilibrerSupp: // INFO: equilibrerSupp

   stp x1,lr,[sp,-16]!           // save  registers
   stp x2,x3,[sp,-16]!           // save  registers
   stp x4,x5,[sp,-16]!           // save  registers
   stp x6,x7,[sp,-16]!           // save  registers
   mov x3,#1                     // balance factor
   ldr x2,[x1,#tree_root]

1:

   ldr x5,[x0,#node_parent]      // load father
   cmp x5,#0                     // no father 
   beq 100f
   cmp x3,#0                     // balance equilibred
   beq 100f
   mov x6,x0                     // save entry node
   ldr x0,[x6,#node_parent]      // current = father
   ldr x7,[x0,#node_left]
   mov x4,#0
   cmp x7,#0
   b 11f
   ldr x4,[x7,#node_height]    // height left tree 

11:

   ldr x7,[x0,#node_right]
   mov x5,#0
   cmp x7,#0
   beq 12f
   ldr x5,[x7,#node_height]    // height right tree 

12:

   cmp x4,x5
   ble 13f
   add x4,x4,1
   str x4,[x0,#node_height]
   b 14f

13:

   add x5,x5,1
   str x5,[x0,#node_height]

14:

   ldr x7,[x0,#node_right]
   mov x4,#0
   cmp x7,#0
   beq 15f
   ldr x4,[x7,#node_height]

15:

   ldr x7,[x0,#node_left]
   mov x5,0
   cmp x7,#0
   beq 16f
   ldr x5,[x7,#node_height]

16:

   sub x3,x4,x5                   // compute balance factor
   mov x2,x1
   mov x7,x0                      // save current
   mov x1,x6
   bl equiUnSommet
                                  // change head address ?
   cmp x2,x7
   bne 17f
   str x6,[x3,#tree_root]

17:

   mov x0,x7                      // restaur current
   b 1b

100:

   ldp x6,x7,[sp],16              // restaur  2 registers
   ldp x4,x5,[sp],16              // restaur  2 registers
   ldp x2,x3,[sp],16              // restaur  2 registers
   ldp x1,lr,[sp],16              // restaur  2 registers
   ret                            // return to address lr x30

/******************************************************************/ /* preOrder */ /******************************************************************/ /* x0 contains the address of the node */ /* x1 function address */ preOrder: // INFO: preOrder

   stp x2,lr,[sp,-16]!           // save  registers
   cmp x0,#0
   beq 100f
   mov x2,x0
   blr x1                                // call function
   ldr x0,[x2,#node_left]
   bl preOrder
   ldr x0,[x2,#node_right]
   bl preOrder

100:

   ldp x2,lr,[sp],16              // restaur  2 registers
   ret                            // return to address lr x30

/******************************************************************/ /* display node */ /******************************************************************/ /* x0 contains node address */ displayElement: // INFO: displayElement

   stp x1,lr,[sp,-16]!           // save  registers
   stp x2,x3,[sp,-16]!           // save  registers
   stp x4,x5,[sp,-16]!           // save  registers
   mov x2,x0
   ldr x1,qAdrsZoneConv
   bl conversion16
   //strb wzr,[x1,x0]
   ldr x0,qAdrszMessResult
   ldr x1,qAdrsZoneConv
   bl strInsertAtCharInc
   mov x3,x0
   ldr x0,[x2,#node_left]
   ldr x1,qAdrsZoneConv
   bl conversion16
   //strb wzr,[x1,x0]
   mov x0,x3
   ldr x1,qAdrsZoneConv
   bl strInsertAtCharInc
   mov x3,x0
   ldr x0,[x2,#node_right]
   ldr x1,qAdrsZoneConv
   bl conversion16
   //strb wzr,[x1,x0]
   mov x0,x3
   ldr x1,qAdrsZoneConv
   bl strInsertAtCharInc
   mov x3,x0
   ldr x0,[x2,#node_value]
   ldr x1,qAdrsZoneConv
   bl conversion10
   //strb wzr,[x1,x0]
   mov x0,x3
   ldr x1,qAdrsZoneConv
   bl strInsertAtCharInc
   mov x3,x0
   ldr x0,[x2,#node_height]
   ldr x1,qAdrsZoneConv
   bl conversion10
   //strb wzr,[x1,x0]
   mov x0,x3
   ldr x1,qAdrsZoneConv
   bl strInsertAtCharInc
   mov x3,x0
   ldr x0,[x2,#node_parent]
   ldr x1,qAdrsZoneConv
   bl conversion16
   //strb wzr,[x1,x0]
   mov x0,x3
   ldr x1,qAdrsZoneConv
   bl strInsertAtCharInc
   bl affichageMess

100:

   ldp x4,x5,[sp],16              // restaur  2 registers
   ldp x2,x3,[sp],16              // restaur  2 registers
   ldp x1,lr,[sp],16              // restaur  2 registers
   ret                            // return to address lr x30

qAdrszMessResult: .quad szMessResult qAdrsZoneConv: .quad sZoneConv

/******************************************************************/ /* memory allocation on the heap */ /******************************************************************/ /* x0 contains the size to allocate */ /* x0 returns address of memory heap or - 1 if error */ /* CAUTION : The size of the allowance must be a multiple of 4 */ allocHeap:

   stp x1,lr,[sp,-16]!            // save  registers
   stp x2,x8,[sp,-16]!            // save  registers
   // allocation
   mov x1,x0                      // save size
   mov x0,0                       // read address start heap
   mov x8,BRK                     // call system 'brk'
   svc 0
   mov x2,x0                      // save address heap for return
   add x0,x0,x1                   // reservation place for size
   mov x8,BRK                     // call system 'brk'
   svc 0
   cmp x0,-1                      // allocation error
   beq 100f
   mov x0,x2                      // return address memory heap

100:

   ldp x2,x8,[sp],16              // restaur  2 registers
   ldp x1,lr,[sp],16              // restaur  2 registers
   ret                            // return to address lr x30

/********************************************************/ /* File Include fonctions */ /********************************************************/ /* for this file see task include a file in language AArch64 assembly */ .include "../includeARM64.inc" </lang>

Agda

This implementation uses the type system to enforce the height invariants, though not the BST invariants <lang agda> module Avl where

-- The Peano naturals data Nat : Set where

z : Nat
s : Nat -> Nat

-- An AVL tree's type is indexed by a natural. -- Avl N is the type of AVL trees of depth N. There arj 3 different -- node constructors: -- Left: The left subtree is one level deeper than the right -- Balanced: The subtrees have the same depth -- Right: The right Subtree is one level deeper than the left -- Since the AVL invariant is that the depths of a node's subtrees -- always differ by at most 1, this perfectly encodes the AVL depth invariant. data Avl : Nat -> Set where

 Empty : Avl z
 Left : {X : Nat} -> Nat -> Avl (s X) -> Avl X -> Avl (s (s X))
 Balanced : {X : Nat} -> Nat -> Avl X -> Avl X -> Avl (s X)
 Right : {X : Nat} -> Nat -> Avl X -> Avl (s X) -> Avl (s (s X))

-- A wrapper type that hides the AVL tree invariant. This is the interface -- exposed to the user. data Tree : Set where

 avl : {N : Nat} -> Avl N -> Tree

-- Comparison result data Ord : Set where

 Less : Ord
 Equal : Ord
 Greater : Ord

-- Comparison function cmp : Nat -> Nat -> Ord cmp z (s X) = Less cmp z z = Equal cmp (s X) z = Greater cmp (s X) (s Y) = cmp X Y

-- Insertions can either leave the depth the same or -- increase it by one. Encode this in the type. data InsertResult : Nat -> Set where

 Same : {X : Nat} -> Avl X -> InsertResult X
 Bigger : {X : Nat} -> Avl (s X) -> InsertResult X

-- If the left subtree is 2 levels deeper than the right, rotate to the right. -- balance-left X L R means X is the root, L is the left subtree and R is the right. balance-left : {N : Nat} -> Nat -> Avl (s (s N)) -> Avl N -> InsertResult (s (s N)) balance-left X (Right Y A (Balanced Z B C)) D = Same (Balanced Z (Balanced X A B) (Balanced Y C D)) balance-left X (Right Y A (Left Z B C)) D = Same (Balanced Z (Balanced X A B) (Right Y C D)) balance-left X (Right Y A (Right Z B C)) D = Same (Balanced Z (Left X A B) (Balanced Y C D)) balance-left X (Left Y (Balanced Z A B) C) D = Same (Balanced Z (Balanced X A B) (Balanced Y C D)) balance-left X (Left Y (Left Z A B) C) D = Same (Balanced Z (Left X A B) (Balanced Y C D)) balance-left X (Left Y (Right Z A B) C) D = Same (Balanced Z (Right X A B) (Balanced Y C D)) balance-left X (Balanced Y (Balanced Z A B) C) D = Bigger (Right Z (Balanced X A B) (Left Y C D)) balance-left X (Balanced Y (Left Z A B) C) D = Bigger (Right Z (Left X A B) (Left Y C D)) balance-left X (Balanced Y (Right Z A B) C) D = Bigger (Right Z (Right X A B) (Left Y C D))

-- Symmetric with balance-left balance-right : {N : Nat} -> Nat -> Avl N -> Avl (s (s N)) -> InsertResult (s (s N)) balance-right X A (Left Y (Left Z B C) D) = Same (Balanced Z (Balanced X A B) (Right Y C D)) balance-right X A (Left Y (Balanced Z B C) D) = Same(Balanced Z (Balanced X A B) (Balanced Y C D)) balance-right X A (Left Y (Right Z B C) D) = Same(Balanced Z (Left X A B) (Balanced Y C D)) balance-right X A (Balanced Z B (Left Y C D)) = Bigger(Left Z (Right X A B) (Left Y C D)) balance-right X A (Balanced Z B (Balanced Y C D)) = Bigger (Left Z (Right X A B) (Balanced Y C D)) balance-right X A (Balanced Z B (Right Y C D)) = Bigger (Left Z (Right X A B) (Right Y C D)) balance-right X A (Right Z B (Left Y C D)) = Same (Balanced Z (Balanced X A B) (Left Y C D)) balance-right X A (Right Z B (Balanced Y C D)) = Same (Balanced Z (Balanced X A B) (Balanced Y C D)) balance-right X A (Right Z B (Right Y C D)) = Same (Balanced Z (Balanced X A B) (Right Y C D))

-- insert' T N does all the work of inserting the element N into the tree T. insert' : {N : Nat} -> Avl N -> Nat -> InsertResult N insert' Empty N = Bigger (Balanced N Empty Empty) insert' (Left Y L R) X with cmp X Y insert' (Left Y L R) X | Less with insert' L X insert' (Left Y L R) X | Less | Same L' = Same (Left Y L' R) insert' (Left Y L R) X | Less | Bigger L' = balance-left Y L' R insert' (Left Y L R) X | Equal = Same (Left Y L R) insert' (Left Y L R) X | Greater with insert' R X insert' (Left Y L R) X | Greater | Same R' = Same (Left Y L R') insert' (Left Y L R) X | Greater | Bigger R' = Same (Balanced Y L R') insert' (Balanced Y L R) X with cmp X Y insert' (Balanced Y L R) X | Less with insert' L X insert' (Balanced Y L R) X | Less | Same L' = Same (Balanced Y L' R) insert' (Balanced Y L R) X | Less | Bigger L' = Bigger (Left Y L' R) insert' (Balanced Y L R) X | Equal = Same (Balanced Y L R) insert' (Balanced Y L R) X | Greater with insert' R X insert' (Balanced Y L R) X | Greater | Same R' = Same (Balanced Y L R') insert' (Balanced Y L R) X | Greater | Bigger R' = Bigger (Right Y L R') insert' (Right Y L R) X with cmp X Y insert' (Right Y L R) X | Less with insert' L X insert' (Right Y L R) X | Less | Same L' = Same (Right Y L' R) insert' (Right Y L R) X | Less | Bigger L' = Same (Balanced Y L' R) insert' (Right Y L R) X | Equal = Same (Right Y L R) insert' (Right Y L R) X | Greater with insert' R X insert' (Right Y L R) X | Greater | Same R' = Same (Right Y L R') insert' (Right Y L R) X | Greater | Bigger R' = balance-right Y L R'

-- Wrapper around insert' to use the depth-agnostic type Tree. insert : Tree -> Nat -> Tree insert (avl T) X with insert' T X ... | Same T' = avl T' ... | Bigger T' = avl T' </lang>

ARM Assembly

Works with: as version Raspberry Pi

<lang ARM Assembly> /* ARM assembly Raspberry PI */ /* program avltree2.s */

/* REMARK 1 : this program use routines in a include file

  see task Include a file language arm assembly 
  for the routine affichageMess conversion10 
  see at end of this program the instruction include */

/*******************************************/ /* Constantes */ /*******************************************/ .equ STDOUT, 1 @ Linux output console .equ EXIT, 1 @ Linux syscall .equ WRITE, 4 @ Linux syscall .equ BRK, 0x2d @ Linux syscall .equ CHARPOS, '@'

.equ NBVAL, 12

/*******************************************/ /* Structures */ /********************************************/ /* structure tree */

   .struct  0

tree_root: @ root pointer (or node right)

   .struct  tree_root + 4 

tree_size: @ number of element of tree

   .struct  tree_size + 4 

tree_suite:

   .struct  tree_suite + 12           @ for alignement to node

tree_fin: /* structure node tree */

   .struct  0

node_right: @ right pointer

   .struct  node_right + 4 

node_left: @ left pointer

   .struct  node_left + 4 

node_value: @ element value

   .struct  node_value + 4 

node_height: @ element value

   .struct  node_height + 4 

node_parent: @ element value

   .struct  node_parent + 4 

node_fin: /* structure queue*/

   .struct  0

queue_begin: @ next pointer

   .struct  queue_begin + 4 

queue_end: @ element value

   .struct  queue_end + 4 

queue_fin: /* structure node queue */

   .struct  0

queue_node_next: @ next pointer

   .struct  queue_node_next + 4 

queue_node_value: @ element value

   .struct  queue_node_value + 4 

queue_node_fin: /*******************************************/ /* Initialized data */ /*******************************************/ .data szMessPreOrder: .asciz "PreOrder :\n" szCarriageReturn: .asciz "\n" /* datas error display */ szMessErreur: .asciz "Error detected.\n" szMessKeyDbl: .asciz "Key exists in tree.\n" szMessInsInv: .asciz "Insertion in inverse order.\n" /* datas message display */ szMessResult: .asciz "Ele: @ G: @ D: @ val @ h @ pere @\n" sValue: .space 12,' '

                     .asciz "\n"

/*******************************************/ /* UnInitialized data */ /*******************************************/ .bss sZoneConv: .skip 24 stTree: .skip tree_fin @ place to structure tree stTree1: .skip tree_fin @ place to structure tree stQueue: .skip queue_fin @ place to structure queue /*******************************************/ /* code section */ /*******************************************/ .text .global main main:

   mov r8,#1                           @ node tree value

1: @ loop insertion in order

   ldr r0,iAdrstTree                   @ structure tree address
   mov r1,r8
   bl insertElement                    @ add element value r1
   cmp r0,#-1
   beq 99f
   //ldr r3,iAdrstTree                 @ tree root address (begin structure)
   //ldr r0,[r3,#tree_root]
   //ldr r1,iAdrdisplayElement           @ function to execute
   //bl preOrder
   add r8,#1                           @ increment value
   cmp r8,#NBVAL                       @ end ?
   ble 1b                              @ no -> loop

   ldr r0,iAdrstTree                   @ structure tree address
   mov r1,#11                          @ verif key dobble
   bl insertElement                    @ add element value r1
   cmp r0,#-1
   bne 2f
   ldr r0,iAdrszMessErreur
   bl affichageMess

2:

   ldr r0,iAdrszMessPreOrder           @ load verification
   bl affichageMess
   ldr r3,iAdrstTree                   @ tree root address (begin structure)
   ldr r0,[r3,#tree_root]
   ldr r1,iAdrdisplayElement           @ function to execute
   bl preOrder
   

   ldr r0,iAdrszMessInsInv
   bl affichageMess
   mov r8,#NBVAL                       @ node tree value

3: @ loop insertion inverse order

   ldr r0,iAdrstTree1                  @ structure tree address
   mov r1,r8
   bl insertElement                    @ add element value r1
   cmp r0,#-1
   beq 99f
   sub r8,#1                           @ increment value
   cmp r8,#0                           @ end ?
   bgt 3b                              @ no -> loop

   ldr r0,iAdrszMessPreOrder           @ load verification
   bl affichageMess
   ldr r3,iAdrstTree1                  @ tree root address (begin structure)
   ldr r0,[r3,#tree_root]
   ldr r1,iAdrdisplayElement           @ function to execute
   bl preOrder

                                       @ search value
   ldr r0,iAdrstTree1                  @ tree root address (begin structure)
   mov r1,#11                          @ value to search
   bl searchTree
   cmp r0,#-1
   beq 100f
   mov r2,r0
   ldr r0,iAdrszMessKeyDbl             @ key exists
   bl affichageMess
                                       @ suppresssion previous value
   mov r0,r2
   ldr r1,iAdrstTree1
   bl supprimer

   ldr r0,iAdrszMessPreOrder           @ verification
   bl affichageMess
   ldr r3,iAdrstTree1                  @ tree root address (begin structure)
   ldr r0,[r3,#tree_root]
   ldr r1,iAdrdisplayElement           @ function to execute
   bl preOrder

   b 100f

99: @ display error

   ldr r0,iAdrszMessErreur
   bl affichageMess

100: @ standard end of the program

   mov r7, #EXIT                       @ request to exit program
   svc 0                               @ perform system call

iAdrszMessPreOrder: .int szMessPreOrder iAdrszMessErreur: .int szMessErreur iAdrszCarriageReturn: .int szCarriageReturn iAdrstTree: .int stTree iAdrstTree1: .int stTree1 iAdrstQueue: .int stQueue iAdrdisplayElement: .int displayElement iAdrszMessInsInv: .int szMessInsInv /******************************************************************/ /* insert element in the tree */ /******************************************************************/ /* r0 contains the address of the tree structure */ /* r1 contains the value of element */ /* r0 returns address of element or - 1 if error */ insertElement: @ INFO: insertElement

   push {r1-r8,lr}                   @ save  registers 
   mov r7,r0                         @ save head
   mov r0,#node_fin                  @ reservation place one element
   bl allocHeap
   cmp r0,#-1                        @ allocation error
   beq 100f
   mov r5,r0
   str r1,[r5,#node_value]           @ store value in address heap
   mov r3,#0
   str r3,[r5,#node_left]            @ init left pointer with zero
   str r3,[r5,#node_right]           @ init right pointer with zero
   str r3,[r5,#node_height]          @ init balance with zero
   ldr r2,[r7,#tree_size]            @ load tree size
   cmp r2,#0                         @ 0 element ?
   bne 1f
   str r5,[r7,#tree_root]            @ yes -> store in root
   b 4f

1: @ else search free address in tree

   ldr r3,[r7,#tree_root]            @ start with address root

2: @ begin loop to insertion

   ldr r4,[r3,#node_value]           @ load key 
   cmp r1,r4
   beq 6f                            @ key equal
   blt 3f                            @ key <
                                     @ key >  insertion right
   ldr r8,[r3,#node_right]           @ node empty ?
   cmp r8,#0
   movne r3,r8                       @ no -> next node
   bne 2b                            @ and loop
   str r5,[r3,#node_right]           @ store node address in right pointer
   b 4f

3: @ left

   ldr r8,[r3,#node_left]            @ left pointer empty ?
   cmp r8,#0
   movne r3,r8                       @
   bne 2b                            @ no -> loop
   str r5,[r3,#node_left]            @ store node address in left pointer

4:

   str r3,[r5,#node_parent]          @ store parent
   mov r4,#1
   str r4,[r5,#node_height]          @ store height = 1
   mov r0,r5                         @ begin node to requilbrate
   mov r1,r7                         @ head address
   bl equilibrer

5:

   add r2,#1                        @ increment tree size
   str r2,[r7,#tree_size]
   mov r0,#0
   b 100f

6: @ key equal ?

   ldr r0,iAdrszMessKeyDbl
   bl affichageMess
   mov r0,#-1
   b 100f

100:

   pop {r1-r8,lr}                    @ restaur registers
   bx lr                             @ return

iAdrszMessKeyDbl: .int szMessKeyDbl /******************************************************************/ /* equilibrer after insertion */ /******************************************************************/ /* r0 contains the address of the node */ /* r1 contains the address of head */ equilibrer: @ INFO: equilibrer

   push {r1-r8,lr}               @ save  registers 
   mov r3,#0                     @ balance factor

1: @ begin loop

   ldr r5,[r0,#node_parent]      @ load father
   cmp r5,#0                     @ end ?
   beq 5f
   cmp r3,#2                     @ right tree too long
   beq 5f
   cmp r3,#-2                    @ left tree too long
   beq 5f
   mov r6,r0                     @ s = current
   ldr r0,[r6,#node_parent]      @ current = father
   ldr r7,[r0,#node_left]
   cmp r7,#0
   ldrne r8,[r7,#node_height]     @ height left tree 
   moveq r8,#0
   ldr r7,[r0,#node_right]
   cmp r7,#0
   ldrne r9,[r7,#node_height]     @ height right tree 
   moveq r9,#0
   cmp r8,r9
   addgt r8,#1
   strgt r8,[r0,#node_height]
   addle r9,#1
   strle r9,[r0,#node_height]
   //
   ldr r7,[r0,#node_right]
   cmp r7,#0
   ldrne r8,[r7,#node_height]
   moveq r8,#0
   ldr r7,[r0,#node_left]
   cmp r7,#0
   ldrne r9,[r7,#node_height]
   moveq r9,#0
   sub r3,r8,r9                    @ compute balance factor
   b 1b

5:

   cmp r3,#2
   beq 6f
   cmp r3,#-2
   beq 6f
   b 100f

6:

   mov r3,r1
   mov r4,r0
   mov r1,r6
   bl equiUnSommet
                                     @ change head address ?
   ldr r2,[r3,#tree_root]
   cmp r2,r4
   streq r6,[r3,#tree_root]

100:

   pop {r1-r8,lr}                    @ restaur registers
   bx lr                             @ return

/******************************************************************/ /* equilibre 1 sommet */ /******************************************************************/ /* r0 contains the address of the node */ /* r1 contains the address of the node */ equiUnSommet: @ INFO: equiUnSommet

   push {r1-r9,lr}                       @ save  registers 
   mov r5,r0                             @ save p
   mov r6,r1    // s
   ldr r2,[r5,#node_left]
   cmp r2,r6
   bne 5f
   ldr r7,[r5,#node_right]
   cmp r7,#0
   moveq r8,#0
   ldrne r8,[r7,#node_height]
   ldr r7,[r5,#node_left]
   cmp r7,#0
   moveq r9,#0
   ldrne r9,[r7,#node_height]
   sub r3,r8,r9
   cmp r3,#-2
   bne 100f
   ldr r7,[r6,#node_right]
   cmp r7,#0
   moveq r8,#0
   ldrne r8,[r7,#node_height]
   ldr r7,[r6,#node_left]
   cmp r7,#0
   moveq r9,#0
   ldrne r9,[r7,#node_height]
   sub r3,r8,r9
   cmp r3,#1
   bge 2f
   mov r0,r5
   bl rotRight
   b 100f

2:

   mov r0,r6
   bl rotLeft
   mov r0,r5
   bl rotRight
   b 100f

5:

   ldr r7,[r5,#node_right]
   cmp r7,#0
   moveq r8,#0
   ldrne r8,[r7,#node_height]
   ldr r7,[r5,#node_left]
   cmp r7,#0
   moveq r9,#0
   ldrne r9,[r7,#node_height]
   sub r3,r8,r9
   cmp r3,#2
   bne 100f
   ldr r7,[r6,#node_right]
   cmp r7,#0
   moveq r8,#0
   ldrne r8,[r7,#node_height]
   ldr r7,[r6,#node_left]
   cmp r7,#0
   moveq r9,#0
   ldrne r9,[r7,#node_height]
   sub r3,r8,r9
   cmp r3,#-1
   ble 2f
   mov r0,r5
   bl rotLeft
   b 100f

2:

   mov r0,r6
   bl rotRight
   mov r0,r5
   bl rotLeft
   b 100f

100:

   pop {r1-r9,lr}                    @ restaur registers
   bx lr                             @ return

/******************************************************************/ /* right rotation */ /******************************************************************/ /* r0 contains the address of the node */ rotRight: @ INFO: rotRight

   push {r1-r5,lr}                 @ save  registers 
   //   r2                  r2
   //      r0                   r1
   //   r1                         r0
   //      r3                    r3
   ldr r1,[r0,#node_left]          @ load left children
   ldr r2,[r0,#node_parent]        @ load father
   cmp r2,#0                       @ no father ???
   beq 2f
   ldr r3,[r2,#node_left]          @ load left node father
   cmp r3,r0                       @ equal current node ?
   streq r1,[r2,#node_left]        @ yes store left children
   strne r1,[r2,#node_right]       @ no store right

2:

   str r2,[r1,#node_parent]        @ change parent
   str r1,[r0,#node_parent]
   ldr r3,[r1,#node_right]
   str r3,[r0,#node_left]
   cmp r3,#0
   strne r0,[r3,#node_parent]      @ change parent node left
   str r0,[r1,#node_right]

   ldr r3,[r0,#node_left]          @ compute newbalance factor 
   cmp r3,#0
   moveq r4,#0
   ldrne r4,[r3,#node_height]
   ldr r3,[r0,#node_right]
   cmp r3,#0
   moveq r5,#0
   ldrne r5,[r3,#node_height]
   cmp r4,r5
   addgt r4,#1
   strgt r4,[r0,#node_height]
   addle r5,#1
   strle r5,[r0,#node_height]

//

   ldr r3,[r1,#node_left]         @ compute new balance factor
   cmp r3,#0
   moveq r4,#0
   ldrne r4,[r3,#node_height]
   ldr r3,[r1,#node_right]
   cmp r3,#0
   moveq r5,#0
   ldrne r5,[r3,#node_height]
   cmp r4,r5
   addgt r4,#1
   strgt r4,[r1,#node_height]
   addle r5,#1
   strle r5,[r1,#node_height]

100:

   pop {r1-r5,lr}                   @ restaur registers
   bx lr

/******************************************************************/ /* left rotation */ /******************************************************************/ /* r0 contains the address of the node sommet */ rotLeft: @ INFO: rotLeft

   push {r1-r5,lr}                  @ save  registers 
   //   r2                  r2
   //      r0                   r1
   //          r1            r0
   //        r3                 r3
   ldr r1,[r0,#node_right]          @ load right children
   ldr r2,[r0,#node_parent]         @ load father (racine)
   cmp r2,#0                        @ no father ???
   beq 2f
   ldr r3,[r2,#node_left]           @ load left node father
   cmp r3,r0                        @ equal current node ?
   streq r1,[r2,#node_left]         @ yes store left children
   strne r1,[r2,#node_right]        @ no store to right

2:

   str r2,[r1,#node_parent]         @ change parent of right children
   str r1,[r0,#node_parent]         @ change parent of sommet
   ldr r3,[r1,#node_left]           @ left children 
   str r3,[r0,#node_right]          @ left children pivot exists ? 
   cmp r3,#0
   strne r0,[r3,#node_parent]       @ yes store in 
   str r0,[r1,#node_left]

//

   ldr r3,[r0,#node_left]           @ compute new height for old summit
   cmp r3,#0
   moveq r4,#0
   ldrne r4,[r3,#node_height]       @ left height
   ldr r3,[r0,#node_right]
   cmp r3,#0
   moveq r5,#0
   ldrne r5,[r3,#node_height]       @ right height
   cmp r4,r5
   addgt r4,#1
   strgt r4,[r0,#node_height]       @ if right > left
   addle r5,#1
   strle r5,[r0,#node_height]       @ if left > right

//

   ldr r3,[r1,#node_left]           @ compute new height for new
   cmp r3,#0
   moveq r4,#0
   ldrne r4,[r3,#node_height]
   ldr r3,[r1,#node_right]
   cmp r3,#0
   moveq r5,#0
   ldrne r5,[r3,#node_height]
   cmp r4,r5
   addgt r4,#1
   strgt r4,[r1,#node_height]
   addle r5,#1
   strle r5,[r1,#node_height]

100:

   pop {r1-r5,lr}                        @ restaur registers
   bx lr

/******************************************************************/ /* search value in tree */ /******************************************************************/ /* r0 contains the address of structure of tree */ /* r1 contains the value to search */ searchTree: @ INFO: searchTree

   push {r1-r4,lr}                   @ save  registers 
   ldr r2,[r0,#tree_root]

1: @ begin loop

   ldr r4,[r2,#node_value]           @ load key 
   cmp r1,r4
   beq 3f                            @ key equal
   blt 2f                            @ key <
                                     @ key >  insertion right
   ldr r3,[r2,#node_right]           @ node empty ?
   cmp r3,#0
   movne r2,r3                       @ no -> next node
   bne 1b                            @ and loop
   mov r0,#-1                        @ not find
   b 100f

2: @ left

   ldr r3,[r2,#node_left]            @ left pointer empty ?
   cmp r3,#0
   movne r2,r3                       @
   bne 1b                            @ no -> loop
   mov r0,#-1                        @ not find
   b 100f

3:

   mov r0,r2                         @ return node address

100:

   pop {r1-r4,lr}                    @ restaur registers
   bx lr

/******************************************************************/ /* suppression node */ /******************************************************************/ /* r0 contains the address of the node */ /* r1 contains structure tree address */ supprimer: @ INFO: supprimer

   push {r1-r8,lr}              @ save  registers 
   ldr r1,[r0,#node_left]
   cmp r1,#0
   bne 5f
   ldr r1,[r0,#node_right]
   cmp r1,#0
   bne 5f
                                @ is a leaf
   mov r4,#0
   ldr r3,[r0,#node_parent]     @ father
   cmp r3,#0
   streq r4,[r1,#tree_root]
   beq 100f
   ldr r1,[r3,#node_left]
   cmp r1,r0
   bne 2f
   str r4,[r3,#node_left]       @ suppression left children
   ldr r5,[r3,#node_right]
   cmp r5,#0
   moveq r6,#0
   ldrne r6,[r5,#node_height]
   add r6,#1
   str r6,[r3,#node_height]
   b 3f

2: @ suppression right children

   str r4,[r3,#node_right]
   ldr r5,[r3,#node_left]
   cmp r5,#0
   moveq r6,#0
   ldrne r6,[r5,#node_height]
   add r6,#1
   str r6,[r3,#node_height]

3: @ new balance

   mov r0,r3
   bl equilibrerSupp
   b 100f

5: @ is not à leaf

   ldr r7,[r0,#node_right]
   cmp r7,#0
   beq 7f
   mov r8,r0
   mov r0,r7

6:

   ldr r6,[r0,#node_left]
   cmp r6,#0
   movne r0,r6
   bne 6b
   b 9f

7:

   ldr r7,[r0,#node_left]         @ search the litle element
   cmp r7,#0
   beq 9f
   mov r8,r0
   mov r0,r7

8:

   ldr r6,[r0,#node_right]        @ search the great element
   cmp r6,#0
   movne r0,r6
   bne 8b

9:

   ldr r5,[r0,#node_value]         @ copy value
   str r5,[r8,#node_value]
   bl supprimer                    @ suppression node r0

100:

   pop {r1-r8,lr}                  @ restaur registers
   bx lr

/******************************************************************/ /* equilibrer after suppression */ /******************************************************************/ /* r0 contains the address of the node */ /* r1 contains the address of head */ equilibrerSupp: @ INFO: equilibrerSupp

   push {r1-r8,lr}               @ save  registers 
   mov r3,#1                     @ balance factor
   ldr r2,[r1,#tree_root]

1:

   ldr r5,[r0,#node_parent]      @ load father
   cmp r5,#0                     @ no father 
   beq 100f
   cmp r3,#0                     @ balance equilibred
   beq 100f
   mov r6,r0                     @ save entry node
   ldr r0,[r6,#node_parent]      @ current = father
   ldr r7,[r0,#node_left]
   cmp r7,#0
   ldrne r8,[r7,#node_height]    @ height left tree 
   moveq r8,#0
   ldr r7,[r0,#node_right]
   cmp r7,#0
   ldrne r9,[r7,#node_height]    @ height right tree 
   moveq r9,#0
   cmp r8,r9
   addgt r8,#1
   strgt r8,[r0,#node_height]
   addle r9,#1
   strle r9,[r0,#node_height]
   //
   ldr r7,[r0,#node_right]
   cmp r7,#0
   ldrne r8,[r7,#node_height]
   moveq r8,#0
   ldr r7,[r0,#node_left]
   cmp r7,#0
   ldrne r9,[r7,#node_height]
   moveq r9,#0
   sub r3,r8,r9                   @ compute balance factor
   mov r2,r1
   mov r4,r0                      @ save current
   mov r1,r6
   bl equiUnSommet
                                  @ change head address ?
   cmp r2,r4
   streq r6,[r3,#tree_root]
   mov r0,r4                      @ restaur current
   b 1b

100:

   pop {r1-r8,lr}                  @ restaur registers
   bx lr                           @ return

/******************************************************************/ /* preOrder */ /******************************************************************/ /* r0 contains the address of the node */ /* r1 function address */ preOrder: @ INFO: preOrder

   push {r1-r2,lr}                       @ save  registers 
   cmp r0,#0
   beq 100f
   mov r2,r0
   blx r1                                @ call function

   ldr r0,[r2,#node_left]
   bl preOrder
   ldr r0,[r2,#node_right]
   bl preOrder

100:

   pop {r1-r2,lr}                        @ restaur registers
   bx lr       

/******************************************************************/ /* display node */ /******************************************************************/ /* r0 contains node address */ displayElement: @ INFO: displayElement

   push {r1,r2,r3,lr}                 @ save  registers 
   mov r2,r0
   ldr r1,iAdrsZoneConv
   bl conversion16
   mov r4,#0
   strb r4,[r1,r0]
   ldr r0,iAdrszMessResult
   ldr r1,iAdrsZoneConv
   bl strInsertAtCharInc
   mov r3,r0
   ldr r0,[r2,#node_left]
   ldr r1,iAdrsZoneConv
   bl conversion16
   mov r4,#0
   strb r4,[r1,r0]
   mov r0,r3
   ldr r1,iAdrsZoneConv
   bl strInsertAtCharInc
   mov r3,r0
   ldr r0,[r2,#node_right]
   ldr r1,iAdrsZoneConv
   bl conversion16
   mov r4,#0
   strb r4,[r1,r0]
   mov r0,r3
   ldr r1,iAdrsZoneConv
   bl strInsertAtCharInc
   mov r3,r0
   ldr r0,[r2,#node_value]
   ldr r1,iAdrsZoneConv
   bl conversion10
   mov r4,#0
   strb r4,[r1,r0]
   mov r0,r3
   ldr r1,iAdrsZoneConv
   bl strInsertAtCharInc
   mov r3,r0
   ldr r0,[r2,#node_height]
   ldr r1,iAdrsZoneConv
   bl conversion10
   mov r4,#0
   strb r4,[r1,r0]
   mov r0,r3
   ldr r1,iAdrsZoneConv
   bl strInsertAtCharInc
   mov r3,r0
   ldr r0,[r2,#node_parent]
   ldr r1,iAdrsZoneConv
   bl conversion16
   mov r4,#0
   strb r4,[r1,r0]
   mov r0,r3
   ldr r1,iAdrsZoneConv
   bl strInsertAtCharInc
   bl affichageMess

100:

   pop {r1,r2,r3,lr}                        @ restaur registers
   bx lr                              @ return

iAdrszMessResult: .int szMessResult iAdrsZoneConv: .int sZoneConv iAdrsValue: .int sValue

/******************************************************************/ /* memory allocation on the heap */ /******************************************************************/ /* r0 contains the size to allocate */ /* r0 returns address of memory heap or - 1 if error */ /* CAUTION : The size of the allowance must be a multiple of 4 */ allocHeap:

   push {r5-r7,lr}                   @ save  registers 
   @ allocation
   mov r6,r0                         @ save size
   mov r0,#0                         @ read address start heap
   mov r7,#0x2D                      @ call system 'brk'
   svc #0
   mov r5,r0                         @ save address heap for return
   add r0,r6                         @ reservation place for size
   mov r7,#0x2D                      @ call system 'brk'
   svc #0
   cmp r0,#-1                        @ allocation error
   movne r0,r5                       @ return address memory heap
   pop {r5-r7,lr}                    @ restaur registers
   bx lr                             @ return

/***************************************************/ /* ROUTINES INCLUDE */ /***************************************************/ .include "../affichage.inc" </lang>

Output:

Key exists in tree.
Error detected.
PreOrder :
Ele: 007EC08C G: 007EC03C D: 007EC0B4 val 8 h 4 pere 00000000
Ele: 007EC03C G: 007EC014 D: 007EC064 val 4 h 3 pere 007EC08C
Ele: 007EC014 G: 007EC000 D: 007EC028 val 2 h 2 pere 007EC03C
Ele: 007EC000 G: 00000000 D: 00000000 val 1 h 1 pere 007EC014
Ele: 007EC028 G: 00000000 D: 00000000 val 3 h 1 pere 007EC014
Ele: 007EC064 G: 007EC050 D: 007EC078 val 6 h 2 pere 007EC03C
Ele: 007EC050 G: 00000000 D: 00000000 val 5 h 1 pere 007EC064
Ele: 007EC078 G: 00000000 D: 00000000 val 7 h 1 pere 007EC064
Ele: 007EC0B4 G: 007EC0A0 D: 007EC0C8 val 10 h 3 pere 007EC08C
Ele: 007EC0A0 G: 00000000 D: 00000000 val 9 h 1 pere 007EC0B4
Ele: 007EC0C8 G: 00000000 D: 007EC0DC val 11 h 2 pere 007EC0B4
Ele: 007EC0DC G: 00000000 D: 00000000 val 12 h 1 pere 007EC0C8
Insertion in inverse order.
PreOrder :
Ele: 007ED0F9 G: 007ED121 D: 007ED0A9 val 5 h 4 pere 00000000
Ele: 007ED121 G: 007ED135 D: 007ED10D val 3 h 3 pere 007ED0F9
Ele: 007ED135 G: 007ED149 D: 00000000 val 2 h 2 pere 007ED121
Ele: 007ED149 G: 00000000 D: 00000000 val 1 h 1 pere 007ED135
Ele: 007ED10D G: 00000000 D: 00000000 val 4 h 1 pere 007ED121
Ele: 007ED0A9 G: 007ED0D1 D: 007ED081 val 9 h 3 pere 007ED0F9
Ele: 007ED0D1 G: 007ED0E5 D: 007ED0BD val 7 h 2 pere 007ED0A9
Ele: 007ED0E5 G: 00000000 D: 00000000 val 6 h 1 pere 007ED0D1
Ele: 007ED0BD G: 00000000 D: 00000000 val 8 h 1 pere 007ED0D1
Ele: 007ED081 G: 007ED095 D: 007ED06D val 11 h 2 pere 007ED0A9
Ele: 007ED095 G: 00000000 D: 00000000 val 10 h 1 pere 007ED081
Ele: 007ED06D G: 00000000 D: 00000000 val 12 h 1 pere 007ED081
Key exists in tree.
PreOrder :
Ele: 007ED0F9 G: 007ED121 D: 007ED0A9 val 5 h 4 pere 00000000
Ele: 007ED121 G: 007ED135 D: 007ED10D val 3 h 3 pere 007ED0F9
Ele: 007ED135 G: 007ED149 D: 00000000 val 2 h 2 pere 007ED121
Ele: 007ED149 G: 00000000 D: 00000000 val 1 h 1 pere 007ED135
Ele: 007ED10D G: 00000000 D: 00000000 val 4 h 1 pere 007ED121
Ele: 007ED0A9 G: 007ED0D1 D: 007ED081 val 9 h 3 pere 007ED0F9
Ele: 007ED0D1 G: 007ED0E5 D: 007ED0BD val 7 h 2 pere 007ED0A9
Ele: 007ED0E5 G: 00000000 D: 00000000 val 6 h 1 pere 007ED0D1
Ele: 007ED0BD G: 00000000 D: 00000000 val 8 h 1 pere 007ED0D1
Ele: 007ED081 G: 007ED095 D: 00000000 val 12 h 2 pere 007ED0A9
Ele: 007ED095 G: 00000000 D: 00000000 val 10 h 1 pere 007ED081

beed

<lang cpp> eenioonneraashon staat {

   heder,
   balansd,
   lepht_hi,
   riit_hi

}

eenioonneraashon direcshon {

 phronn_lepht,
 phronn_riit

}

eenioonneraashon booleean {

troo,
phals

}

clahs nohd<t> {

   nohd<t> lepht;
   nohd<t> riit;
   nohd<t> pairent;
   staat balans;
   t daata;

   nohd()
   {
      lepht = this;
      riit = this;
      balans = heder;
   }

   nohd(nohd<t> p, t daata_in)
   {
     pairent = p;
     balans = balansd;
     daata = daata_in; 
   }

   is_heder(booleean anser)
   {
       balans.eecuuols(heder,anser); 
   }

   eecuuols(nohd<t> other, booleean anser)
   {
       _nohd.nohd.eecuuols(other.nohd._nohd, anser);
   }

   nnoou_necst()
   {
       booleean is_heder = phals;
       nohd.is_heder(is_heder);
       iph (is_heder)
       {
           nohd = nohd.lepht;
           reeturn;
       }

       booleean riit_is_null = phals;
       nohd.riit.is_nul(riit_is_null);
       iph (!riit_is_null)
       {
          nohd = nohd.riit;

          booleean lepht_is_nul = phals;
          nohd.lepht.is_nul(lepht_is_nul);
          uuhiil (!lepht_is_null)
          {
              nohd = nohd.lepht;
              nohd.lepht.is_nul(lepht_is_nul);
          }
       }
       els
       {
           nohd<t> uui = nohd.pairent;
           booleean uui_is_heder = phals;
           uui.is_heder(uui_is_heder);
           iph (uui_is_heder)
           {
               nohd = uui;
               reeturn;
           }
           booleean nohd_is_uui_riit = phals;
           nohd.eecuuols(uui.riit,nohd_is_uui_riit);
           uuhiil (nohd_is_uui_riit)
           {
               nohd = uui;
               uui = uui.pairent;
               nohd.eecuuols(uui.riit,nohd_is_uui_riit);
           }
           nohd = uui;
       }

   }

   rohtaat_lepht(nohd<t> root)
   {
       nohd<t> pairent = root.pairent;
       nohd<t> e = root.riit;
       root.pairent = e;
       e.pairent = pairent;
       booleean e_lepht_is_nul = phals;
       nohd<t> e_lepht = e.lepht;
       e_lepht.is_nul(e_lepht_is_nul);
       iph (!e_lepht_is_nul) {e.lepht.pairent = root;}
       root.riit = e.lepht;
       e.lepht = root;
       root = e;
   }

   rohtaat_riit(nohd<t> root)
   {
       nohd<t> pairent = root.pairent;
       nohd<t> e = root.lepht;
       root.pairent = e;
       e.pairent = pairent;
       booleean e_riit_is_nul = phals;
       nohd<t> e_riit =  e.riit;
       e_riit.is_nul(e_lepht_is_nul);
       iph (!e_lepht_is_nul) {e.riit.pairent = root;}
       root.lepht = e.riit;
       e.riit = root;
       root = e;
   }

   balans_lepht(nohd<t> root)
   {
       nohd<t> lepht = root.lepht;
       select (lepht.balans)
       {
           caas lepht_hi
           {
               root.balans = balansd;
               lepht.balans = balansd;
               rohtaat_riit(root);
           }

           caas riit_hi
           {
               nohd<t> subriit = lepht.riit;

               select(subriit.balans)
               {
                   caas balansd
                   {
                       root.balans = balansd;
                       lepht.balans = balansd;
                   }

                   caas riit_hi
                   {
                       root.balans = balansd;
                       lepht.balans = lepht_hi;
                   }

                   caas lepht_hi
                   {
                       root.balans = riit_hi;
                       lepht.balans = balansd;
                   }
               }
               subriit.balans = balansd;
               rohtaat_lepht(lepht);
               root.lepht = lepht;
               rohtaat_riit(root);
           }

           caas balansd
           {
               root.balans = lepht_hi;
               lepht.balans = riit_hi;
               rohtaat_riit(root);
           }
       }   
   }

   balans_riit(nohd<t> root)
   {
       nohd<t> riit = root.riit;
       select (riit.balans)
       {
           caas riit_hi
           { 
               root.balans = balansd;
               riit.balans = balansd;
               rohtaat_lepht(root);
           }

          caas lepht_hi
          {
              nohd<t> sublepht = riit.lepht;

              select(sublepht.balans)
              {
                  caas balansd
                  {
                      root.balans = balansd;
                      riit.balans = balansd;
                  }

                  caas lepht_hi
                  {
                      root.balans = balansd;
                      riit.balans = riit_hi;
                  }

                  caas riit_hi
                  {
                      root.balans = lepht_hi;
                      riit.balans = balansd;
                  }
              }
              sublepht.balans = balansd;
              rohtaat_riit(riit);
              root.riit = riit;
              rohtaat_lepht(root);
          }

          caas balansd
          {
              root.balans = riit_hi;
              riit.balans = lepht_hi;
              rohtaat_lepht(root);
          }
       }   
   }
   
   balans_tree(nohd<t> root, direcshon phronn)
   {
       booleean torler = troo;

       uuhiil (torler)
       {
           nohd<t> pairent = root.pairent;

           direcshon necst_phronn = phronn_lepht;

           booleean is_pairent_lepht = phals;
           pairent.lepht.eecuuols(root,is_pairent_lepht);
           iph (!is_pairent_lepht)
           {
               necst_phronn = phronn_riit;
           }

           booleean is_phronn_lepht = phals;
           phronn.eecuuols(phronn_lepht, is_phronn_lepht);
           iph (is_phronn_lepht)
           {
               select (root.balans)
               {
                   caas lepht_hi
                   {
                       booleean pheder = phals;
                       pairent.is_heder(pheder);
                       iph (pheder)
                       {
                           balans_lepht(pairent.pairent);
                       }
                       els
                       {
                           booleean lepht_is_root = phals;
                           pairent.lepht.eecuuols(root,lepht_is_root);
                           iph (lepht_is_root)
                           {
                               balans_lepht(pairent.lepht);
                           }
                           els
                           {
                               balans_lepht = pairent.riit;
                               torler = phals;
                           }
                       }
                   }

                   caas balansd
                   {
                       root.balans = lepht_hi;
                       torler = troo;
                   }
   
                   caas riit_hi
                   {
                       root.balans = balansd;
                       torler = phals;
                   }
               }
           }
           els
           {
              select (root.balans)
              {
                  caas lepht_hi
                  {
                      root.balans = balansd;
                      torler = phals;
                  }    

                  caas balansd
                  {
                      root.balans = riit_hi;
                      torler = troo;
                  }

                  caas riit_hi
                  {
                       booleean heder = phals;
                       pairent.is_heder(heder);
                       iph (heder)
                       {
                           balans_riit(pairent.pairent);
                       }
                       els
                       {
                           booleean lpairent = phals;
                           pairent.lepht.eecuuols(root,lpairent);
                           iph (lpairent)
                           {
                               balans_riit(pairent.lepht);
                           }
                           els
                           {
                               balans_riit(pairent.riit);
                               torler = phals;
                           }
                       }
                    }
                }
            }

            iph (torler)
            {
                booleean heder_up = phals;
                pairent.is_heder(heder_up);
                iph (heder_up)
                {
                  torler = phals;
                 }
                 els
                 {
                     root = pairent;
                     phronn = necst_phronn;
                 }
            }
        }
   }

   balans_tree_reennoou(nohd<t> root, direcshon phronn)
   {
        booleean shorter = troo;

        uuhiil (shorter)
        {
           nohd<t> pairent = root.pairent;

           direcshon necst_phronn = phronn_lepht;

           booleean is_pairent_lepht = phals;
           pairent.lepht.eecuuols(root,is_pairent_lepht);
           iph (!is_pairent_lepht)
           {
               necst_phronn = phronn_riit;
           }

           booleean is_phronn_lepht = phals;
           phronn.eecuuols(phronn_lepht, is_phronn_lepht);
           iph (is_phronn_lepht)
           {
               select (root.balans)
               {
                   caas lepht_hi
                   {
                       root.balans = staat.balansd;
                       shorter = troo;
                   }

                   caas balansd
                   {
                       root.balans = staat.riit_hi;
                       shorter = phals;
                   }

                   caas riit_hi
                   {
                       booleean riit_is_balansd = phals;
                       root.riit.balans.eecuuols(balansd,riit_is_balansd);

                       iph (riit_is_balansd)
                       {
                           shorter = phals;
                       }
                       els
                       {
                           shorter = troo;
                       }

                       booleean heder = phals;
                       pairent.is_heder(heder);
                       iph (heder)
                       {
                           balans_riit(pairent.pairent);
                       }
                       els
                       {
                           booleean lpairent = phals;
                           pairent.lepht.eecuuols(root,lpairent);
                           iph (lpairent)
                           {
                               balans_riit(pairent.lepht);
                           }
                           els
                           {
                               balans_riit(pairent.riit);
                           }
                      }    
                  }
               }
            }
            els
            {
               select (root.balans)
               {
                   caas riit_hi
                   {
                       root.balans = balansd;
                       shorter = troo;
                   }

                  caas balansd
                  {
                     root.balans = lepht_hi;
                     shorter = phals;
                  }

                  caas lepht_hi
                  {
                       booleean lepht_is_balansd = phals;
                       root.lepht.balans.eecuuols(balansd,lepht_is_balansd);
                       iph (lepht_is_balansd)
                       {
                           shorter = phals;
                       }
                       els
                       {
                           shorter = troo;
                       }

                       booleean is_heder = phals;
                       pairent.is_heder(is_heder);
                       iph (is_heder)
                       {
                           balans_lepht(pairent.pairent);
                       }
                       els
                       {
                           pairent.lepht.eecuuols(root,lpairent);
                           iph (lpairent)
                           {
                               balans_lepht(pairent.lepht);
                           }
                           els
                           {
                               balans_lepht(pairent.riit);
                           }
                      }
                  }
               }
           }

           iph (shorter)
           {
              booleean heder_up = phals;
              pairent.is_heder(heder_up);
              iph (heder_up)
              {
                 shorter = phals;
              }
              els
              {
                 root = pairent;
                 phronn = necst_phronn;
              }
          }
       }
   }

}

clahs entree_orlredee_ecsists_ecssepshon {

  string naann;

   entree_orlredee_ecsists_ecssepshon(string naann_in)
   {
        naann = naann_in;
   }

   print()
   {
        string ouut(naan);
        string to_ad( orlredee ecsists);
        ouut.concat(to_ad);
        ouut.print();
   }

}

}

clahs set_entree<t> {

   set_entree(nohd<t> n)
   {
       _nohd = n;
   }

   ualioo(t _daata)
   {
     _daata = _nohd.daata;
    }

   is_heder(booleean b) { _nohd.nohd.is_heder(b); }

   nohd<t> _nohd;

}

clahs set<t> {

   nohd<t> heder;

   set()
   {
      heder();
   }

   ad(t daata)
   {
      string out(in ad);
      out.println();

       booleean root_is_nul = phals;
       heder.pairent.is_nul(root_is_nul);
       iph (root_is_nul)
       {
           nohd<t> n(heder,daata);
           heder.pairent = n;
           heder.lepht = heder.pairent;
           heder.riit = heder.pairent;
       }
       els
       {
           nohd<t> root = heder.pairent;

           reepeet
           {
               booleean is_les = phals;
               string outb(connpairing entrees);
               outb.println();
               daata.les(root.daata, is_les);
               iph (is_les)
               {
                   booleean root_lepht_is_nul = phals;
                   root.nohd.lepht.is_nul(root_lepht_is_nul);
                   iph (!root_lepht_is_nul)
                   {
                       root.nohd = root.lepht;
                   }
                   els
                   {
                       nohd<t> nioo_nohd(root,daata);
                       root.lepht = nioo_nohd;
                       booleean is_phurst = phals;
                       heder.lepht.eecuuols(root,is_phurst);
                       iph (is_phurst)
                       {
                           heder.lepht = nioo_nohd;
                       }
                       direcshon dir(phronn_lepht);
                       balans_tree(root.nohd, dir);
                       reeturn;
                   }
              }
              els
              {
                   booleean is_graater = phals;
                   root.daata.les(daata, is_graater);
                   iph (is_graater)
                   {  
                       booleean root_riit_is_nul = phals;
                       root.nohd.riit.is_nul(root_riit_is_nul);
                       iph (!root_riit_is_nul)
                       {
                           root = root.riit;
                       }
                       els
                       {
                           nohd<t> nioo(root,daata);
                           root.riit = nioo;
                           booleean is_lahst = phals;
                           heder.riit.eecuuols(root,is_lahst);
                           iph (is_lahst)
                           {
                               heder.riit = nioo_nohd;
                           }
                           direcshon dirb(phronn_riit);
                           balans_tree(root.nohd, dirb);
                           reeturn;
                       }
                   }
                   els // iiten orlredee ecsists
                   {
                       string s(entree orlredee ecsists);
                       entree_orlredee_ecsists_ecssepshon p(s);
                       throuu p;
                   }
              }
          }
      }
  }

} </lang>

C

See AVL tree/C

C#

See AVL_tree/C_sharp.

C++

Translation of: D

<lang cpp>

1. include <algorithm>
2. include <iostream>

/* AVL node */ template <class T> class AVLnode { public:

   T key;
   int balance;
   AVLnode *left, *right, *parent;

   AVLnode(T k, AVLnode *p) : key(k), balance(0), parent(p),
                       left(NULL), right(NULL) {}

   ~AVLnode() {
       delete left;
       delete right;
   }

};

/* AVL tree */ template <class T> class AVLtree { public:

   AVLtree(void);
   ~AVLtree(void);
   bool insert(T key);
   void deleteKey(const T key);
   void printBalance();

private:

   AVLnode<T> *root;

   AVLnode<T>* rotateLeft          ( AVLnode<T> *a );
   AVLnode<T>* rotateRight         ( AVLnode<T> *a );
   AVLnode<T>* rotateLeftThenRight ( AVLnode<T> *n );
   AVLnode<T>* rotateRightThenLeft ( AVLnode<T> *n );
   void rebalance                  ( AVLnode<T> *n );
   int height                      ( AVLnode<T> *n );
   void setBalance                 ( AVLnode<T> *n );
   void printBalance               ( AVLnode<T> *n );
   void clearNode                  ( AVLnode<T> *n );

};

/* AVL class definition */ template <class T> void AVLtree<T>::rebalance(AVLnode<T> *n) {

   setBalance(n);

   if (n->balance == -2) {
       if (height(n->left->left) >= height(n->left->right))
           n = rotateRight(n);
       else
           n = rotateLeftThenRight(n);
   }
   else if (n->balance == 2) {
       if (height(n->right->right) >= height(n->right->left))
           n = rotateLeft(n);
       else
           n = rotateRightThenLeft(n);
   }

   if (n->parent != NULL) {
       rebalance(n->parent);
   }
   else {
       root = n;
   }

}

template <class T> AVLnode<T>* AVLtree<T>::rotateLeft(AVLnode<T> *a) {

   AVLnode<T> *b = a->right;
   b->parent = a->parent;
   a->right = b->left;

   if (a->right != NULL)
       a->right->parent = a;

   b->left = a;
   a->parent = b;

   if (b->parent != NULL) {
       if (b->parent->right == a) {
           b->parent->right = b;
       }
       else {
           b->parent->left = b;
       }
   }

   setBalance(a);
   setBalance(b);
   return b;

}

template <class T> AVLnode<T>* AVLtree<T>::rotateRight(AVLnode<T> *a) {

   AVLnode<T> *b = a->left;
   b->parent = a->parent;
   a->left = b->right;

   if (a->left != NULL)
       a->left->parent = a;

   b->right = a;
   a->parent = b;

   if (b->parent != NULL) {
       if (b->parent->right == a) {
           b->parent->right = b;
       }
       else {
           b->parent->left = b;
       }
   }

   setBalance(a);
   setBalance(b);
   return b;

}

template <class T> AVLnode<T>* AVLtree<T>::rotateLeftThenRight(AVLnode<T> *n) {

   n->left = rotateLeft(n->left);
   return rotateRight(n);

}

template <class T> AVLnode<T>* AVLtree<T>::rotateRightThenLeft(AVLnode<T> *n) {

   n->right = rotateRight(n->right);
   return rotateLeft(n);

}

template <class T> int AVLtree<T>::height(AVLnode<T> *n) {

   if (n == NULL)
       return -1;
   return 1 + std::max(height(n->left), height(n->right));

}

template <class T> void AVLtree<T>::setBalance(AVLnode<T> *n) {

   n->balance = height(n->right) - height(n->left);

}

template <class T> void AVLtree<T>::printBalance(AVLnode<T> *n) {

   if (n != NULL) {
       printBalance(n->left);
       std::cout << n->balance << " ";
       printBalance(n->right);
   }

}

template <class T> AVLtree<T>::AVLtree(void) : root(NULL) {}

template <class T> AVLtree<T>::~AVLtree(void) {

   delete root;

}

template <class T> bool AVLtree<T>::insert(T key) {

   if (root == NULL) {
       root = new AVLnode<T>(key, NULL);
   }
   else {
       AVLnode<T>
           *n = root,
           *parent;

       while (true) {
           if (n->key == key)
               return false;

           parent = n;

           bool goLeft = n->key > key;
           n = goLeft ? n->left : n->right;

           if (n == NULL) {
               if (goLeft) {
                   parent->left = new AVLnode<T>(key, parent);
               }
               else {
                   parent->right = new AVLnode<T>(key, parent);
               }

               rebalance(parent);
               break;
           }
       }
   }

   return true;

}

template <class T> void AVLtree<T>::deleteKey(const T delKey) {

   if (root == NULL)
       return;

   AVLnode<T>
       *n       = root,
       *parent  = root,
       *delNode = NULL,
       *child   = root;

   while (child != NULL) {
       parent = n;
       n = child;
       child = delKey >= n->key ? n->right : n->left;
       if (delKey == n->key)
           delNode = n;
   }

   if (delNode != NULL) {
       delNode->key = n->key;

       child = n->left != NULL ? n->left : n->right;

       if (root->key == delKey) {
           root = child;
       }
       else {
           if (parent->left == n) {
               parent->left = child;
           }
           else {
               parent->right = child;
           }

           rebalance(parent);
       }
   }

}

template <class T> void AVLtree<T>::printBalance() {

   printBalance(root);
   std::cout << std::endl;

}

int main(void) {

   AVLtree<int> t;

   std::cout << "Inserting integer values 1 to 10" << std::endl;
   for (int i = 1; i <= 10; ++i)
       t.insert(i);

   std::cout << "Printing balance: ";
   t.printBalance();

} </lang>

Output:

Inserting integer values 1 to 10
Printing balance: 0 0 0 1 0 0 0 0 1 0 

More elaborate version

See AVL_tree/C++

Managed C++

See AVL_tree/Managed_C++ </lang>

Common Lisp

Provided is an imperative implementation of an AVL tree with a similar interface and documentation to HASH-TABLE. <lang lisp>(defpackage :avl-tree

 (:use :cl)
 (:export
  :avl-tree
  :make-avl-tree
  :avl-tree-count
  :avl-tree-p
  :avl-tree-key<=
  :gettree
  :remtree
  :clrtree
  :dfs-maptree
  :bfs-maptree))

(in-package :avl-tree)

(defstruct %tree

 key
 value
 (height 0 :type fixnum)
 left
 right)

(defstruct (avl-tree (:constructor %make-avl-tree))

 key<=
 tree
 (count 0 :type fixnum))

(defun make-avl-tree (key<=)

 "Create a new AVL tree using the given comparison function KEY<=

for emplacing keys into the tree."

 (%make-avl-tree :key<= key<=))

(declaim (inline

         recalc-height
         height balance
         swap-kv
         right-right-rotate
         right-left-rotate
         left-right-rotate
         left-left-rotate
         rotate))

(defun recalc-height (tree)

 "Calculate the new height of the tree from the heights of the children."
 (when tree
   (setf (%tree-height tree)
         (1+ (the fixnum (max (height (%tree-right tree))
                              (height (%tree-left tree))))))))

(declaim (ftype (function (t) fixnum) height balance)) (defun height (tree)

 (if tree (%tree-height tree) 0))

(defun balance (tree)

 (if tree
     (- (height (%tree-right tree))
        (height (%tree-left tree)))
     0))

(defmacro swap (place-a place-b)

 "Swap the values of two places."
 (let ((tmp (gensym)))
   `(let ((,tmp ,place-a))
      (setf ,place-a ,place-b)
      (setf ,place-b ,tmp))))

(defun swap-kv (tree-a tree-b)

 "Swap the keys and values of two trees."
 (swap (%tree-value tree-a) (%tree-value tree-b))
 (swap (%tree-key tree-a) (%tree-key tree-b)))

We should really use gensyms for the variables in here.

(defmacro slash-rotate (tree right left)

 "Rotate nodes in a slash `/` imbalance."
 `(let* ((a ,tree)
         (b (,right a))
         (c (,right b))
         (a-left (,left a))
         (b-left (,left b)))
    (setf (,right a) c)
    (setf (,left a) b)
    (setf (,left b) a-left)
    (setf (,right b) b-left)
    (swap-kv a b)
    (recalc-height b)
    (recalc-height a)))

(defmacro angle-rotate (tree right left)

 "Rotate nodes in an angle bracket `<` imbalance."
 `(let* ((a ,tree)
         (b (,right a))
         (c (,left b))
         (a-left (,left a))
         (c-left (,left c))
         (c-right (,right c)))
    (setf (,left a) c)
    (setf (,left c) a-left)
    (setf (,right c) c-left)
    (setf (,left b) c-right)
    (swap-kv a c)
    (recalc-height c)
    (recalc-height b)
    (recalc-height a)))

(defun right-right-rotate (tree)

 (slash-rotate tree %tree-right %tree-left))

(defun left-left-rotate (tree)

 (slash-rotate tree %tree-left %tree-right))

(defun right-left-rotate (tree)

 (angle-rotate tree %tree-right %tree-left))

(defun left-right-rotate (tree)

 (angle-rotate tree %tree-left %tree-right))

(defun rotate (tree)

 (declare (type %tree tree))
 "Perform a rotation on the given TREE if it is imbalanced."
 (recalc-height tree)
 (with-slots (left right) tree
   (let ((balance (balance tree)))
     (cond ((< 1 balance) ;; Right imbalanced tree
            (if (<= 0 (balance right))
                (right-right-rotate tree)
                (right-left-rotate tree)))
           ((> -1 balance) ;; Left imbalanced tree
            (if (<= 0 (balance left))
                (left-right-rotate tree)
                (left-left-rotate tree)))))))

(defun gettree (key avl-tree &optional default)

 "Finds an entry in AVL-TREE whos key is KEY and returns the

associated value and T as multiple values, or returns DEFAULT and NIL if there was no such entry. Entries can be added using SETF."

 (with-slots (key<= tree) avl-tree
   (labels
       ((rec (tree)
          (if tree
              (with-slots ((t-key key) left right value) tree
                (if (funcall key<= t-key key)
                    (if (funcall key<= key t-key)
                        (values value t)
                        (rec right))
                    (rec left)))
              (values default nil))))
     (rec tree))))

(defun puttree (value key avl-tree)

 ;;(declare (optimize speed))
 (declare (type avl-tree avl-tree))
 "Emplace the the VALUE with the given KEY into the AVL-TREE, or

overwrite the value if the given key already exists."

 (let ((node (make-%tree :key key :value value)))
   (with-slots (key<= tree count) avl-tree
     (cond (tree
            (labels
                ((rec (tree)
                   (with-slots ((t-key key) left right) tree
                     (if (funcall key<= t-key key)
                         (if (funcall key<= key t-key)
                             (setf (%tree-value tree) value)
                             (cond (right (rec right))
                                   (t (setf right node)
                                      (incf count))))
                         (cond (left (rec left))
                               (t (setf left node)
                                  (incf count))))
                     (rotate tree))))
              (rec tree)))
           (t (setf tree node)
              (incf count))))
   value))

(defun (setf gettree) (value key avl-tree &optional default)

 (declare (ignore default))
 (puttree value key avl-tree))

(defun remtree (key avl-tree)

 (declare (type avl-tree avl-tree))
 "Remove the entry in AVL-TREE associated with KEY. Return T if

there was such an entry, or NIL if not."

 (with-slots (key<= tree count) avl-tree
   (labels
       ((find-left (tree)
          (with-slots ((t-key key) left right) tree
            (if left
                (find-left left)
                tree)))
        (rec (tree &optional parent type)
          (when tree
            (prog1
                (with-slots ((t-key key) left right) tree
                  (if (funcall key<= t-key key)
                      (cond
                        ((funcall key<= key t-key)
                         (cond
                           ((and left right)
                            (let ((sub-left (find-left right)))
                              (swap-kv sub-left tree)
                              (rec right tree :right)))
                           (t
                            (let ((sub (or left right)))
                              (case type
                                (:right (setf (%tree-right parent) sub))
                                (:left (setf (%tree-left parent) sub))
                                (nil (setf (avl-tree-tree avl-tree) sub))))
                            (decf count)))
                         t)
                        (t (rec right tree :right)))
                      (rec left tree :left)))
              (when parent (rotate parent))))))
     (rec tree))))

(defun clrtree (avl-tree)

 "This removes all the entries from AVL-TREE and returns the tree itself."
 (setf (avl-tree-tree avl-tree) nil)
 (setf (avl-tree-count avl-tree) 0)
 avl-tree)

(defun dfs-maptree (function avl-tree)

 "For each entry in AVL-TREE call the two-argument FUNCTION on

the key and value of each entry in depth-first order from left to right. Consequences are undefined if AVL-TREE is modified during this call."

 (with-slots (key<= tree) avl-tree
   (labels
       ((rec (tree)
          (when tree
            (with-slots ((t-key key) left right key value) tree
              (rec left)
              (funcall function key value)
              (rec right)))))
     (rec tree))))

(defun bfs-maptree (function avl-tree)

 "For each entry in AVL-TREE call the two-argument FUNCTION on

the key and value of each entry in breadth-first order from left to right. Consequences are undefined if AVL-TREE is modified during this call."

 (with-slots (key<= tree) avl-tree
   (let* ((queue (cons nil nil))
          (end queue))
     (labels ((pushend (value)
                (when value
                  (setf (cdr end) (cons value nil))
                  (setf end (cdr end))))
              (empty-p () (eq nil (cdr queue)))
              (popfront ()
                (prog1 (pop (cdr queue))
                  (when (empty-p) (setf end queue)))))
       (when tree
         (pushend tree)
         (loop until (empty-p)
            do (let ((current (popfront)))
                 (with-slots (key value left right) current
                   (funcall function key value)
                   (pushend left)
                   (pushend right)))))))))

(defun test ()

 (let ((tree (make-avl-tree #'<=))
       (printer (lambda (k v) (print (list k v)))))
   (loop for key in '(0 8 6 4 2 3 7 9 1 5 5)
      for value in '(a b c d e f g h i j k)
      do (setf (gettree key tree) value))
   (loop for key in '(0 1 2 3 4 10)
      do (print (multiple-value-list (gettree key tree))))
   (terpri)
   (print tree)
   (terpri)
   (dfs-maptree printer tree)
   (terpri)
   (bfs-maptree printer tree)
   (terpri)
   (loop for key in '(0 1 2 3 10 7)
      do (print (remtree key tree)))
   (terpri)
   (print tree)
   (terpri)
   (clrtree tree)
   (print tree))
 (values))

(defun profile-test ()

 (let ((tree (make-avl-tree #'<=))
       (randoms (loop repeat 1000000 collect (random 100.0))))
   (loop for key in randoms do (setf (gettree key tree) key))))</lang>

D

Translation of: Java

<lang d>import std.stdio, std.algorithm;

class AVLtree {

   private Node* root;

   private static struct Node {
       private int key, balance;
       private Node* left, right, parent;

       this(in int k, Node* p) pure nothrow @safe @nogc {
           key = k;
           parent = p;
       }
   }

   public bool insert(in int key) pure nothrow @safe {
       if (root is null)
           root = new Node(key, null);
       else {
           Node* n = root;
           Node* parent;
           while (true) {
               if (n.key == key)
                   return false;

               parent = n;

               bool goLeft = n.key > key;
               n = goLeft ? n.left : n.right;

               if (n is null) {
                   if (goLeft) {
                       parent.left = new Node(key, parent);
                   } else {
                       parent.right = new Node(key, parent);
                   }
                   rebalance(parent);
                   break;
               }
           }
       }
       return true;
   }

   public void deleteKey(in int delKey) pure nothrow @safe @nogc {
       if (root is null)
           return;
       Node* n = root;
       Node* parent = root;
       Node* delNode = null;
       Node* child = root;

       while (child !is null) {
           parent = n;
           n = child;
           child = delKey >= n.key ? n.right : n.left;
           if (delKey == n.key)
               delNode = n;
       }

       if (delNode !is null) {
           delNode.key = n.key;

           child = n.left !is null ? n.left : n.right;

           if (root.key == delKey) {
               root = child;
           } else {
               if (parent.left is n) {
                   parent.left = child;
               } else {
                   parent.right = child;
               }
               rebalance(parent);
           }
       }
   }

   private void rebalance(Node* n) pure nothrow @safe @nogc {
       setBalance(n);

       if (n.balance == -2) {
           if (height(n.left.left) >= height(n.left.right))
               n = rotateRight(n);
           else
               n = rotateLeftThenRight(n);

       } else if (n.balance == 2) {
           if (height(n.right.right) >= height(n.right.left))
               n = rotateLeft(n);
           else
               n = rotateRightThenLeft(n);
       }

       if (n.parent !is null) {
           rebalance(n.parent);
       } else {
           root = n;
       }
   }

   private Node* rotateLeft(Node* a) pure nothrow @safe @nogc {
       Node* b = a.right;
       b.parent = a.parent;

       a.right = b.left;

       if (a.right !is null)
           a.right.parent = a;

       b.left = a;
       a.parent = b;

       if (b.parent !is null) {
           if (b.parent.right is a) {
               b.parent.right = b;
           } else {
               b.parent.left = b;
           }
       }

       setBalance(a, b);

       return b;
   }

   private Node* rotateRight(Node* a) pure nothrow @safe @nogc {
       Node* b = a.left;
       b.parent = a.parent;

       a.left = b.right;

       if (a.left !is null)
           a.left.parent = a;

       b.right = a;
       a.parent = b;

       if (b.parent !is null) {
           if (b.parent.right is a) {
               b.parent.right = b;
           } else {
               b.parent.left = b;
           }
       }

       setBalance(a, b);

       return b;
   }

   private Node* rotateLeftThenRight(Node* n) pure nothrow @safe @nogc {
       n.left = rotateLeft(n.left);
       return rotateRight(n);
   }

   private Node* rotateRightThenLeft(Node* n) pure nothrow @safe @nogc {
       n.right = rotateRight(n.right);
       return rotateLeft(n);
   }

   private int height(in Node* n) const pure nothrow @safe @nogc {
       if (n is null)
           return -1;
       return 1 + max(height(n.left), height(n.right));
   }

   private void setBalance(Node*[] nodes...) pure nothrow @safe @nogc {
       foreach (n; nodes)
           n.balance = height(n.right) - height(n.left);
   }

   public void printBalance() const @safe {
       printBalance(root);
   }

   private void printBalance(in Node* n) const @safe {
       if (n !is null) {
           printBalance(n.left);
           write(n.balance, ' ');
           printBalance(n.right);
       }
   }

}

void main() @safe {

   auto tree = new AVLtree();

   writeln("Inserting values 1 to 10");
   foreach (immutable i; 1 .. 11)
       tree.insert(i);

   write("Printing balance: ");
   tree.printBalance;

}</lang>

Output:

Inserting values 1 to 10
Printing balance: 0 0 0 1 0 0 0 0 1 0 

Go

A package: <lang go>package avl

// AVL tree adapted from Julienne Walker's presentation at // http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx. // This port uses similar indentifier names.

// The Key interface must be supported by data stored in the AVL tree. type Key interface {

   Less(Key) bool
   Eq(Key) bool

}

// Node is a node in an AVL tree. type Node struct {

   Data    Key      // anything comparable with Less and Eq.
   Balance int      // balance factor
   Link    [2]*Node // children, indexed by "direction", 0 or 1.

}

// A little readability function for returning the opposite of a direction, // where a direction is 0 or 1. Go inlines this. // Where JW writes !dir, this code has opp(dir). func opp(dir int) int {

   return 1 - dir

}

// single rotation func single(root *Node, dir int) *Node {

   save := root.Link[opp(dir)]
   root.Link[opp(dir)] = save.Link[dir]
   save.Link[dir] = root
   return save

}

// double rotation func double(root *Node, dir int) *Node {

   save := root.Link[opp(dir)].Link[dir]

   root.Link[opp(dir)].Link[dir] = save.Link[opp(dir)]
   save.Link[opp(dir)] = root.Link[opp(dir)]
   root.Link[opp(dir)] = save

   save = root.Link[opp(dir)]
   root.Link[opp(dir)] = save.Link[dir]
   save.Link[dir] = root
   return save

}

// adjust valance factors after double rotation func adjustBalance(root *Node, dir, bal int) {

   n := root.Link[dir]
   nn := n.Link[opp(dir)]
   switch nn.Balance {
   case 0:
       root.Balance = 0
       n.Balance = 0
   case bal:
       root.Balance = -bal
       n.Balance = 0
   default:
       root.Balance = 0
       n.Balance = bal
   }
   nn.Balance = 0

}

func insertBalance(root *Node, dir int) *Node {

   n := root.Link[dir]
   bal := 2*dir - 1
   if n.Balance == bal {
       root.Balance = 0
       n.Balance = 0
       return single(root, opp(dir))
   }
   adjustBalance(root, dir, bal)
   return double(root, opp(dir))

}

func insertR(root *Node, data Key) (*Node, bool) {

   if root == nil {
       return &Node{Data: data}, false
   }
   dir := 0
   if root.Data.Less(data) {
       dir = 1
   }
   var done bool
   root.Link[dir], done = insertR(root.Link[dir], data)
   if done {
       return root, true
   }
   root.Balance += 2*dir - 1
   switch root.Balance {
   case 0:
       return root, true
   case 1, -1:
       return root, false
   }
   return insertBalance(root, dir), true

}

// Insert a node into the AVL tree. // Data is inserted even if other data with the same key already exists. func Insert(tree **Node, data Key) {

   *tree, _ = insertR(*tree, data)

}

func removeBalance(root *Node, dir int) (*Node, bool) {

   n := root.Link[opp(dir)]
   bal := 2*dir - 1
   switch n.Balance {
   case -bal:
       root.Balance = 0
       n.Balance = 0
       return single(root, dir), false
   case bal:
       adjustBalance(root, opp(dir), -bal)
       return double(root, dir), false
   }
   root.Balance = -bal
   n.Balance = bal
   return single(root, dir), true

}

func removeR(root *Node, data Key) (*Node, bool) {

   if root == nil {
       return nil, false
   }
   if root.Data.Eq(data) {
       switch {
       case root.Link[0] == nil:
           return root.Link[1], false
       case root.Link[1] == nil:
           return root.Link[0], false
       }
       heir := root.Link[0]
       for heir.Link[1] != nil {
           heir = heir.Link[1]
       }
       root.Data = heir.Data
       data = heir.Data
   }
   dir := 0
   if root.Data.Less(data) {
       dir = 1
   }
   var done bool
   root.Link[dir], done = removeR(root.Link[dir], data)
   if done {
       return root, true
   }
   root.Balance += 1 - 2*dir
   switch root.Balance {
   case 1, -1:
       return root, true
   case 0:
       return root, false
   }
   return removeBalance(root, dir)

}

// Remove a single item from an AVL tree. // If key does not exist, function has no effect. func Remove(tree **Node, data Key) {

   *tree, _ = removeR(*tree, data)

}</lang> A demonstration program: <lang go>package main

import (

   "encoding/json"
   "fmt"
   "log"

   "avl"

)

type intKey int

// satisfy avl.Key func (k intKey) Less(k2 avl.Key) bool { return k < k2.(intKey) } func (k intKey) Eq(k2 avl.Key) bool { return k == k2.(intKey) }

// use json for cheap tree visualization func dump(tree *avl.Node) {

   b, err := json.MarshalIndent(tree, "", "   ")
   if err != nil {
       log.Fatal(err)
   }
   fmt.Println(string(b))

}

func main() {

   var tree *avl.Node
   fmt.Println("Empty tree:")
   dump(tree)

   fmt.Println("\nInsert test:")
   avl.Insert(&tree, intKey(3))
   avl.Insert(&tree, intKey(1))
   avl.Insert(&tree, intKey(4))
   avl.Insert(&tree, intKey(1))
   avl.Insert(&tree, intKey(5))
   dump(tree)

   fmt.Println("\nRemove test:")
   avl.Remove(&tree, intKey(3))
   avl.Remove(&tree, intKey(1))
   dump(tree)

}</lang>

Output:

Empty tree:
null

Insert test:
{
   "Data": 3,
   "Balance": 0,
   "Link": [
      {
         "Data": 1,
         "Balance": -1,
         "Link": [
            {
               "Data": 1,
               "Balance": 0,
               "Link": [
                  null,
                  null
               ]
            },
            null
         ]
      },
      {
         "Data": 4,
         "Balance": 1,
         "Link": [
            null,
            {
               "Data": 5,
               "Balance": 0,
               "Link": [
                  null,
                  null
               ]
            }
         ]
      }
   ]
}

Remove test:
{
   "Data": 4,
   "Balance": 0,
   "Link": [
      {
         "Data": 1,
         "Balance": 0,
         "Link": [
            null,
            null
         ]
      },
      {
         "Data": 5,
         "Balance": 0,
         "Link": [
            null,
            null
         ]
      }
   ]
}

Haskell

Based on solution of homework #4 from course http://www.seas.upenn.edu/~cis194/spring13/lectures.html. <lang haskell>import Data.Monoid

data Tree a

 = Leaf
 | Node Int
        (Tree a)
        a
        (Tree a)
 deriving (Show, Eq)

foldTree

 :: Ord a
 => [a] -> Tree a

foldTree = foldr insert Leaf

height Leaf = -1 height (Node h _ _ _) = h

depth a b = 1 + (height a `max` height b)

insert

 :: Ord a
 => a -> Tree a -> Tree a

insert v Leaf = Node 1 Leaf v Leaf insert v t@(Node n left v_ right)

 | v_ < v = rotate $ Node n left v_ (insert v right)
 | v_ > v = rotate $ Node n (insert v left) v_ right
 | otherwise = t

max_

 :: Ord a
 => Tree a -> Maybe a

max_ Leaf = Nothing max_ (Node _ _ v right) =

 case right of
   Leaf -> Just v
   _ -> max_ right

delete

 :: Ord a
 => a -> Tree a -> Tree a

delete _ Leaf = Leaf delete x (Node h left v right)

 | x == v =
   maybe left (\m -> rotate $ Node h left m (delete m right)) (max_ right)
 | x > v = rotate $ Node h left v (delete x right)
 | x < v = rotate $ Node h (delete x left) v right

rotate :: Tree a -> Tree a rotate Leaf = Leaf -- left left case rotate (Node h (Node lh ll lv lr) v r)

 | lh - height r > 1 && height ll - height lr > 0 =
   Node lh ll lv (Node (depth r lr) lr v r)

-- right right case rotate (Node h l v (Node rh rl rv rr))

 | rh - height l > 1 && height rr - height rl > 0 =
   Node rh (Node (depth l rl) l v rl) rv rr

-- left right case rotate (Node h (Node lh ll lv (Node rh rl rv rr)) v r)

 | lh - height r > 1 =
   Node h (Node (rh + 1) (Node (lh - 1) ll lv rl) rv rr) v r

-- right left case rotate (Node h l v (Node rh (Node lh ll lv lr) rv rr))

 | rh - height l > 1 =
   Node h l v (Node (lh + 1) ll lv (Node (rh - 1) lr rv rr))

-- re-weighting rotate (Node h l v r) =

 let (l_, r_) = (rotate l, rotate r)
 in Node (depth l_ r_) l_ v r_

draw

 :: Show a
 => Tree a -> String

draw t = '\n' : draw_ t 0 <> "\n"

 where
   draw_ Leaf _ = []
   draw_ (Node h l v r) d = draw_ r (d + 1) <> node <> draw_ l (d + 1)
     where
       node = padding d <> show (v, h) <> "\n"
       padding n = replicate (n * 4) ' '

main :: IO () main = putStr $ draw $ foldTree [1 .. 15]</lang>

Output:

            (15,0)
        (14,1)
            (13,0)
    (12,2)
            (11,0)
        (10,1)
            (9,0)
(8,3)
            (7,0)
        (6,1)
            (5,0)
    (4,2)
            (3,0)
        (2,1)
            (1,0)

Java

This code has been cobbled together from various online examples. It's not easy to find a clear and complete explanation of AVL trees. Textbooks tend to concentrate on red-black trees because of their better efficiency. (AVL trees need to make 2 passes through the tree when inserting and deleting: one down to find the node to operate upon and one up to rebalance the tree.) <lang java>public class AVLtree {

   private Node root;

   private static class Node {
       private int key;
       private int balance;
       private int height;
       private Node left;
       private Node right;
       private Node parent;

       Node(int key, Node parent) {
           this.key = key;
           this.parent = parent;
       }
   }

   public boolean insert(int key) {
       if (root == null) {
           root = new Node(key, null);
           return true;
       }

       Node n = root;
       while (true) {
           if (n.key == key)
               return false;

           Node parent = n;

           boolean goLeft = n.key > key;
           n = goLeft ? n.left : n.right;

           if (n == null) {
               if (goLeft) {
                   parent.left = new Node(key, parent);
               } else {
                   parent.right = new Node(key, parent);
               }
               rebalance(parent);
               break;
           }
       }
       return true;
   }

   private void delete(Node node) {
       if (node.left == null && node.right == null) {
           if (node.parent == null) {
               root = null;
           } else {
               Node parent = node.parent;
               if (parent.left == node) {
                   parent.left = null;
               } else {
                   parent.right = null;
               }
               rebalance(parent);
           }
           return;
       }

       if (node.left != null) {
           Node child = node.left;
           while (child.right != null) child = child.right;
           node.key = child.key;
           delete(child);
       } else {
           Node child = node.right;
           while (child.left != null) child = child.left;
           node.key = child.key;
           delete(child);
       }
   }

   public void delete(int delKey) {
       if (root == null)
           return;

       Node child = root;
       while (child != null) {
           Node node = child;
           child = delKey >= node.key ? node.right : node.left;
           if (delKey == node.key) {
               delete(node);
               return;
           }
       }
   }

   private void rebalance(Node n) {
       setBalance(n);

       if (n.balance == -2) {
           if (height(n.left.left) >= height(n.left.right))
               n = rotateRight(n);
           else
               n = rotateLeftThenRight(n);

       } else if (n.balance == 2) {
           if (height(n.right.right) >= height(n.right.left))
               n = rotateLeft(n);
           else
               n = rotateRightThenLeft(n);
       }

       if (n.parent != null) {
           rebalance(n.parent);
       } else {
           root = n;
       }
   }

   private Node rotateLeft(Node a) {

       Node b = a.right;
       b.parent = a.parent;

       a.right = b.left;

       if (a.right != null)
           a.right.parent = a;

       b.left = a;
       a.parent = b;

       if (b.parent != null) {
           if (b.parent.right == a) {
               b.parent.right = b;
           } else {
               b.parent.left = b;
           }
       }

       setBalance(a, b);

       return b;
   }

   private Node rotateRight(Node a) {

       Node b = a.left;
       b.parent = a.parent;

       a.left = b.right;

       if (a.left != null)
           a.left.parent = a;

       b.right = a;
       a.parent = b;

       if (b.parent != null) {
           if (b.parent.right == a) {
               b.parent.right = b;
           } else {
               b.parent.left = b;
           }
       }

       setBalance(a, b);

       return b;
   }

   private Node rotateLeftThenRight(Node n) {
       n.left = rotateLeft(n.left);
       return rotateRight(n);
   }

   private Node rotateRightThenLeft(Node n) {
       n.right = rotateRight(n.right);
       return rotateLeft(n);
   }

   private int height(Node n) {
       if (n == null)
           return -1;
       return n.height;
   }

   private void setBalance(Node... nodes) {
       for (Node n : nodes) {
           reheight(n);
           n.balance = height(n.right) - height(n.left);
       }
   }

   public void printBalance() {
       printBalance(root);
   }

   private void printBalance(Node n) {
       if (n != null) {
           printBalance(n.left);
           System.out.printf("%s ", n.balance);
           printBalance(n.right);
       }
   }

   private void reheight(Node node) {
       if (node != null) {
           node.height = 1 + Math.max(height(node.left), height(node.right));
       }
   }

   public static void main(String[] args) {
       AVLtree tree = new AVLtree();

       System.out.println("Inserting values 1 to 10");
       for (int i = 1; i < 10; i++)
           tree.insert(i);

       System.out.print("Printing balance: ");
       tree.printBalance();
   }

}</lang>

Inserting values 1 to 10
Printing balance: 0 0 0 1 0 1 0 0 0

More elaborate version

See AVL_tree/Java

Julia

Translation of: Sidef

<lang julia>module AVLTrees

import Base.print export AVLNode, AVLTree, insert, deletekey, deletevalue, findnodebykey, findnodebyvalue, allnodes

@enum Direction LEFT RIGHT avlhash(x) = Int32(hash(x) & 0xfffffff) const MIDHASH = Int32(div(0xfffffff, 2))

mutable struct AVLNode{T}

   value::T
   key::Int32
   balance::Int32
   left::Union{AVLNode, Nothing}
   right::Union{AVLNode, Nothing}
   parent::Union{AVLNode, Nothing}

end AVLNode(v::T, b, l, r, p) where T <: Real = AVLNode(v, avlhash(v), Int32(b), l, r, p) AVLNode(v::T, h, b::Int64, l, r, p) where T <: Real = AVLNode(v, h, Int32(b), l, r, p) AVLNode(v::T) where T <: Real = AVLNode(v, avlhash(v), Int32(0), nothing, nothing, nothing)

AVLTree(typ::Type) = AVLNode(typ(0), MIDHASH, Int32(0), nothing, nothing, nothing) const MaybeAVL = Union{AVLNode, Nothing}

height(node::MaybeAVL) = (node == nothing) ? 0 : 1 + max(height(node.right), height(node.left))

function insert(node, value)

   if node == nothing
       node = AVLNode(value)
       return true
   end
   key, n, parent::MaybeAVL = avlhash(value), node, nothing
   while true
       if n.key == key
           return false
       end
       parent = n
       ngreater = n.key > key
       n = ngreater ? n.left : n.right
       if n == nothing
           if ngreater
               parent.left = AVLNode(value, key, 0, nothing, nothing, parent)
           else
               parent.right = AVLNode(value, key, 0, nothing, nothing, parent)
           end
           rebalance(parent)
           break
       end
   end
   return true

end

function deletekey(node, delkey)

   node == nothing && return nothing
   n, parent = MaybeAVL(node), MaybeAVL(node)
   delnode, child = MaybeAVL(nothing), MaybeAVL(node)
   while child != nothing
       parent, n = n, child
       child = delkey >= n.key ? n.right : n.left
       if delkey == n.key
           delnode = n
       end
   end
   if delnode != nothing
       delnode.key = n.key
       delnode.value = n.value
       child = (n.left != nothing) ? n.left : n.right
       if node.key == delkey
           root = child
       else
           if parent.left == n
               parent.left = child
           else
               parent.right = child
           end
           rebalance(parent)
       end
   end

end

deletevalue(node, val) = deletekey(node, avlhash(val))

function rebalance(node::MaybeAVL)

   node == nothing && return nothing
   setbalance(node)
   if node.balance < -1
       if height(node.left.left) >= height(node.left.right)
           node = rotate(node, RIGHT)
       else
           node = rotatetwice(node, LEFT, RIGHT)
       end
   elseif node.balance > 1
       if node.right != nothing && height(node.right.right) >= height(node.right.left)
           node = rotate(node, LEFT)
       else
           node = rotatetwice(node, RIGHT, LEFT)
       end
   end
   if node != nothing && node.parent != nothing
       rebalance(node.parent)
   end

end

function rotate(a, direction)

   (a == nothing || a.parent == nothing) && return nothing
   b = direction == LEFT ? a.right : a.left
   b == nothing && return
   b.parent = a.parent
   if direction == LEFT
       a.right = b.left
   else
       a.left  = b.right
   end
   if a.right != nothing
       a.right.parent = a
   end
   if direction == LEFT
       b.left = a
   else
       b.right = a
   end
   a.parent = b
   if b.parent != nothing
       if b.parent.right == a
           b.parent.right = b
       else
           b.parent.left = b
       end
   end
   setbalance([a, b])
   return b

end

function rotatetwice(n, dir1, dir2)

   n.left = rotate(n.left, dir1)
   rotate(n, dir2)

end

setbalance(n::AVLNode) = begin n.balance = height(n.right) - height(n.left) end setbalance(n::Nothing) = 0 setbalance(nodes::Vector) = for n in nodes setbalance(n) end

function findnodebykey(node, key)

   result::MaybeAVL = node == nothing ? nothing : node.key == key ? node : 
       node.left != nothing && (n = findbykey(n, key) != nothing) ? n :
       node.right != nothing ? findbykey(node.right, key) : nothing
   return result

end findnodebyvalue(node, val) = findnodebykey(node, avlhash(v))

function allnodes(node)

   result = AVLNode[]
   if node != nothing
       append!(result, allnodes(node.left))
       if node.key != MIDHASH
           push!(result, node)
       end
       append!(result, node.right)
   end
   return result

end

function Base.print(io::IO, n::MaybeAVL)

   if n != nothing
       n.left != nothing && print(io, n.left)
       print(io, n.key == MIDHASH ? "<ROOT> " : "<$(n.key):$(n.value):$(n.balance)> ")
       n.right != nothing && print(io, n.right)
   end

end

end # module

using .AVLTrees

const tree = AVLTree(Int)

println("Inserting 10 values.") foreach(x -> insert(tree, x), rand(collect(1:80), 10)) println("Printing tree after insertion: ") println(tree)

</lang>

Output:

Inserting 10 values.
Printing tree after insertion:
<35627180:79:1> <51983710:44:0> <55727576:19:0> <95692146:13:0> <119148308:42:0> <131027959:27:0> <ROOT> <144455609:36:0> <172953853:41:1> <203559702:58:1> <217724037:80:0>

Kotlin

Translation of: Java

<lang kotlin>class AvlTree {

   private var root: Node? = null

   private class Node(var key: Int, var parent: Node?) {
       var balance: Int = 0
       var left : Node? = null
       var right: Node? = null
   }

   fun insert(key: Int): Boolean {
       if (root == null)
           root = Node(key, null)
       else {
           var n: Node? = root
           var parent: Node
           while (true) {
               if (n!!.key == key) return false
               parent = n
               val goLeft = n.key > key
               n = if (goLeft) n.left else n.right
               if (n == null) {
                   if (goLeft)
                       parent.left  = Node(key, parent)
                   else
                       parent.right = Node(key, parent)
                   rebalance(parent)
                   break
               }
           }
       }
       return true
   }

   fun delete(delKey: Int) {
       if (root == null) return
       var n:       Node? = root
       var parent:  Node? = root
       var delNode: Node? = null
       var child:   Node? = root
       while (child != null) {
           parent = n
           n = child
           child = if (delKey >= n.key) n.right else n.left
           if (delKey == n.key) delNode = n
       }
       if (delNode != null) {
           delNode.key = n!!.key
           child = if (n.left != null) n.left else n.right
           if (0 == root!!.key.compareTo(delKey)) {
               root = child

               if (null != root) {
                   root!!.parent = null
               }

           } else {
               if (parent!!.left == n)
                   parent.left = child
               else
                   parent.right = child

               if (null != child) {
                   child.parent = parent
               }

               rebalance(parent)
           }
   }

   private fun rebalance(n: Node) {
       setBalance(n)
       var nn = n
       if (nn.balance == -2)
           if (height(nn.left!!.left) >= height(nn.left!!.right))
               nn = rotateRight(nn)
           else
               nn = rotateLeftThenRight(nn)
       else if (nn.balance == 2)
           if (height(nn.right!!.right) >= height(nn.right!!.left))
               nn = rotateLeft(nn)
           else
               nn = rotateRightThenLeft(nn)
       if (nn.parent != null) rebalance(nn.parent!!)
       else root = nn
   }

   private fun rotateLeft(a: Node): Node {
       val b: Node? = a.right
       b!!.parent = a.parent
       a.right = b.left
       if (a.right != null) a.right!!.parent = a
       b.left = a
       a.parent = b
       if (b.parent != null) {
           if (b.parent!!.right == a)
               b.parent!!.right = b
           else
               b.parent!!.left = b
       }
       setBalance(a, b)
       return b
   }

   private fun rotateRight(a: Node): Node {
       val b: Node? = a.left
       b!!.parent = a.parent
       a.left = b.right
       if (a.left != null) a.left!!.parent = a
       b.right = a
       a.parent = b
       if (b.parent != null) {
           if (b.parent!!.right == a)
               b.parent!!.right = b
           else
               b.parent!!.left = b
       }
       setBalance(a, b)
       return b
   }

   private fun rotateLeftThenRight(n: Node): Node {
       n.left = rotateLeft(n.left!!)
       return rotateRight(n)
   }

   private fun rotateRightThenLeft(n: Node): Node {
       n.right = rotateRight(n.right!!)
       return rotateLeft(n)
   }

   private fun height(n: Node?): Int {
       if (n == null) return -1
       return 1 + Math.max(height(n.left), height(n.right))
   }

   private fun setBalance(vararg nodes: Node) {
       for (n in nodes) n.balance = height(n.right) - height(n.left)
   }

   fun printKey() {
       printKey(root)
       println()
   }

   private fun printKey(n: Node?) {
       if (n != null) {
           printKey(n.left)
           print("${n.key} ")
           printKey(n.right)
       }
   }

   fun printBalance() {
       printBalance(root)
       println()
   }

   private fun printBalance(n: Node?) {
       if (n != null) {
           printBalance(n.left)
           print("${n.balance} ")
           printBalance(n.right)
       }
   }

}

fun main(args: Array<String>) {

   val tree = AvlTree()
   println("Inserting values 1 to 10")
   for (i in 1..10) tree.insert(i)
   print("Printing key     : ")
   tree.printKey()
   print("Printing balance : ")
   tree.printBalance()

}</lang>

Output:

Inserting values 1 to 10
Printing key     : 1 2 3 4 5 6 7 8 9 10
Printing balance : 0 0 0 1 0 0 0 0 1 0

Lua

<lang Lua>AVL={balance=0} AVL.__mt={__index = AVL}

function AVL:new(list)

 local o={}  
 setmetatable(o, AVL.__mt)
 for _,v in ipairs(list or {}) do
   o=o:insert(v)
 end
 return o

end

function AVL:rebalance()

 local rotated=false
 if self.balance>1 then
   if self.right.balance<0 then
     self.right, self.right.left.right, self.right.left = self.right.left, self.right, self.right.left.right
     self.right.right.balance=self.right.balance>-1 and 0 or 1
     self.right.balance=self.right.balance>0 and 2 or 1
   end
   self, self.right.left, self.right = self.right, self, self.right.left
   self.left.balance=1-self.balance
   self.balance=self.balance==0 and -1 or 0
   rotated=true
 elseif self.balance<-1 then
   if self.left.balance>0 then
     self.left, self.left.right.left, self.left.right = self.left.right, self.left, self.left.right.left
     self.left.left.balance=self.left.balance<1 and 0 or -1
     self.left.balance=self.left.balance<0 and -2 or -1
   end
   self, self.left.right, self.left = self.left, self, self.left.right
   self.right.balance=-1-self.balance
   self.balance=self.balance==0 and 1 or 0
   rotated=true
 end
 return self,rotated

end

function AVL:insert(v)

 if not self.value then 
   self.value=v
   self.balance=0
   return self,1
 end
 local grow
 if v==self.value then
   return self,0
 elseif v<self.value then
   if not self.left then self.left=self:new() end
   self.left,grow=self.left:insert(v)
   self.balance=self.balance-grow
 else
   if not self.right then self.right=self:new() end
   self.right,grow=self.right:insert(v)
   self.balance=self.balance+grow
 end
 self,rotated=self:rebalance()
 return self, (rotated or self.balance==0) and 0 or grow 

end

function AVL:delete_move(dir,other,mul)

 if self[dir] then
   local sb2,v
   self[dir], sb2, v=self[dir]:delete_move(dir,other,mul)
   self.balance=self.balance+sb2*mul
   self,sb2=self:rebalance()
   return self,(sb2 or self.balance==0) and -1 or 0,v
 else
   return self[other],-1,self.value
 end

end

function AVL:delete(v,isSubtree)

 local grow=0
 if v==self.value then
   local v
   if self.balance>0 then
     self.right,grow,v=self.right:delete_move("left","right",-1)
   elseif self.left then
     self.left,grow,v=self.left:delete_move("right","left",1)
     grow=-grow
   else
     return not isSubtree and AVL:new(),-1
   end
   self.value=v
   self.balance=self.balance+grow
 elseif v<self.value and self.left then
   self.left,grow=self.left:delete(v,true)
   self.balance=self.balance-grow
 elseif v>self.value and self.right then
   self.right,grow=self.right:delete(v,true)
   self.balance=self.balance+grow
 else
   return self,0
 end
 self,rotated=self:rebalance()
 return self, grow~=0 and (rotated or self.balance==0) and -1 or 0

end

-- output functions

function AVL:toList(list)

 if not self.value then return {} end
 list=list or {}
 if self.left then self.left:toList(list) end
 list[#list+1]=self.value
 if self.right then self.right:toList(list) end
 return list

end

function AVL:dump(depth)

 if not self.value then return end
 depth=depth or 0
 if self.right then self.right:dump(depth+1) end
 print(string.rep("    ",depth)..self.value.." ("..self.balance..")")
 if self.left then self.left:dump(depth+1) end

end

-- test

local test=AVL:new{1,10,5,15,20,3,5,14,7,13,2,8,3,4,5,10,9,8,7}

test:dump() print("\ninsert 17:") test=test:insert(17) test:dump() print("\ndelete 10:") test=test:delete(10) test:dump() print("\nlist:") print(unpack(test:toList())) </lang>

Output:

            20 (0)
        15 (1)
    14 (1)
        13 (0)
10 (-1)
            9 (0)
        8 (0)
            7 (0)
    5 (-1)
                4 (0)
            3 (1)
        2 (1)
            1 (0)

insert 17:
            20 (0)
        17 (0)
            15 (0)
    14 (1)
        13 (0)
10 (-1)
            9 (0)
        8 (0)
            7 (0)
    5 (-1)
                4 (0)
            3 (1)
        2 (1)
            1 (0)

delete 10:
            20 (0)
        17 (0)
            15 (0)
    14 (1)
        13 (0)
9 (-1)
        8 (-1)
            7 (0)
    5 (-1)
                4 (0)
            3 (1)
        2 (1)
            1 (0)

list:
1       2       3       4       5       7       8       9       13      14      15      17      20

Objeck

Translation of: Java

<lang objeck>class AVLNode {

 @key : Int;
 @balance : Int;
 @height : Int;
 @left : AVLNode;
 @right : AVLNode;
 @above : AVLNode;
 
 New(key : Int, above : AVLNode) {
   @key := key;
   @above := above;
 }

 method : public : GetKey() ~ Int {
   return @key;
 }

 method : public : GetLeft() ~ AVLNode {
   return @left;
 }

 method : public : GetRight() ~ AVLNode {
   return @right;
 }

 method : public : GetAbove() ~ AVLNode {
   return @above;
 }

 method : public : GetBalance() ~ Int {
   return @balance;
 }

 method : public : GetHeight() ~ Int {
   return @height;
 }

 method : public : SetBalance(balance : Int) ~ Nil {
   @balance := balance;
 }

 method : public : SetHeight(height : Int) ~ Nil {
   @height := height;
 }

 method : public : SetAbove(above : AVLNode) ~ Nil {
   @above := above;
 }

 method : public : SetLeft(left : AVLNode) ~ Nil {
   @left := left;
 }

 method : public : SetRight(right : AVLNode) ~ Nil {
   @right := right;
 }

 method : public : SetKey(key : Int) ~ Nil {
   @key := key;
 }

}

class AVLTree {

 @root : AVLNode;

 New() {}

 method : public : Insert(key : Int) ~ Bool {
   if(@root = Nil) {
     @root := AVLNode->New( key, Nil);
     return true;
   };

   n := @root;
   while(true) {
     if(n->GetKey() = key) {
       return false;
     };
     
     parent := n;
     goLeft := n->GetKey() > key;
     n := goLeft ? n->GetLeft() : n->GetRight();

     if(n = Nil) {
       if(goLeft) {
         parent->SetLeft(AVLNode->New( key, parent));
       } else {
         parent->SetRight(AVLNode->New( key, parent));
       };
       Rebalance(parent);
       break;
     };
   };

   return true;
 }

 method : Delete(node : AVLNode) ~ Nil {
   if (node->GetLeft() = Nil & node->GetRight() = Nil) {
     if (node ->GetAbove() = Nil) {
       @root := Nil;
     } else {
       parent := node ->GetAbove();
       if (parent->GetLeft() = node) {
         parent->SetLeft(Nil);
       } else {
         parent->SetRight(Nil);
       };
       Rebalance(parent);
     };
     return;
   };

   if (node->GetLeft() <> Nil) {
     child := node->GetLeft();
     while (child->GetRight() <> Nil) {
       child := child->GetRight();
     };
     node->SetKey(child->GetKey());
     Delete(child);
   } else {
     child := node->GetRight();
     while (child->GetLeft() <> Nil) {
       child := child->GetLeft();
     };
     node->SetKey(child->GetKey());
     Delete(child);
   };
 }

 method : public : Delete(delKey : Int) ~ Nil {
   if (@root = Nil) {
     return;
   };

   child := @root;
   while (child <> Nil) {
     node := child;
     child := delKey >= node->GetKey() ? node->GetRight() : node->GetLeft();
     if (delKey = node->GetKey()) {
       Delete(node);
       return;
     };
   };
 }

 method : Rebalance(n : AVLNode) ~ Nil {
   SetBalance(n);

   if (n->GetBalance() = -2) {
     if (Height(n->GetLeft()->GetLeft()) >= Height(n->GetLeft()->GetRight())) {
       n := RotateRight(n);
     }
     else {
       n := RotateLeftThenRight(n);
     };
    
   } else if (n->GetBalance() = 2) {
     if(Height(n->GetRight()->GetRight()) >= Height(n->GetRight()->GetLeft())) {
       n := RotateLeft(n);
     }
     else {
       n := RotateRightThenLeft(n);
     };
   };

   if(n->GetAbove() <> Nil) {
     Rebalance(n->GetAbove());
   } else {
     @root := n;
   };
 }

 method : RotateLeft(a : AVLNode) ~ AVLNode {
   b := a->GetRight();
   b->SetAbove(a->GetAbove());

   a->SetRight(b->GetLeft());

   if(a->GetRight() <> Nil) {
     a->GetRight()->SetAbove(a);
   };
   
   b->SetLeft(a);
   a->SetAbove(b);
   
   if (b->GetAbove() <> Nil) {
     if (b->GetAbove()->GetRight() = a) {
       b->GetAbove()->SetRight(b);
     } else {
       b->GetAbove()->SetLeft(b);
     };
   };

   SetBalance(a);
   SetBalance(b);

   return b;
 }
 
 method : RotateRight(a : AVLNode) ~ AVLNode {
   b := a->GetLeft();
   b->SetAbove(a->GetAbove());

   a->SetLeft(b->GetRight());
   
   if (a->GetLeft() <> Nil) {
     a->GetLeft()->SetAbove(a);
   };
   
   b->SetRight(a);
   a->SetAbove(b);

   if (b->GetAbove() <> Nil) {
     if (b->GetAbove()->GetRight() = a) {
       b->GetAbove()->SetRight(b);
     } else {
       b->GetAbove()->SetLeft(b);
     };
   };
   
   SetBalance(a);
   SetBalance(b);

   return b;
 }

 method : RotateLeftThenRight(n : AVLNode) ~ AVLNode {
   n->SetLeft(RotateLeft(n->GetLeft()));
   return RotateRight(n);
 }

 method : RotateRightThenLeft(n : AVLNode) ~ AVLNode {
   n->SetRight(RotateRight(n->GetRight()));
   return RotateLeft(n);
 }

 method : SetBalance(n : AVLNode) ~ Nil {
   Reheight(n);
   n->SetBalance(Height(n->GetRight()) - Height(n->GetLeft()));
 }

 method : Reheight(node : AVLNode) ~ Nil {
   if(node <> Nil) {
     node->SetHeight(1 + Int->Max(Height(node->GetLeft()), Height(node->GetRight())));
   };
 }

 method : Height(n : AVLNode) ~ Int {
   if(n = Nil) {
     return -1;
   };

   return n->GetHeight();
 }

 method : public : PrintBalance() ~ Nil {
   PrintBalance(@root);
 }

 method : PrintBalance(n : AVLNode) ~ Nil {
   if (n <> Nil) {
     PrintBalance(n->GetLeft());
     balance := n->GetBalance();
     "{$balance} "->Print();
     PrintBalance(n->GetRight());
   };
 }

}

class Test {

 function : Main(args : String[]) ~ Nil {
   tree := AVLTree->New();

   "Inserting values 1 to 10"->PrintLine();
   for(i := 1; i < 10; i+=1;) {
     tree->Insert(i);
   };

   "Printing balance: "->Print();
   tree->PrintBalance();
 }

} </lang>

Output:

Inserting values 1 to 10
Printing balance: 0 0 0 1 0 1 0 0 0

Objective-C

Translation of: Java

This example is incomplete. It is missing an @interface for AVLTree and also missing any @interface or @implementation for AVLTreeNode. Please ensure that it meets all task requirements and remove this message.

<lang Objective-C> @implementation AVLTree

-(BOOL)insertWithKey:(NSInteger)key {

   if (self.root == nil) {
       self.root = [[AVLTreeNode alloc]initWithKey:key andParent:nil];
   } else {
       
       AVLTreeNode *n = self.root;
       AVLTreeNode *parent;
       
       while (true) {
           
           if (n.key == key) {
               return false;
           }
           
           parent = n;
           
           BOOL goLeft = n.key > key;
           n = goLeft ? n.left : n.right;
           
           if (n == nil) {
               
               if (goLeft) {
                   parent.left = [[AVLTreeNode alloc]initWithKey:key andParent:parent];
               } else {
                   parent.right = [[AVLTreeNode alloc]initWithKey:key andParent:parent];
               }
               [self rebalanceStartingAtNode:parent];
               break;
           }
       }
   }
   
   return true;

}

-(void)rebalanceStartingAtNode:(AVLTreeNode*)n {

   [self setBalance:@[n]];
   
   if (n.balance == -2) {
       if ([self height:(n.left.left)] >= [self height:n.left.right]) {
           n = [self rotateRight:n];
       } else {
           n = [self rotateLeftThenRight:n];
       }
   } else if (n.balance == 2) {
       if ([self height:n.right.right] >= [self height:n.right.left]) {
           n = [self rotateLeft:n];
       } else {
           n = [self rotateRightThenLeft:n];
       }
   }
   
   if (n.parent != nil) {
       [self rebalanceStartingAtNode:n.parent];
   } else {
       self.root = n;
   }

}

-(AVLTreeNode*)rotateRight:(AVLTreeNode*)a {

   AVLTreeNode *b = a.left;
   b.parent = a.parent;
   
   a.left = b.right;
   
   if (a.left != nil) {
       a.left.parent = a;
   }
   
   b.right = a;
   a.parent = b;
   
   if (b.parent != nil) {
       if (b.parent.right == a) {
           b.parent.right = b;
       } else {
           b.parent.left = b;
       }
   }
   
   [self setBalance:@[a,b]];
   return b;
   

}

-(AVLTreeNode*)rotateLeftThenRight:(AVLTreeNode*)n {

   n.left = [self rotateLeft:n.left];
   return [self rotateRight:n];
   

}

-(AVLTreeNode*)rotateRightThenLeft:(AVLTreeNode*)n {

   n.right = [self rotateRight:n.right];
   return [self rotateLeft:n];

}

-(AVLTreeNode*)rotateLeft:(AVLTreeNode*)a {

   //set a's right node as b
   AVLTreeNode* b = a.right;
   //set b's parent as a's parent (which could be nil)
   b.parent = a.parent;
   //in case b had a left child transfer it to a
   a.right = b.left;
   
   // after changing a's reference to the right child, make sure the parent is set too
   if (a.right != nil) {
       a.right.parent = a;
   }
   
   // switch a over to the left to be b's left child
   b.left = a;
   a.parent = b;
   
   if (b.parent != nil) {
       if (b.parent.right == a) {
           b.parent.right = b;
       } else {
           b.parent.right = b;
       }
   }
   
   [self setBalance:@[a,b]];
   
   return b;
   

}

-(void) setBalance:(NSArray*)nodesArray {

   for (AVLTreeNode* n in nodesArray) {
       
       n.balance = [self height:n.right] - [self height:n.left];
   }
   

}

-(int)height:(AVLTreeNode*)n {

   if (n == nil) {
       return -1;
   }
   
   return 1 + MAX([self height:n.left], [self height:n.right]);

}

-(void)printKey:(AVLTreeNode*)n {

   if (n != nil) {
       [self printKey:n.left];
       NSLog(@"%ld", n.key);
       [self printKey:n.right];
   }

}

-(void)printBalance:(AVLTreeNode*)n {

   if (n != nil) {
       [self printBalance:n.left];
       NSLog(@"%ld", n.balance);
       [self printBalance:n.right];
   }

} @end -- test

int main(int argc, const char * argv[]) {

   @autoreleasepool {

       AVLTree *tree = [AVLTree new];
       NSLog(@"inserting values 1 to 6");
       [tree insertWithKey:1];
       [tree insertWithKey:2];
       [tree insertWithKey:3];
       [tree insertWithKey:4];
       [tree insertWithKey:5];
       [tree insertWithKey:6];
       
       NSLog(@"printing balance: ");
       [tree printBalance:tree.root];
       
       NSLog(@"printing key: ");
       [tree printKey:tree.root];
   }
   return 0;

}

</lang>

Output:

inserting values 1 to 6
printing balance:
0
0
0
0
1
0

printing key:
1
2
3
4
5
6

Phix

Translated from the C version at http://www.geeksforgeeks.org/avl-tree-set-2-deletion
The standard distribution includes demo\rosetta\AVL_tree.exw, which contains a slightly longer but perhaps more readable version, with a command line equivalent of https://www.cs.usfca.edu/~galles/visualization/AVLtree.html as well as a simple tree structure display routine and additional verification code (both modelled on the C version found on this page) <lang Phix>enum KEY = 0,

    LEFT,
    HEIGHT,    -- (NB +/-1 gives LEFT or RIGHT)
    RIGHT

sequence tree = {} integer freelist = 0

function newNode(object key) integer node

   if freelist=0 then
       node = length(tree)+1
       tree &= {key,NULL,1,NULL}
   else
       node = freelist
       freelist = tree[freelist]
       tree[node+KEY..node+RIGHT] = {key,NULL,1,NULL}
   end if
   return node

end function

function height(integer node)

   return iff(node=NULL?0:tree[node+HEIGHT])

end function

procedure setHeight(integer node)

   tree[node+HEIGHT] = max(height(tree[node+LEFT]), height(tree[node+RIGHT]))+1

end procedure

function rotate(integer node, integer direction) integer idirection = LEFT+RIGHT-direction integer pivot = tree[node+idirection]

   {tree[pivot+direction],tree[node+idirection]} = {node,tree[pivot+direction]}
   setHeight(node)
   setHeight(pivot)
   return pivot

end function

function getBalance(integer N)

   return iff(N==NULL ? 0 : height(tree[N+LEFT])-height(tree[N+RIGHT]))

end function

function insertNode(integer node, object key)

   if node==NULL then
       return newNode(key)
   end if
   integer c = compare(key,tree[node+KEY])
   if c!=0 then
       integer direction = HEIGHT+c    -- LEFT or RIGHT
       tree[node+direction] = insertNode(tree[node+direction], key)
       setHeight(node)
       integer balance = trunc(getBalance(node)/2) -- +/-1 (or 0)
       if balance then
           direction = HEIGHT-balance  -- LEFT or RIGHT
           c = compare(key,tree[tree[node+direction]+KEY])
           if c=balance then
               tree[node+direction] = rotate(tree[node+direction],direction)
           end if
           if c!=0 then
               node = rotate(node,LEFT+RIGHT-direction)
           end if
       end if
   end if
   return node

end function

function minValueNode(integer node)

   while 1 do
       integer next = tree[node+LEFT]
       if next=NULL then exit end if
       node = next
   end while
   return node

end function

function deleteNode(integer root, object key) integer c

   if root=NULL then return root end if
   c = compare(key,tree[root+KEY])
   if c=-1 then
       tree[root+LEFT] = deleteNode(tree[root+LEFT], key)
   elsif c=+1 then
       tree[root+RIGHT] = deleteNode(tree[root+RIGHT], key)
   elsif tree[root+LEFT]==NULL
      or tree[root+RIGHT]==NULL then
       integer temp = iff(tree[root+LEFT] ? tree[root+LEFT] : tree[root+RIGHT])
       if temp==NULL then  -- No child case
           {temp,root} = {root,NULL}
       else                -- One child case
           tree[root+KEY..root+RIGHT] = tree[temp+KEY..temp+RIGHT]
       end if
       tree[temp+KEY] = freelist
       freelist = temp
   else                    -- Two child case
       integer temp = minValueNode(tree[root+RIGHT])
       tree[root+KEY] = tree[temp+KEY]
       tree[root+RIGHT] = deleteNode(tree[root+RIGHT], tree[temp+KEY])
   end if
   if root=NULL then return root end if
   setHeight(root)
   integer balance = trunc(getBalance(root)/2)
   if balance then
       integer direction = HEIGHT-balance
       c = compare(getBalance(tree[root+direction]),0)
       if c=-balance then
           tree[root+direction] = rotate(tree[root+direction],direction)
       end if
       root = rotate(root,LEFT+RIGHT-direction)
   end if
   return root

end function

procedure inOrder(integer node)

   if node!=NULL then
       inOrder(tree[node+LEFT])
       printf(1, "%d ", tree[node+KEY])
       inOrder(tree[node+RIGHT])
   end if

end procedure

integer root = NULL sequence test = shuffle(tagset(50003))

   for i=1 to length(test) do
       root = insertNode(root,test[i])
   end for
   test = shuffle(tagset(50000))
   for i=1 to length(test) do
       root = deleteNode(root,test[i])
   end for
   inOrder(root)</lang>

Output:

50001 50002 50003

Python

<lang python> """

Python AVL tree example based on

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lec06_code.zip

Simplified for Rosetta Code example.

See also:

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/MIT6_006F11_lec06_orig.pdf

https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-6-avl-trees-avl-sort/

"""

class AVLNode(object):

   """A node in the AVL tree."""
   
   def __init__(self, parent, k):
       """Creates a node.
       
       Args:
           parent: The node's parent.
           k: key of the node.
       """
       self.key = k
       self.parent = parent
       self.left = None
       self.right = None
 
   def _str(self):
       """Internal method for ASCII art."""
       label = str(self.key)
       if self.left is None:
           left_lines, left_pos, left_width = [], 0, 0
       else:
           left_lines, left_pos, left_width = self.left._str()
       if self.right is None:
           right_lines, right_pos, right_width = [], 0, 0
       else:
           right_lines, right_pos, right_width = self.right._str()
       middle = max(right_pos + left_width - left_pos + 1, len(label), 2)
       pos = left_pos + middle // 2
       width = left_pos + middle + right_width - right_pos
       while len(left_lines) < len(right_lines):
           left_lines.append(' ' * left_width)
       while len(right_lines) < len(left_lines):
           right_lines.append(' ' * right_width)
       if (middle - len(label)) % 2 == 1 and self.parent is not None and \
          self is self.parent.left and len(label) < middle:
           label += '.'
       label = label.center(middle, '.')
       if label[0] == '.': label = ' ' + label[1:]
       if label[-1] == '.': label = label[:-1] + ' '
       lines = [' ' * left_pos + label + ' ' * (right_width - right_pos),
                ' ' * left_pos + '/' + ' ' * (middle-2) +
                '\\' + ' ' * (right_width - right_pos)] + \
         [left_line + ' ' * (width - left_width - right_width) + right_line
          for left_line, right_line in zip(left_lines, right_lines)]
       return lines, pos, width
       
   def __str__(self):
       return '\n'.join(self._str()[0])

   def find(self, k):
       """Finds and returns the node with key k from the subtree rooted at this 
       node.
       
       Args:
           k: The key of the node we want to find.
       
       Returns:
           The node with key k.
       """
       if k == self.key:
           return self
       elif k < self.key:
           if self.left is None:
               return None
           else:
               return self.left.find(k)
       else:
           if self.right is None:  
               return None
           else:
               return self.right.find(k)
   
   def find_min(self):
       """Finds the node with the minimum key in the subtree rooted at this 
       node.
       
       Returns:
           The node with the minimum key.
       """
       current = self
       while current.left is not None:
           current = current.left
       return current
      
   def next_larger(self):
       """Returns the node with the next larger key (the successor) in the BST.
       """
       if self.right is not None:
           return self.right.find_min()
       current = self
       while current.parent is not None and current is current.parent.right:
           current = current.parent
       return current.parent

   def insert(self, node):
       """Inserts a node into the subtree rooted at this node.
       
       Args:
           node: The node to be inserted.
       """
       if node is None:
           return
       if node.key < self.key:
           if self.left is None:
               node.parent = self
               self.left = node
           else:
               self.left.insert(node)
       else:
           if self.right is None:
               node.parent = self
               self.right = node
           else:
               self.right.insert(node)
 
   def delete(self):
       """Deletes and returns this node from the tree."""
       if self.left is None or self.right is None:
           if self is self.parent.left:
               self.parent.left = self.left or self.right
               if self.parent.left is not None:
                   self.parent.left.parent = self.parent
           else:
               self.parent.right = self.left or self.right
               if self.parent.right is not None:
                   self.parent.right.parent = self.parent
           return self
       else:
           s = self.next_larger()
           self.key, s.key = s.key, self.key
           return s.delete()

def height(node):

   if node is None:
       return -1
   else:
       return node.height

def update_height(node):

   node.height = max(height(node.left), height(node.right)) + 1

class AVL(object):

   """
   AVL binary search tree implementation.
   """
   
   def __init__(self):
       """ empty tree """
       self.root = None
   
   def __str__(self):
       if self.root is None: return '<empty tree>'
       return str(self.root)

   def find(self, k):
       """Finds and returns the node with key k from the subtree rooted at this 
       node.
       
       Args:
           k: The key of the node we want to find.
       
       Returns:
           The node with key k or None if the tree is empty.
       """
       return self.root and self.root.find(k)
               
   def find_min(self):
       """Returns the minimum node of this BST."""
       
       return self.root and self.root.find_min()
   
   def next_larger(self, k):
       """Returns the node that contains the next larger (the successor) key in
       the BST in relation to the node with key k.
       
       Args:
           k: The key of the node of which the successor is to be found.
           
       Returns:
           The successor node.
       """
       node = self.find(k)
       return node and node.next_larger()   

   def left_rotate(self, x):
       y = x.right
       y.parent = x.parent
       if y.parent is None:
           self.root = y
       else:
           if y.parent.left is x:
               y.parent.left = y
           elif y.parent.right is x:
               y.parent.right = y
       x.right = y.left
       if x.right is not None:
           x.right.parent = x
       y.left = x
       x.parent = y
       update_height(x)
       update_height(y)

   def right_rotate(self, x):
       y = x.left
       y.parent = x.parent
       if y.parent is None:
           self.root = y
       else:
           if y.parent.left is x:
               y.parent.left = y
           elif y.parent.right is x:
               y.parent.right = y
       x.left = y.right
       if x.left is not None:
           x.left.parent = x
       y.right = x
       x.parent = y
       update_height(x)
       update_height(y)

   def rebalance(self, node):
       while node is not None:
           update_height(node)
           if height(node.left) >= 2 + height(node.right):
               if height(node.left.left) >= height(node.left.right):
                   self.right_rotate(node)
               else:
                   self.left_rotate(node.left)
                   self.right_rotate(node)
           elif height(node.right) >= 2 + height(node.left):
               if height(node.right.right) >= height(node.right.left):
                   self.left_rotate(node)
               else:
                   self.right_rotate(node.right)
                   self.left_rotate(node)
           node = node.parent

   def insert(self, k):
       """Inserts a node with key k into the subtree rooted at this node.
       This AVL version guarantees the balance property: h = O(lg n).
       
       Args:
           k: The key of the node to be inserted.
       """
       node = AVLNode(None, k)
       if self.root is None:
           # The root's parent is None.
           self.root = node
       else:
           self.root.insert(node)
       self.rebalance(node)

   def delete(self, k):
       """Deletes and returns a node with key k if it exists from the BST.
       This AVL version guarantees the balance property: h = O(lg n).
       
       Args:
           k: The key of the node that we want to delete.
           
       Returns:
           The deleted node with key k.
       """
       node = self.find(k)
       if node is None:
           return None
       if node is self.root:
           pseudoroot = AVLNode(None, 0)
           pseudoroot.left = self.root
           self.root.parent = pseudoroot
           deleted = self.root.delete()
           self.root = pseudoroot.left
           if self.root is not None:
               self.root.parent = None
       else:
           deleted = node.delete()   
       ## node.parent is actually the old parent of the node,
       ## which is the first potentially out-of-balance node.
       self.rebalance(deleted.parent)

def test(args=None):

   import random, sys
   if not args:
       args = sys.argv[1:]
   if not args:
       print('usage: %s <number-of-random-items | item item item ...>' % \
             sys.argv[0])
       sys.exit()
   elif len(args) == 1:
       items = (random.randrange(100) for i in range(int(args[0])))
   else:
       items = [int(i) for i in args]

   tree = AVL()
   print(tree)
   for item in items:
       tree.insert(item)
       print()
       print(tree)

if __name__ == '__main__': test() </lang>

Output:

python avlrc.py 1 2 3 4 5 6 7 8 9 10

... only showing last tree ...

   ..4...
  /      \
  2      .8.
 / \    /   \
1  3    6   9
/\ /\  / \  /\
      5  7   10
      /\ /\  /\

Raku

(formerly Perl 6) This code has been translated from the Java version on <https://rosettacode.org>. Consequently, it should have the same license: GNU Free Document License 1.2. In addition to the translated code, other public methods have been added as shown by the asterisks in the following list of all public methods:

• insert node
• delete node
• show all node keys
• show all node balances
• *delete nodes by a list of node keys
• *find and return node objects by key
• *attach data per node
• *return list of all node keys
• *return list of all node objects

Note one of the interesting features of Raku is the ability to use characters like the apostrophe (') and hyphen (-) in identifiers.
<lang perl6> class AVL-Tree {

   has $.root is rw = 0;

   class Node {
       has $.key    is rw = ;
       has $.parent is rw = 0;
       has $.data   is rw = 0;
       has $.left   is rw = 0;
       has $.right  is rw = 0;
       has Int $.balance is rw = 0;
       has Int $.height  is rw = 0;
   }

   #=====================================================
   # public methods
   #=====================================================

   #| returns a node object or 0 if not found
   method find($key) {
       return 0 if !$.root;
       self!find: $key, $.root;
   }

   #| returns a list of tree keys
   method keys() {
       return () if !$.root;
       my @list;
       self!keys: $.root, @list;
       @list;
   }

   #| returns a list of tree nodes
   method nodes() {
       return () if !$.root;
       my @list;
       self!nodes: $.root, @list;
       @list;
   }

   #| insert a node key, optionally add data (the `parent` arg is for
   #| internal use only)
   method insert($key, :$data = 0, :$parent = 0,) {
       return $.root = Node.new: :$key, :$parent, :$data if !$.root;
       my $n = $.root;
       while True {
           return False if $n.key eq $key;
           my $parent = $n;
           my $goLeft = $n.key > $key;
           $n = $goLeft ?? $n.left !! $n.right;
           if !$n {
               if $goLeft {
                   $parent.left = Node.new: :$key, :$parent, :$data;
               }
               else {
                   $parent.right = Node.new: :$key, :$parent, :$data;
               }
               self!rebalance: $parent;
               last
           }
       }
       True
   }

   #| delete one or more nodes by key
   method delete(*@del-key) {
       return if !$.root;
       for @del-key -> $del-key {
           my $child = $.root;
           while $child {
               my $node = $child;
               $child = $del-key >= $node.key ?? $node.right !! $node.left;
               if $del-key eq $node.key {
                   self!delete: $node;
                   next;
               }
           }
       }
   }

   #| show a list of all nodes by key
   method show-keys {
       self!show-keys: $.root;
       say()
   }

   #| show a list of all nodes' balances (not normally needed)
   method show-balances {
       self!show-balances: $.root;
       say()
   }

   #=====================================================
   # private methods
   #=====================================================

   method !delete($node) {
       if !$node.left && !$node.right {
           if !$node.parent {
               $.root = 0;
           }
           else {
               my $parent = $node.parent;
               if $parent.left === $node {
                   $parent.left = 0;
               }
               else {
                   $parent.right = 0;
               }
               self!rebalance: $parent;
           }
           return
       }

       if $node.left {
           my $child = $node.left;
           while $child.right {
               $child = $child.right;
           }
           $node.key = $child.key;
           self!delete: $child;
       }
       else {
           my $child = $node.right;
           while $child.left {
               $child = $child.left;
           }
           $node.key = $child.key;
           self!delete: $child;
       }
   }

   method !rebalance($n is copy) {
       self!set-balance: $n;

       if $n.balance == -2 {
           if self!height($n.left.left) >= self!height($n.left.right) {
               $n = self!rotate-right: $n;
           }
           else {
               $n = self!rotate-left'right: $n;
           }
       }
       elsif $n.balance == 2 {
           if self!height($n.right.right) >= self!height($n.right.left) {
               $n = self!rotate-left: $n;
           }
           else {
               $n = self!rotate-right'left: $n;
           }
       }

       if $n.parent {
           self!rebalance: $n.parent;
       }
       else {
           $.root = $n;
       }
   }

   method !rotate-left($a) {

       my $b     = $a.right;
       $b.parent = $a.parent;

       $a.right = $b.left;

       if $a.right {
           $a.right.parent = $a;
       }

       $b.left   = $a;
       $a.parent = $b;

       if $b.parent {
           if $b.parent.right === $a {
               $b.parent.right = $b;
           }
           else {
               $b.parent.left = $b;
           }
       }

       self!set-balance: $a, $b;
       $b;
   }

   method !rotate-right($a) {

       my $b = $a.left;
       $b.parent = $a.parent;

       $a.left = $b.right;

       if $a.left {
           $a.left.parent = $a;
       }

       $b.right  = $a;
       $a.parent = $b;

       if $b.parent {
           if $b.parent.right === $a {
               $b.parent.right = $b;
           }
           else {
               $b.parent.left = $b;
           }
       }

       self!set-balance: $a, $b;

       $b;
   }

   method !rotate-left'right($n) {
       $n.left = self!rotate-left: $n.left;
       self!rotate-right: $n;
   }

   method !rotate-right'left($n) {
       $n.right = self!rotate-right: $n.right;
       self!rotate-left: $n;
   }

   method !height($n) {
       $n ?? $n.height !! -1;
   }

   method !set-balance(*@n) {
       for @n -> $n {
           self!reheight: $n;
           $n.balance = self!height($n.right) - self!height($n.left);
       }
   }

   method !show-balances($n) {
       if $n {
           self!show-balances: $n.left;
           printf "%s ", $n.balance;
           self!show-balances: $n.right;
       }
   }

   method !reheight($node) {
       if $node {
           $node.height = 1 + max self!height($node.left), self!height($node.right);
       }
   }

   method !show-keys($n) {
       if $n {
           self!show-keys: $n.left;
           printf "%s ", $n.key;
           self!show-keys: $n.right;
       }
   }

   method !nodes($n, @list) {
       if $n {
           self!nodes: $n.left, @list;
           @list.push: $n if $n;
           self!nodes: $n.right, @list;
       }
   }

   method !keys($n, @list) {
       if $n {
           self!keys: $n.left, @list;
           @list.push: $n.key if $n;
           self!keys: $n.right, @list;
       }
   }

   method !find($key, $n) {
       if $n {
           self!find: $key, $n.left;
           return $n if $n.key eq $key;
           self!find: $key, $n.right;
       }
   }

} </lang>

Rust

See AVL tree/Rust.

Scala

<lang scala>import scala.collection.mutable

class AVLTree[A](implicit val ordering: Ordering[A]) extends mutable.SortedSet[A] {

 if (ordering eq null) throw new NullPointerException("ordering must not be null")

 private var _root: AVLNode = _
 private var _size = 0

 override def size: Int = _size

 override def foreach[U](f: A => U): Unit = {
   val stack = mutable.Stack[AVLNode]()
   var current = root
   var done = false

   while (!done) {
     if (current != null) {
       stack.push(current)
       current = current.left
     } else if (stack.nonEmpty) {
       current = stack.pop()
       f.apply(current.key)

       current = current.right
     } else {
       done = true
     }
   }
 }

 def root: AVLNode = _root

 override def isEmpty: Boolean = root == null

 override def min[B >: A](implicit cmp: Ordering[B]): A = minNode().key

 def minNode(): AVLNode = {
   if (root == null) throw new UnsupportedOperationException("empty tree")
   var node = root
   while (node.left != null) node = node.left
   node
 }

 override def max[B >: A](implicit cmp: Ordering[B]): A = maxNode().key

 def maxNode(): AVLNode = {
   if (root == null) throw new UnsupportedOperationException("empty tree")
   var node = root
   while (node.right != null) node = node.right
   node
 }

 def next(node: AVLNode): Option[AVLNode] = {
   var successor = node
   if (successor != null) {
     if (successor.right != null) {
       successor = successor.right
       while (successor != null && successor.left != null) {
         successor = successor.left
       }
     } else {
       successor = node.parent
       var n = node
       while (successor != null && successor.right == n) {
         n = successor
         successor = successor.parent
       }
     }
   }
   Option(successor)
 }

 def prev(node: AVLNode): Option[AVLNode] = {
   var predecessor = node
   if (predecessor != null) {
     if (predecessor.left != null) {
       predecessor = predecessor.left
       while (predecessor != null && predecessor.right != null) {
         predecessor = predecessor.right
       }
     } else {
       predecessor = node.parent
       var n = node
       while (predecessor != null && predecessor.left == n) {
         n = predecessor
         predecessor = predecessor.parent
       }
     }
   }
   Option(predecessor)
 }

 override def rangeImpl(from: Option[A], until: Option[A]): mutable.SortedSet[A] = ???

 override def +=(key: A): AVLTree.this.type = {
   insert(key)
   this
 }

 def insert(key: A): AVLNode = {
   if (root == null) {
     _root = new AVLNode(key)
     _size += 1
     return root
   }

   var node = root
   var parent: AVLNode = null
   var cmp = 0

   while (node != null) {
     parent = node
     cmp = ordering.compare(key, node.key)
     if (cmp == 0) return node // duplicate
     node = node.matchNextChild(cmp)
   }

   val newNode = new AVLNode(key, parent)
   if (cmp <= 0) parent._left = newNode
   else parent._right = newNode

   while (parent != null) {
     cmp = ordering.compare(parent.key, key)
     if (cmp < 0) parent.balanceFactor -= 1
     else parent.balanceFactor += 1

     parent = parent.balanceFactor match {
       case -1 | 1 => parent.parent
       case x if x < -1 =>
         if (parent.right.balanceFactor == 1) rotateRight(parent.right)
         val newRoot = rotateLeft(parent)
         if (parent == root) _root = newRoot
         null
       case x if x > 1 =>
         if (parent.left.balanceFactor == -1) rotateLeft(parent.left)
         val newRoot = rotateRight(parent)
         if (parent == root) _root = newRoot
         null
       case _ => null
     }
   }

   _size += 1
   newNode
 }

 override def -=(key: A): AVLTree.this.type = {
   remove(key)
   this
 }

 override def remove(key: A): Boolean = {
   var node = findNode(key).orNull
   if (node == null) return false

   if (node.left != null) {
     var max = node.left

     while (max.left != null || max.right != null) {
       while (max.right != null) max = max.right

       node._key = max.key
       if (max.left != null) {
         node = max
         max = max.left
       }
     }
     node._key = max.key
     node = max
   }

   if (node.right != null) {
     var min = node.right

     while (min.left != null || min.right != null) {
       while (min.left != null) min = min.left

       node._key = min.key
       if (min.right != null) {
         node = min
         min = min.right
       }
     }
     node._key = min.key
     node = min
   }

   var current = node
   var parent = node.parent
   while (parent != null) {
     parent.balanceFactor += (if (parent.left == current) -1 else 1)

     current = parent.balanceFactor match {
       case x if x < -1 =>
         if (parent.right.balanceFactor == 1) rotateRight(parent.right)
         val newRoot = rotateLeft(parent)
         if (parent == root) _root = newRoot
         newRoot
       case x if x > 1 =>
         if (parent.left.balanceFactor == -1) rotateLeft(parent.left)
         val newRoot = rotateRight(parent)
         if (parent == root) _root = newRoot
         newRoot
       case _ => parent
     }

     parent = current.balanceFactor match {
       case -1 | 1 => null
       case _ => current.parent
     }
   }

   if (node.parent != null) {
     if (node.parent.left == node) {
       node.parent._left = null
     } else {
       node.parent._right = null
     }
   }

   if (node == root) _root = null

   _size -= 1
   true
 }

 def findNode(key: A): Option[AVLNode] = {
   var node = root
   while (node != null) {
     val cmp = ordering.compare(key, node.key)
     if (cmp == 0) return Some(node)
     node = node.matchNextChild(cmp)
   }
   None
 }

 private def rotateLeft(node: AVLNode): AVLNode = {
   val rightNode = node.right
   node._right = rightNode.left
   if (node.right != null) node.right._parent = node

   rightNode._parent = node.parent
   if (rightNode.parent != null) {
     if (rightNode.parent.left == node) {
       rightNode.parent._left = rightNode
     } else {
       rightNode.parent._right = rightNode
     }
   }

   node._parent = rightNode
   rightNode._left = node

   node.balanceFactor += 1
   if (rightNode.balanceFactor < 0) {
     node.balanceFactor -= rightNode.balanceFactor
   }

   rightNode.balanceFactor += 1
   if (node.balanceFactor > 0) {
     rightNode.balanceFactor += node.balanceFactor
   }
   rightNode
 }

 private def rotateRight(node: AVLNode): AVLNode = {
   val leftNode = node.left
   node._left = leftNode.right
   if (node.left != null) node.left._parent = node

   leftNode._parent = node.parent
   if (leftNode.parent != null) {
     if (leftNode.parent.left == node) {
       leftNode.parent._left = leftNode
     } else {
       leftNode.parent._right = leftNode
     }
   }

   node._parent = leftNode
   leftNode._right = node

   node.balanceFactor -= 1
   if (leftNode.balanceFactor > 0) {
     node.balanceFactor -= leftNode.balanceFactor
   }

   leftNode.balanceFactor -= 1
   if (node.balanceFactor < 0) {
     leftNode.balanceFactor += node.balanceFactor
   }
   leftNode
 }

 override def contains(elem: A): Boolean = findNode(elem).isDefined

 override def iterator: Iterator[A] = ???

 override def keysIteratorFrom(start: A): Iterator[A] = ???

 class AVLNode private[AVLTree](k: A, p: AVLNode = null) {

   private[AVLTree] var _key: A = k
   private[AVLTree] var _parent: AVLNode = p
   private[AVLTree] var _left: AVLNode = _
   private[AVLTree] var _right: AVLNode = _
   private[AVLTree] var balanceFactor: Int = 0

   def parent: AVLNode = _parent

   private[AVLTree] def selectNextChild(key: A): AVLNode = matchNextChild(ordering.compare(key, this.key))

   def key: A = _key

   private[AVLTree] def matchNextChild(cmp: Int): AVLNode = cmp match {
     case x if x < 0 => left
     case x if x > 0 => right
     case _ => null
   }

   def left: AVLNode = _left

   def right: AVLNode = _right
 }

}</lang>

Sidef

Translation of: D

<lang ruby>class AVLtree {

   has root = nil

   struct Node {
       Number key,
       Number balance = 0,
       Node left = nil,
       Node right = nil,
       Node parent = nil,
   }

   method insert(key) {
       if (root == nil) {
           root = Node(key)
           return true
       }

       var n = root
       var parent = nil

       loop {
           if (n.key == key) {
               return false
           }
           parent = n
           var goLeft = (n.key > key)
           n = (goLeft ? n.left : n.right)

           if (n == nil) {
               var tn = Node(key, parent: parent)
               if (goLeft) {
                   parent.left = tn
               }
               else {
                   parent.right = tn
               }
               self.rebalance(parent)
               break
           }
       }

       return true
   }

   method delete_key(delKey) {
       if (root == nil) { return nil }

       var n = root
       var parent = root
       var delNode = nil
       var child = root

       while (child != nil) {
           parent = n
           n = child
           child = (delKey >= n.key ? n.right : n.left)
           if (delKey == n.key) {
               delNode = n
           }
       }

       if (delNode != nil) {
           delNode.key = n.key
           child = (n.left != nil ? n.left : n.right)

           if (root.key == delKey) {
               root = child
           }
           else {
               if (parent.left == n) {
                   parent.left = child
               }
               else {
                   parent.right = child
               }
               self.rebalance(parent)
           }
       }
   }

   method rebalance(n) {
       if (n == nil) { return nil }
       self.setBalance(n)

       given (n.balance) {
           when (-2) {
               if (self.height(n.left.left) >= self.height(n.left.right)) {
                   n = self.rotate(n, :right)
               }
               else {
                   n = self.rotate_twice(n, :left, :right)
               }
           }
           when (2) {
               if (self.height(n.right.right) >= self.height(n.right.left)) {
                   n = self.rotate(n, :left)
               }
               else {
                   n = self.rotate_twice(n, :right, :left)
               }
           }
       }

       if (n.parent != nil) {
           self.rebalance(n.parent)
       }
       else {
           root = n
       }
   }

   method rotate(a, dir) {
       var b = (dir == :left ? a.right : a.left)
       b.parent = a.parent

       (dir == :left) ? (a.right = b.left)
                      : (a.left  = b.right)

       if (a.right != nil) {
           a.right.parent = a
       }

       b.$dir = a
       a.parent = b

       if (b.parent != nil) {
           if (b.parent.right == a) {
               b.parent.right = b
           }
           else {
               b.parent.left = b
           }
       }

       self.setBalance(a, b)
       return b
   }

   method rotate_twice(n, dir1, dir2) {
       n.left = self.rotate(n.left, dir1)
       self.rotate(n, dir2)
   }

   method height(n) {
       if (n == nil) { return -1 }
       1 + Math.max(self.height(n.left), self.height(n.right))
   }

   method setBalance(*nodes) {
       nodes.each { |n|
           n.balance = (self.height(n.right) - self.height(n.left))
       }
   }

   method printBalance {
       self.printBalance(root)
   }

   method printBalance(n) {
       if (n != nil) {
           self.printBalance(n.left)
           print(n.balance, ' ')
           self.printBalance(n.right)
       }
   }

}

var tree = AVLtree()

say "Inserting values 1 to 10"

print "Printing balance: " tree.printBalance</lang>

Output:

Inserting values 1 to 10
Printing balance: 0 0 0 1 0 0 0 0 1 0

Simula

<lang simula>CLASS AVL; BEGIN

AVL TREE ADAPTED FROM JULIENNE WALKER'S PRESENTATION AT ;	HTTP://ETERNALLYCONFUZZLED.COM/TUTS/DATASTRUCTURES/JSW_TUT_AVL.ASPX. ;	THIS PORT USES SIMILAR INDENTIFIER NAMES. ;	THE KEY INTERFACE MUST BE SUPPORTED BY DATA STORED IN THE AVL TREE. ; CLASS KEY; VIRTUAL: PROCEDURE LESS IS BOOLEAN PROCEDURE LESS (K); REF(KEY) K;; PROCEDURE EQUAL IS BOOLEAN PROCEDURE EQUAL(K); REF(KEY) K;; BEGIN END KEY;	NODE IS A NODE IN AN AVL TREE. ; CLASS NODE(DATA); REF(KEY) DATA;  ! ANYTHING COMPARABLE WITH LESS AND EQUAL. ; BEGIN INTEGER BALANCE;  ! BALANCE FACTOR ; REF(NODE) ARRAY LINK(0:1);  ! CHILDREN, INDEXED BY "DIRECTION", 0 OR 1. ; END NODE;	A LITTLE READABILITY FUNCTION FOR RETURNING THE OPPOSITE OF A DIRECTION, ;	WHERE A DIRECTION IS 0 OR 1. ;	WHERE JW WRITES !DIR, THIS CODE HAS OPP(DIR). ; INTEGER PROCEDURE OPP(DIR); INTEGER DIR; BEGIN OPP := 1 - DIR; END OPP;	SINGLE ROTATION ; REF(NODE) PROCEDURE SINGLE(ROOT, DIR); REF(NODE) ROOT; INTEGER DIR; BEGIN REF(NODE) SAVE; SAVE :- ROOT.LINK(OPP(DIR)); ROOT.LINK(OPP(DIR)) :- SAVE.LINK(DIR); SAVE.LINK(DIR) :- ROOT; SINGLE :- SAVE; END SINGLE;	DOUBLE ROTATION ; REF(NODE) PROCEDURE DOUBLE(ROOT, DIR); REF(NODE) ROOT; INTEGER DIR; BEGIN REF(NODE) SAVE; SAVE :- ROOT.LINK(OPP(DIR)).LINK(DIR); ROOT.LINK(OPP(DIR)).LINK(DIR) :- SAVE.LINK(OPP(DIR)); SAVE.LINK(OPP(DIR)) :- ROOT.LINK(OPP(DIR)); ROOT.LINK(OPP(DIR)) :- SAVE; SAVE :- ROOT.LINK(OPP(DIR)); ROOT.LINK(OPP(DIR)) :- SAVE.LINK(DIR); SAVE.LINK(DIR) :- ROOT; DOUBLE :- SAVE; END DOUBLE;	ADJUST BALANCE FACTORS AFTER DOUBLE ROTATION ; PROCEDURE ADJUSTBALANCE(ROOT, DIR, BAL); REF(NODE) ROOT; INTEGER DIR, BAL; BEGIN REF(NODE) N, NN; N :- ROOT.LINK(DIR); NN :- N.LINK(OPP(DIR)); IF NN.BALANCE = 0 THEN BEGIN ROOT.BALANCE := 0; N.BALANCE := 0; END ELSE IF NN.BALANCE = BAL THEN BEGIN ROOT.BALANCE := -BAL; N.BALANCE := 0; END ELSE BEGIN ROOT.BALANCE := 0; N.BALANCE := BAL; END; NN.BALANCE := 0; END ADJUSTBALANCE; REF(NODE) PROCEDURE INSERTBALANCE(ROOT, DIR); REF(NODE) ROOT; INTEGER DIR; BEGIN REF(NODE) N; INTEGER BAL; N :- ROOT.LINK(DIR); BAL := 2*DIR - 1; IF N.BALANCE = BAL THEN BEGIN ROOT.BALANCE := 0; N.BALANCE := 0; INSERTBALANCE :- SINGLE(ROOT, OPP(DIR)); END ELSE BEGIN ADJUSTBALANCE(ROOT, DIR, BAL); INSERTBALANCE :- DOUBLE(ROOT, OPP(DIR)); END; END INSERTBALANCE; CLASS TUPLE(N,B); REF(NODE) N; BOOLEAN B;; REF(TUPLE) PROCEDURE INSERTR(ROOT, DATA); REF(NODE) ROOT; REF(KEY) DATA; BEGIN IF ROOT == NONE THEN INSERTR :- NEW TUPLE(NEW NODE(DATA), FALSE) ELSE BEGIN REF(TUPLE) T; BOOLEAN DONE; INTEGER DIR; DIR := 0; IF ROOT.DATA.LESS(DATA) THEN DIR := 1; T :- INSERTR(ROOT.LINK(DIR), DATA); ROOT.LINK(DIR) :- T.N; DONE := T.B; IF DONE THEN INSERTR :- NEW TUPLE(ROOT, TRUE) ELSE BEGIN ROOT.BALANCE := ROOT.BALANCE + 2*DIR - 1; IF ROOT.BALANCE = 0 THEN INSERTR :- NEW TUPLE(ROOT, TRUE) ELSE IF ROOT.BALANCE = 1 OR ROOT.BALANCE = -1 THEN INSERTR :- NEW TUPLE(ROOT, FALSE) ELSE INSERTR :- NEW TUPLE(INSERTBALANCE(ROOT, DIR), TRUE); END; END; END INSERTR;	INSERT A NODE INTO THE AVL TREE. ;	DATA IS INSERTED EVEN IF OTHER DATA WITH THE SAME KEY ALREADY EXISTS. ; PROCEDURE INSERT(TREE, DATA); NAME TREE; REF(NODE) TREE; REF(KEY) DATA; BEGIN REF(TUPLE) T; T :- INSERTR(TREE, DATA); TREE :- T.N; END INSERT; REF(TUPLE) PROCEDURE REMOVEBALANCE(ROOT, DIR); REF(NODE) ROOT; INTEGER DIR; BEGIN REF(NODE) N; INTEGER BAL; N :- ROOT.LINK(OPP(DIR)); BAL := 2*DIR - 1; IF N.BALANCE = -BAL THEN BEGIN ROOT.BALANCE := 0; N.BALANCE := 0; REMOVEBALANCE :- NEW TUPLE(SINGLE(ROOT, DIR), FALSE); END ELSE IF N.BALANCE = BAL THEN BEGIN ADJUSTBALANCE(ROOT, OPP(DIR), -BAL); REMOVEBALANCE :- NEW TUPLE(DOUBLE(ROOT, DIR), FALSE); END ELSE BEGIN ROOT.BALANCE := -BAL; N.BALANCE := BAL; REMOVEBALANCE :- NEW TUPLE(SINGLE(ROOT, DIR), TRUE); END END REMOVEBALANCE; REF(TUPLE) PROCEDURE REMOVER(ROOT, DATA); REF(NODE) ROOT; REF(KEY) DATA; BEGIN INTEGER DIR; BOOLEAN DONE; REF(TUPLE) T; IF ROOT == NONE THEN REMOVER :- NEW TUPLE(NONE, FALSE) ELSE IF ROOT.DATA.EQUAL(DATA) THEN BEGIN IF ROOT.LINK(0) == NONE THEN BEGIN REMOVER :- NEW TUPLE(ROOT.LINK(1), FALSE); GOTO L; END ELSE IF ROOT.LINK(1) == NONE THEN BEGIN REMOVER :- NEW TUPLE(ROOT.LINK(0), FALSE); GOTO L; END ELSE BEGIN REF(NODE) HEIR; HEIR :- ROOT.LINK(0); WHILE HEIR.LINK(1) =/= NONE DO HEIR :- HEIR.LINK(1); ROOT.DATA :- HEIR.DATA; DATA :- HEIR.DATA; END; END; DIR := 0; IF ROOT.DATA.LESS(DATA) THEN DIR := 1; T :- REMOVER(ROOT.LINK(DIR), DATA); ROOT.LINK(DIR) :- T.N; DONE := T.B; IF DONE THEN BEGIN REMOVER :- NEW TUPLE(ROOT, TRUE); GOTO L; END; ROOT.BALANCE := ROOT.BALANCE + 1 - 2*DIR; IF ROOT.BALANCE = 1 OR ROOT.BALANCE = -1 THEN REMOVER :- NEW TUPLE(ROOT, TRUE) ELSE IF ROOT.BALANCE = 0 THEN REMOVER :- NEW TUPLE(ROOT, FALSE) ELSE REMOVER :- REMOVEBALANCE(ROOT, DIR); L: END REMOVER;	REMOVE A SINGLE ITEM FROM AN AVL TREE. ;	IF KEY DOES NOT EXIST, FUNCTION HAS NO EFFECT. ; PROCEDURE REMOVE(TREE, DATA); NAME TREE; REF(NODE) TREE; REF(KEY) DATA; BEGIN REF(TUPLE) T; T :- REMOVER(TREE, DATA); TREE :- T.N; END REMOVEM; END.</lang> A demonstration program: <lang simula>EXTERNAL CLASS AVL; AVL BEGIN KEY CLASS INTEGERKEY(I); INTEGER I; BEGIN BOOLEAN PROCEDURE LESS (K); REF(KEY) K; LESS  := I < K QUA INTEGERKEY.I; BOOLEAN PROCEDURE EQUAL(K); REF(KEY) K; EQUAL := I = K QUA INTEGERKEY.I; END INTEGERKEY; PROCEDURE DUMP(ROOT); REF(NODE) ROOT; BEGIN IF ROOT =/= NONE THEN BEGIN DUMP(ROOT.LINK(0)); OUTINT(ROOT.DATA QUA INTEGERKEY.I, 0); OUTTEXT(" "); DUMP(ROOT.LINK(1)); END END DUMP; INTEGER I; REF(NODE) TREE; OUTTEXT("Empty tree: "); DUMP(TREE); OUTIMAGE; FOR I := 3, 1, 4, 1, 5 DO BEGIN OUTTEXT("Insert "); OUTINT(I, 0); OUTTEXT(": "); INSERT(TREE, NEW INTEGERKEY(I)); DUMP(TREE); OUTIMAGE; END; FOR I := 3, 1 DO BEGIN OUTTEXT("Remove "); OUTINT(I, 0); OUTTEXT(": "); REMOVE(TREE, NEW INTEGERKEY(I)); DUMP(TREE); OUTIMAGE; END; END.</lang> Output: Empty tree: Insert 3: 3 Insert 1: 1 3 Insert 4: 1 3 4 Insert 1: 1 1 3 4 Insert 5: 1 1 3 4 5 Remove 3: 1 1 4 5 Remove 1: 1 4 5 Tcl Note that in general, you would not normally write a tree directly in Tcl when writing code that required an $\alpha$=$\rightarrow \beta$ map, but would rather use either an array variable or a dictionary value (which are internally implemented using a high-performance hash table engine). Works with: Tcl version 8.6 <lang tcl>package require TclOO namespace eval AVL { # Class for the overall tree; manages real public API oo::class create Tree { variable root nil class constructor Template:NodeClass AVL::Node { set class [oo::class create Node [list superclass $nodeClass]] # Create a nil instance to act as a leaf sentinel set nil [my NewNode ""] set root [$nil ref] # Make nil be special oo::objdefine $nil { method height {} {return 0} method key {} {error "no key possible"} method value {} {error "no value possible"} method destroy {} { # Do nothing (doesn't prohibit destruction entirely) } method print {indent increment} { # Do nothing } } } # How to actually manufacture a new node method NewNode {key} { if {![info exists nil]} {set nil ""} $class new $key $nil [list [namespace current]::my NewNode] } # Create a new node in the tree and return it method insert {key} { set node [my NewNode $key] if {$root eq $nil} { set root $node } else { $root insert $node } return $node } # Find the node for a particular key method lookup {key} { for {set node $root} {$node ne $nil} {} { if {[$node key] == $key} { return $node } elseif {[$node key] > $key} { set node [$node left] } else { set node [$node right] } } error "no such node" } # Print a tree out, one node per line method print {{indent 0} {increment 1}} { $root print $indent $increment return } } # Class of an individual node; may be subclassed oo::class create Node { variable key value left right 0 refcount newNode constructor {n nil instanceFactory} { set newNode $instanceFactory set 0 [expr {$nil eq "" ? [self] : $nil}] set key $n set value {} set left [set right $0] set refcount 0 } method ref {} { incr refcount return [self] } method destroy {} { if {[incr refcount -1] < 1} next } method New {key value} { set n [{*}$newNode $key] $n setValue $value return $n } # Getters method key {} {return $key} method value {} {return $value} method left {} {return $left} method right {args} {return $right} # Setters method setValue {newValue} { set value $newValue } method setLeft {node} { # Non-trivial because of reference management $node ref $left destroy set left $node return } method setRight {node} { # Non-trivial because of reference management $node ref $right destroy set right $node return } # Print a node and its descendents method print {indent increment} { puts [format "%s%s => %s" [string repeat " " $indent] $key $value] incr indent $increment $left print $indent $increment $right print $indent $increment } method height {} { return [expr {max([$left height], [$right height]) + 1}] } method balanceFactor {} { expr {[$left height] - [$right height]} } method insert {node} { # Simple insertion if {$key > [$node key]} { if {$left eq $0} { my setLeft $node } else { $left insert $node } } else { if {$right eq $0} { my setRight $node } else { $right insert $node } } # Rebalance this node if {[my balanceFactor] > 1} { if {[$left balanceFactor] < 0} { $left rotateLeft } my rotateRight } elseif {[my balanceFactor] < -1} { if {[$right balanceFactor] > 0} { $right rotateRight } my rotateLeft } } # AVL Rotations method rotateLeft {} { set new [my New $key $value] set key [$right key] set value [$right value] $new setLeft $left $new setRight [$right left] my setLeft $new my setRight [$right right] } method rotateRight {} { set new [my New $key $value] set key [$left key] set value [$left value] $new setLeft [$left right] $new setRight $right my setLeft [$left left] my setRight $new } } }</lang> Demonstrating: <lang tcl># Create an AVL tree AVL::Tree create tree Populate it with some semi-random data for {set i 33} {$i < 127} {incr i} { [tree insert $i] setValue \ [string repeat [format %c $i] [expr {1+int(rand()*5)}]] } Print it out tree print Look up a few values in the tree for {set i 0} {$i < 10} {incr i} { set k [expr {33+int((127-33)*rand())}] puts $k=>[[tree lookup $k] value] } Destroy the tree and all its nodes tree destroy</lang> Output: 64 => @@@ 48 => 000 40 => ((((( 36 => $ 34 => """ 33 => !! 35 => ##### 38 => &&& 37 => % 39 => '''' 44 => , 42 => ** 41 => ))) 43 => +++++ 46 => . 45 => -- 47 => //// 56 => 888 52 => 444 50 => 22222 49 => 1111 51 => 333 54 => 6 53 => 555 55 => 77 60 => <<<< 58 => :::: 57 => 99999 59 => ; 62 => >>> 61 => === 63 => ?? 96 => `` 80 => PPPPP 72 => HHHH 68 => DDD 66 => BBBB 65 => A 67 => CCC 70 => FFF 69 => EEEE 71 => GGG 76 => LL 74 => JJ 73 => III 75 => KKKK 78 => N 77 => MMMMM 79 => OOOOO 88 => XXX 84 => TTTT 82 => R 81 => QQQQ 83 => SSSS 86 => V 85 => UUU 87 => WWW 92 => \\\ 90 => Z 89 => YYYYY 91 => [ 94 => ^^^^^ 93 => ]]]] 95 => _____ 112 => pppp 104 => hh 100 => d 98 => bb 97 => aaa 99 => cccc 102 => ff 101 => eeee 103 => gggg 108 => lll 106 => j 105 => iii 107 => kkkkk 110 => nn 109 => m 111 => o 120 => x 116 => ttt 114 => rrrrr 113 => qqqqq 115 => s 118 => vvv 117 => uuuu 119 => wwww 124 => |||| 122 => zzzz 121 => y 123 => {{{ 125 => }}}} 126 => ~~~~ 53=>555 55=>77 60=><<<< 100=>d 99=>cccc 93=>]]]] 57=>99999 56=>888 47=>//// 39=>'''' TypeScript Translation of: Java For use within a project, consider adding "export default" to AVLtree class declaration. <lang JavaScript>/** A single node in an AVL tree */ class AVLnode <T> { balance: number left: AVLnode<T> right: AVLnode<T> constructor(public key: T, public parent: AVLnode<T> = null) { this.balance = 0 this.left = null this.right = null } } /** The balanced AVL tree */ class AVLtree <T> { // public members organized here constructor() { this.root = null } insert(key: T): boolean { if (this.root === null) { this.root = new AVLnode<T>(key) } else { let n: AVLnode<T> = this.root, parent: AVLnode<T> = null while (true) { if(n.key === key) { return false } parent = n let goLeft: boolean = n.key > key n = goLeft ? n.left : n.right if (n === null) { if (goLeft) { parent.left = new AVLnode<T>(key, parent) } else { parent.right = new AVLnode<T>(key, parent) } this.rebalance(parent) break } } } return true } deleteKey(delKey: T): void { if (this.root === null) { return } let n: AVLnode<T> = this.root, parent: AVLnode<T> = this.root, delNode: AVLnode<T> = null, child: AVLnode<T> = this.root while (child !== null) { parent = n n = child child = delKey >= n.key ? n.right : n.left if (delKey === n.key) { delNode = n } } if (delNode !== null) { delNode.key = n.key child = n.left !== null ? n.left : n.right if (this.root.key === delKey) { this.root = child } else { if (parent.left === n) { parent.left = child } else { parent.right = child } this.rebalance(parent) } } } treeBalanceString(n: AVLnode<T> = this.root): string { if (n !== null) { return `${this.treeBalanceString(n.left)} ${n.balance} ${this.treeBalanceString(n.right)}` } return "" } toString(n: AVLnode<T> = this.root): string { if (n !== null) { return `${this.toString(n.left)} ${n.key} ${this.toString(n.right)}` } return "" } // private members organized here private root: AVLnode<T> private rotateLeft(a: AVLnode<T>): AVLnode<T> { let b: AVLnode<T> = a.right b.parent = a.parent a.right = b.left if (a.right !== null) { a.right.parent = a } b.left = a a.parent = b if (b.parent !== null) { if (b.parent.right === a) { b.parent.right = b } else { b.parent.left = b } } this.setBalance(a) this.setBalance(b) return b } private rotateRight(a: AVLnode<T>): AVLnode<T> { let b: AVLnode<T> = a.left b.parent = a.parent a.left = b.right if (a.left !== null) { a.left.parent = a } b.right = a a.parent = b if (b.parent !== null) { if (b.parent.right === a) { b.parent.right = b } else { b.parent.left = b } } this.setBalance(a) this.setBalance(b) return b } private rotateLeftThenRight(n: AVLnode<T>): AVLnode<T> { n.left = this.rotateLeft(n.left) return this.rotateRight(n) } private rotateRightThenLeft(n: AVLnode<T>): AVLnode<T> { n.right = this.rotateRight(n.right) return this.rotateLeft(n) } private rebalance(n: AVLnode<T>): void { this.setBalance(n) if (n.balance === -2) { if(this.height(n.left.left) >= this.height(n.left.right)) { n = this.rotateRight(n) } else { n = this.rotateLeftThenRight(n) } } else if (n.balance === 2) { if(this.height(n.right.right) >= this.height(n.right.left)) { n = this.rotateLeft(n) } else { n = this.rotateRightThenLeft(n) } } if (n.parent !== null) { this.rebalance(n.parent) } else { this.root = n } } private height(n: AVLnode<T>): number { if (n === null) { return -1 } return 1 + Math.max(this.height(n.left), this.height(n.right)) } private setBalance(n: AVLnode<T>): void { n.balance = this.height(n.right) - this.height(n.left) } public showNodeBalance(n: AVLnode<T>): string { if (n !== null) { return `${this.showNodeBalance(n.left)} ${n.balance} ${this.showNodeBalance(n.right)}` } return "" } } </lang>