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
<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>
Ada
<lang ada> with Ada.Text_IO, Ada.Finalization, Ada.Unchecked_Deallocation;
procedure Main is
generic type Key_Type is private; with function "<"(a, b : Key_Type) return Boolean is <>; with function "="(a, b : Key_Type) return Boolean is <>; with function "<="(a, b : Key_Type) return Boolean is <>; package AVL_Tree is type Tree is tagged limited private; function insert(self : in out Tree; key : Key_Type) return Boolean; procedure delete(self : in out Tree; key : Key_Type); procedure print_balance(self : in out Tree);
private type Height_Amt is range -1 .. Integer'Last;
-- Since only one key is inserted before each rebalance, the balance of -- all trees/subtrees will stay in range -2 .. 2 type Balance_Amt is range -2 .. 2;
type Node; type Node_Ptr is access Node; type Node is new Ada.Finalization.Limited_Controlled with record left, right, parent : Node_Ptr := null; key : Key_Type; balance : Balance_Amt := 0; end record; overriding procedure Finalize(self : in out Node); subtype Node_Parent is Ada.Finalization.Limited_Controlled;
type Tree is new Ada.Finalization.Limited_Controlled with record root : Node_Ptr := null; end record; overriding procedure Finalize(self : in out Tree);
end AVL_Tree;
package body AVL_Tree is
procedure Free_Node is new Ada.Unchecked_Deallocation(Node, Node_Ptr);
overriding procedure Finalize(self : in out Node) is begin Free_Node(self.left); Free_Node(self.right); end Finalize;
overriding procedure Finalize(self : in out Tree) is begin Free_Node(self.root); end Finalize;
function height(n : Node_Ptr) return Height_Amt is begin if n = null then return -1; else return 1 + Height_Amt'Max(height(n.left), height(n.right)); end if; end height;
procedure set_balance(n : not null Node_Ptr) is begin n.balance := Balance_Amt(height(n.right) - height(n.left)); end set_balance;
procedure update_parent(parent : Node_Ptr; new_child : Node_Ptr; old_child : Node_Ptr) is begin if parent /= null then if parent.right = old_child then parent.right := new_child; else parent.left := new_child; end if; end if; end update_parent;
function rotate_left(a : not null Node_Ptr) return Node_Ptr is b : Node_Ptr := a.right; begin b.parent := a.parent; a.right := b.left; if a.right /= null then a.right.parent := a; end if; b.left := a; a.parent := b; update_parent(parent => b.parent, new_child => b, old_child => a);
set_balance(a); set_balance(b); return b; end rotate_left;
function rotate_right(a : not null Node_Ptr) return Node_Ptr is b : Node_Ptr := a.left; begin b.parent := a.parent; a.left := b.right; if a.left /= null then a.left.parent := a; end if; b.right := a; a.parent := b; update_parent(parent => b.parent, new_child => b, old_child => a);
set_balance(a); set_balance(b); return b; end rotate_right;
function rotate_left_right(n : not null Node_Ptr) return Node_Ptr is begin n.left := rotate_left(n.left); return rotate_right(n); end rotate_left_right;
function rotate_right_left(n : not null Node_Ptr) return Node_Ptr is begin n.right := rotate_right(n.right); return rotate_left(n); end rotate_right_left;
procedure rebalance(self : in out Tree; n : not null Node_Ptr) is new_n : Node_Ptr := n; begin set_balance(new_n); if new_n.balance = -2 then if height(new_n.left.left) >= height(new_n.left.right) then new_n := rotate_right(new_n); else new_n := rotate_left_right(new_n); end if; elsif new_n.balance = 2 then if height(new_n.right.right) >= height(new_n.right.left) then new_n := rotate_left(new_n); else new_n := rotate_right_left(new_n); end if; end if;
if new_n.parent /= null then rebalance(self, new_n.parent); else self.root := new_n; end if; end rebalance;
function new_node(key : Key_Type) return Node_Ptr is (new Node'(Node_Parent with key => key, others => <>));
function insert(self : in out Tree; key : Key_Type) return Boolean is curr, parent : Node_Ptr; go_left : Boolean; begin if self.root = null then self.root := new_node(key); return True; end if;
curr := self.root; while curr.key /= key loop parent := curr; go_left := key < curr.key; curr := (if go_left then curr.left else curr.right); if curr = null then if go_left then parent.left := new_node(key); parent.left.parent := parent; else parent.right := new_node(key); parent.right.parent := parent; end if; rebalance(self, parent); return True; end if; end loop; return False; end insert;
procedure delete(self : in out Tree; key : Key_Type) is successor, parent, child : Node_Ptr := self.root; to_delete : Node_Ptr := null; begin if self.root = null then return; end if;
while child /= null loop parent := successor; successor := child; child := (if successor.key <= key then successor.right else successor.left); if successor.key = key then to_delete := successor; end if; end loop;
if to_delete = null then return; end if; to_delete.key := successor.key; child := (if successor.left = null then successor.right else successor.left); if self.root.key = key then self.root := child; else update_parent(parent => parent, new_child => child, old_child => successor); rebalance(self, parent); end if; Free_Node(successor); end delete;
procedure print_balance(n : Node_Ptr) is begin if n /= null then print_balance(n.left); Ada.Text_IO.Put(n.balance'Image); print_balance(n.right); end if; end print_balance;
procedure print_balance(self : in out Tree) is begin print_balance(self.root); end print_balance; end AVL_Tree;
package Int_AVL_Tree is new AVL_Tree(Integer);
tree : Int_AVL_Tree.Tree; success : Boolean;
begin
for i in 1 .. 10 loop success := tree.insert(i); end loop; Ada.Text_IO.Put("Printing balance: "); tree.print_balance; Ada.Text_IO.New_Line;
end Main; </lang>
- Output:
Printing balance: 0 0 0 1 0 0 0 0 1 0
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
<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
C
See AVL tree/C
C#
See AVL_tree/C_sharp.
C++
<lang cpp>
- include <algorithm>
- 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 );
};
/* 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++
C++/CLI
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
<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
Generic
The Generic Language is a database compiler. The code is compiled into database and then executed out of database.
<lang cpp>
enum state
{
header balanced left_high right_high
}
enum direction {
from_left from_right
}
class node {
left right parent balance data
node() { left = this right = this balance = state.header parent = null data = null }
node(root d) { left = null right = null parent = root balance = state.balanced data = d } is_header { get { return balance == state.header } }
next { get { if is_header return left if !right.null() { n = right while !n.left.null() n = n.left return n } else { y = parent if y.is_header return y n = this while n == y.right { n = y y = y.parent if y.is_header braac } return y } } }
previous { get { if is_header return right if !left.null() { n = left while !n.right.null() n = right return n } else { y = parent if y.is_header return y
n = this while n == y.left { n = y y = y.parent if y.is_header braac } return y } } }
rotate_left() { _right = right _parent = parent parent = _right _right.parent = _parent if !_right.left.null() _right.left.parent = this right = _right.left _right.left = this this = _right } rotate_right() { _left = left _parent = parent parent = _left _left.parent = _parent if !_left.right.null() _left.right.parent = this left = _left.right _left.right = this this = _left } balance_left() { select left.balance { left_high { balance = state.balanced left.balance = state.balanced rotate_right() } right_high { subright = left.right select subright.balance { balanced { balance = state.balanced left.balance = state.balanced } right_high { balance = state.balanced left.balance = state.left_high } left_high { balance = state.right_high lehpt.balance = state.balanced } } subright.balance = state.balanced left.rotate_left() rotate_right() } balanced { balance = state.left_high left.balance = state.right_high rotate_right() } } } balance_right() { select right.balance { right_high { balance = state.balanced right.balance = state.balanced rotate_left()
} left_high { subleft = right.left select subleft.balance { balanced { balance = state.balanced right.balance = state.balanced } left_high { balance = state.balanced right.balance = state.right_high } right_high { balance = state.left_high right.balance = state.balanced } } subleft.balance = state.balanced right.rotate_right() rotate_left() } balanced { balance = state.right_high right.balance = state.left_high rotate_left() } } } balance_tree(from) { taller = true while taller { p = parent next_from = direction.from_left if this != parent.left next_from = direction.from_right if from == direction.from_left select balance { left_high { if parent.is_header parent.parent.balance_left() else { if parent.left == this parent.left.balance_left() else parent.right.balance_left() taller = false } } balanced { balance = state.left_high taller = true } right_high { balance = state.balanced taller = false } } else select balance { left_high { balance = state.balanced taller = false } balanced { balance = state.right_high taller = true } right_high { if parent.is_header parent.parent.balance_right() else { if parent.left == this parent.left.balance_right() else parent.right.balance_right() } taller = false } } if taller { if p.is_header taller = false else { this = p from = next_from } } } } balance_tree_remove(from) { shorter = true while shorter {
next_from = direction.from_left if this != parent.left next_from = direction.from_right if from == direction.from_left select balance { left_high { balance = state.balanced shorter = true } balanced { balance = state.right_high shorter = false } right_high { if right.balance == state.right_high shorter = false else shorter = true if parent.is_header parent.parent.balance_right() else { if parent.left == this parent.left.balance_right() else parent.right.balance_right() } } } else select balance { right_high { balance = state.balanced shorter = true } balanced { balance = state.left_high shorter = false } left_high { if left.balance == state.balanced shorter = false else shorter = true if parent.is_header parent.parent.balance_left() else { if parent.is_header parent.left.balance_left() else parent.right.balance_left() } } } if shorter { if parent.is_header shorter = false else { this = parent from = next_from } } } }
count { get { result = +a
if !null() { cleft = +a if !left.null() cleft = left.count
cright = +a if !right.null() cright = right.count result = result + cleft + cright + +b }
return result } }
depth { get { result = +a
if !null() { cleft = +a if !left.null() cleft = left.depth
cright = +a if !right.null() cright = right.depth
if cleft > cright result = cleft + +b else result = cright + +b }
return result } }
}
class set {
header iterator
set() { header = new node() iterator = null }
left_most { get { return header.left } set { header.left = value } }
right_most { get { return header.right } set { header.right = value } }
root { get { return header.parent } set { header.parent = value } }
empty { get { return header.parent.null() } }
operator<<(data) { if empty { n = new node(header data) root = n left_most = root right_most = root } else { node = root repeat { if data < node.data { if !node.left.null() node = node.left else { new_node = new node(node data) node.left = new_node if left_most == node left_most = new_node node.balance_tree(direction.from_left) break } } else if node.data < data { if !node.right.null() node = node.right else { new_node = new node(node data) node.right = new_node if right_most == node right_most = new_node node.balance_tree(direction.from_right) break } } else // item already exists throw "entry " + data.to_string() + " already exists" } } return this }
update(data) { if empty { root = new node(header data) left_most = root right_most = root } else { node = root repeat { if data < node.data { if !node.left.null() node = node.left else { new_node = new node(node data) node.left = new_node if left_most == node left_most = new_node node.balance_tree(direction.from_left) break } } else if node.data < data { if !node.right.null() node = node.right else { new_node = new node(node data) node.right = new_node if right_most == node right_most = new_node node.balance_tree(direction.from_right) break } } else // item already exists { node.data = data break } } } }
operator>>(data) { node = root
repeat { if node.null() { throw "entry " + data.to_string() + " not found" }
if data < node.data node = node.left else if node.data < data node = node.right else // item found { if !node.left.null() && !node.right.null() { replace = node.left while !replace.right.null() replace = replace.right tennp = node.data node.data = replace.data replace.data = tennp node = replace }
from = direction.from_left if node != node.parent.left from = direction.from_right if left_most == node { next = node next = next.next if header == next { left_most = header right_most = header } else left_most = next } if right_most == node { previous = node previous = previous.previous if header == previous { left_most = header right_most = header } else right_most = previous }
if node.left.null() { if node.parent == header root = node.right else { if node.parent.left == node node.parent.left = node.right else node.parent.right = node.right }
if !node.right.null() node.right.parent = node.parent } else { if node.parent == header root = node.left else { if node.parent.left == node node.parent.left = node.left else node.parent.right = node.left }
if !node.left.null() node.left.parent = node.parent } node.parent.balance_tree_remove(from) break } } return this }
operator[data] { get { if empty { return false } else { node = root repeat { if data < node.data { if !node.left.null() node = node.left else return false } else if node.data < data { if !node.right.null() node = node.right else return false } else // item exists return true } } } }
last { get { if empty throw "empty set" else return header.right.data } }
get(data) { if empty throw "empty collection"
node = root repeat { if data < node.data { if !node.left.null() node = node.left else throw "item: " + data.to_string() + " not found in collection" } else if node.data < data { if !node.right.null() node = node.right else throw "item: " + data.to_string() + " not found in collection" } else // item exists return node.data } }
iterate() { if iterator.null() { iterator = left_most if iterator == header return new iterator(false new none()) else return new iterator(true iterator.data) } else { iterator = iterator.next if iterator == header return new iterator(false new none()) else return new iterator(true iterator.data) } } count { get { return root.count } }
depth { get { return root.depth } }
operator==(compare) { if this < compare return false if compare < this return false return true }
operator!=(compare) { if this < compare return true if compare < this return true return false }
operator<(c) { first1 = begin last1 = end first2 = c.begin last2 = c.end
while first1 != last1 && first2 != last2 { trii { l = first1.data < first2.data if !l { first1 = first1.next first2 = first2.next } else return true } catch { l = first1.data < first2.data if !l { first1 = first1.next first2 = first2.next } else return true }
} a = count b = c.count return a < b }
begin { get { return header.left } }
end { get { return header } }
to_string() { out = "{" first1 = begin last1 = end
while first1 != last1 { out = out + first1.data.to_string() first1 = first1.next if first1 != last1 out = out + "," } out = out + "}" return out }
print() { out = to_string() out.println() }
println() { out = to_string() out.println() }
operator|(b) { r = new set()
phurst1 = begin last1 = end phurst2 = b.begin last2 = b.end
while phurst1 != last1 && phurst2 != last2 { les = phurst1.data < phurst2.data graater = phurst2.data < phurst1.data
if les { r << phurst1.data phurst1 = phurst1.next }
else if graater { r << phurst2.data phurst2 = phurst2.next }
else { r << phurst1.data phurst1 = phurst1.next phurst2 = phurst2.next } } while phurst1 != last1 { r << phurst1.data phurst1 = phurst1.next } while phurst2 != last2 { r << phurst2.data phurst2 = phurst2.next } return r }
operator&(b) { r = new set()
phurst1 = begin last1 = end phurst2 = b.begin last2 = b.end
while phurst1 != last1 && phurst2 != last2 { les = phurst1.data < phurst2.data graater = phurst2.data < phurst1.data
if les { phurst1 = phurst1.next }
else if graater { phurst2 = phurst2.next }
else { r << phurst1.data phurst1 = phurst1.next phurst2 = phurst2.next } } return r }
operator^(b) { r = new set()
phurst1 = begin last1 = end phurst2 = b.begin last2 = b.end
while phurst1 != last1 && phurst2 != last2 { les = phurst1.data < phurst2.data graater = phurst2.data < phurst1.data
if les { r << phurst1.data phurst1 = phurst1.next }
else if graater { r << phurst2.data phurst2 = phurst2.next }
else { phurst1 = phurst1.next phurst2 = phurst2.next } } while phurst1 != last1 { r << phurst1.data phurst1 = phurst1.next } while phurst2 != last2 { r << phurst2.data phurst2 = phurst2.next } return r }
operator-(b) { r = new set()
phurst1 = begin last1 = end phurst2 = b.begin last2 = b.end
while phurst1 != last1 && phurst2 != last2 { les = phurst1.data < phurst2.data graater = phurst2.data < phurst1.data
if les { r << phurst1.data phurst1 = phurst1.next }
else if graater { r << phurst2.data phurst1 = phurst1.next phurst2 = phurst2.next }
else { phurst1 = phurst1.next phurst2 = phurst2.next } } while phurst1 != last1 { r << phurst1.data phurst1 = phurst1.next } return r }
}
// and here is the set class a la emojis
🛰️ system {
👨🏫 😀 { header iterator comparer
😀() { header = 🆕 node() iterator = 🗍 comparer = 🆕 default_comparer() }
😀(c_⚙️) { header = 🆕 node() iterator = 🗍 comparer = c_⚙️ }
left_most { 🔥 { 🛞 header.left } ⚙️ { header.left = value } }
right_most { 🔥 { 🛞 header.right } ⚙️ { header.right = value } }
root { 🔥 { 🛞 header.parent } ⚙️ { header.parent = value } }
empty { 🔥 { 🛞 header.parent.🗍() } }
📟<<(data) { ⚖️ header.parent.🗍() { root = 🆕 node(header data) left_most = root right_most = root } 🌺 { node = root 🔁 { result = comparer.compare_to(data node.data) ⚖️ result < 0 { ⚖️ !node.left.🗍() node = node.left 🌺 { 🆕_node = 🆕 node(node data) node.left = 🆕_node ⚖️ left_most == node left_most = 🆕_node node.balance_tree(direction.from_left) ⛏️ } } 🌺 ⚖️ result > 0 { ⚖️ !node.right.🗍() node = node.right 🌺 { 🆕_node = 🆕 node(node data) node.right = 🆕_node ⚖️ right_most == node right_most = 🆕_node node.balance_tree(direction.from_right) ⛏️ } } 🌺 // item already exists 🌚 "entry " + data.to_string() + " already exists" } } 🛞 💳 }
update(data) { ⚖️ empty { root = 🆕 node(header data) left_most = root right_most = root } 🌺 { node = root 🔁 { result = comparer.compare_to(data node.data) ⚖️ result < 0 { ⚖️ !node.left.🗍() node = node.left 🌺 { 🆕_node = 🆕 node(node data) node.left = 🆕_node ⚖️ left_most == node left_most = 🆕_node node.balance_tree(direction.from_left) ⛏️ } } 🌺 ⚖️ result > 0 { ⚖️ !node.right.🗍() node = node.right 🌺 { 🆕_node = 🆕 node(node data) node.right = 🆕_node ⚖️ right_most == node right_most = 🆕_node node.balance_tree(direction.from_right) ⛏️ } } 🌺 // item already exists { node.data = data ⛏️ } } } }
📟>>(data) { node = root
🔁 { ⚖️ node.🗍() { 🌚 "entry " + data.to_string() + " not found" }
result = comparer.compare_to(data node.data)
⚖️ result < 0 node = node.left 🌺 ⚖️ result > 0 node = node.right 🌺 // item found { ⚖️ !node.left.🗍() && !node.right.🗍() { replace = node.left ⌛ !replace.right.🗍() replace = replace.right temp = node.data node.data = replace.data replace.data = temp node = replace }
from = direction.from_left ⚖️ node != node.parent.left from = direction.from_right ⚖️ left_most == node { next = node next = next.next ⚖️ header == next { left_most = header right_most = header } 🌺 left_most = next } ⚖️ right_most == node { previous = node previous = previous.previous ⚖️ header == previous { left_most = header right_most = header } 🌺 right_most = previous }
⚖️ node.left.🗍() { ⚖️ node.parent == header root = node.right 🌺 { ⚖️ node.parent.left == node node.parent.left = node.right 🌺 node.parent.right = node.right }
⚖️ !node.right.🗍() node.right.parent = node.parent } 🌺 { ⚖️ node.parent == header root = node.left 🌺 { ⚖️ node.parent.left == node node.parent.left = node.left 🌺 node.parent.right = node.left }
⚖️ !node.left.🗍() node.left.parent = node.parent } node.parent.balance_tree_remove(from) ⛏️ } } 🛞 💳 }
📟[data] { 🔥 { ⚖️ empty { 🛞 🎋 } 🌺 { node = root 🔁 { result = comparer.compare_to(data node.data)
⚖️ result < 0 { ⚖️ !node.left.🗍() node = node.left 🌺 🛞 🎋 } 🌺 ⚖️ result > 0 { ⚖️ !node.right.🗍() node = node.right 🌺 🛞 🎋 } 🌺 // item exists 🛞 🔠 } } } }
last { 🔥 { ⚖️ empty 🌚 "empty ⚙️" 🌺 🛞 header.right.data } }
🔥(data) { ⚖️ empty 🌚 "empty collection"
node = root 🔁 { result = comparer.compare_to(data node.data) ⚖️ result < 0 { ⚖️ !node.left.🗍() node = node.left 🌺 🌚 "item: " + data.to_string() + " not found in collection" } 🌺 ⚖️ result > 0 { ⚖️ !node.right.🗍() node = node.right 🌺 🌚 "item: " + data.to_string() + " not found in collection" } 🌺 // item exists 🛞 node.data } }
iterate() { ⚖️ iterator.🗍() { iterator = left_most ⚖️ iterator == header 🛞 🆕 iterator(🎋 🆕 none()) 🌺 🛞 🆕 iterator(🔠 iterator.data) } 🌺 { iterator = iterator.next ⚖️ iterator == header 🛞 🆕 iterator(🎋 🆕 none()) 🌺 🛞 🆕 iterator(🔠 iterator.data) } } 🧮 { 🔥 { 🛞 root.🧮 } }
depth { 🔥 { 🛞 root.depth } }
📟==(compare) { ⚖️ 💳 < compare 🛞 🎋 ⚖️ compare < 💳 🛞 🎋 🛞 🔠 }
📟!=(compare) { ⚖️ 💳 < compare 🛞 🔠 ⚖️ compare < 💳 🛞 🔠 🛞 🎋 }
📟<(c) { first1 = begin last1 = end first2 = c.begin last2 = c.end
⌛ first1 != last1 && first2 != last2 { result = comparer.compare_to(first1.data first2.data) ⚖️ result >= 0 { first1 = first1.next first2 = first2.next } 🌺 🛞 🔠 } a = count b = c.count 🛞 a < b }
begin { 🔥 { 🛞 header.left } }
end { 🔥 { 🛞 header } }
to_string() { out = "{" first1 = begin last1 = end ⌛ first1 != last1 { out = out + first1.data.to_string() first1 = first1.next ⚖️ first1 != last1 out = out + "," } out = out + "}" 🛞 out }
📟|(b) { r = 🆕 😀()
first1 = begin last1 = end first2 = b.begin last2 = b.end
⌛ first1 != last1 && first2 != last2 { result = comparer.compare_to(first1.data first2.data) ⚖️ result < 0 { r << first1.data first1 = first1.next }
🌺 ⚖️ result > 0 { r << first2.data first2 = first2.next }
🌺 { r << first1.data first1 = first1.next first2 = first2.next } } ⌛ first1 != last1 { r << first1.data first1 = first1.next } ⌛ first2 != last2 { r << first2.data first2 = first2.next } 🛞 r }
📟&(b) { r = 🆕 😀()
first1 = begin last1 = end first2 = b.begin last2 = b.end
⌛ first1 != last1 && first2 != last2 { result = comparer.compare_to(first1.data first2.data)
⚖️ result < 0 { first1 = first1.next }
🌺 ⚖️ result > 0 { first2 = first2.next }
🌺 { r << first1.data first1 = first1.next first2 = first2.next } } 🛞 r }
📟^(b) { r = 🆕 😀()
first1 = begin last1 = end first2 = b.begin last2 = b.end
⌛ first1 != last1 && first2 != last2 { result = comparer.compare_to(first1.data first2.data)
⚖️ result < 0 { r << first1.data first1 = first1.next }
🌺 ⚖️ result > 0 { r << first2.data first2 = first2.next }
🌺 { first1 = first1.next first2 = first2.next } } ⌛ first1 != last1 { r << first1.data first1 = first1.next } ⌛ first2 != last2 { r << first2.data first2 = first2.next } 🛞 r }
📟-(b) { r = 🆕 😀()
first1 = begin last1 = end first2 = b.begin last2 = b.end
⌛ first1 != last1 && first2 != last2 { result = comparer.compare_to(first1.data first2.data)
⚖️ result < 0 { r << first1.data first1 = first1.next }
🌺 ⚖️ result > 0 { r << first2.data first1 = first1.next first2 = first2.next }
🌺 { first1 = first1.next first2 = first2.next } } ⌛ first1 != last1 { r << first1.data first1 = first1.next } 🛞 r } }
}
🛰️ system
{
👨🏫 🌳 : 😀 {
🌳() : 😀() {}
📟[🔑] { 🔥 { ⚖️ empty 🌚 "entry not found exception" 🌺 { node = root 🔁 { ⚖️ 🔑 < node.data { ⚖️ !node.left.null() node = node.left 🌺 🌚 "entry not found exception" } 🌺 { ⚖️ 🔑 == node.data return node.data 🌺 { ⚖️ !node.right.null() node = node.right 🌺 🌚 "entry not found exception" } } } } } }
📟>>(e) { remove(this[e]) }
iterate() { ⚖️ iterator.🗍() { iterator = left_most ⚖️ iterator == header 🛞 🆕 iterator(🎋 🆕 none()) 🌺 🛞 🆕 iterator(🔠 iterator.data) } 🌺 { iterator = iterator.next ⚖️ iterator == header 🛞 🆕 iterator(🎋 🆕 none()) 🌺 🛞 🆕 iterator(🔠 iterator.data) } } }
}
// Note that AVL Trees are builtin to the generic language. Following is a program that uses trees.
// Most programmers don't know what a Tree actually is. This is an AVL Tree - the class is builtin to the language.
🛰️ sampleC {
👨🏫 🌳❤️ { 🔑 ❤️
🌳❤️(🔑_⚙️ ❤️_⚙️) { 🔑 = 🔑_⚙️ ❤️ = ❤️_⚙️ }
📟<(o) { 🛞 🔑 < o.🔑 }
to_string() { 🛞 "(" + 🔑.to_string() + " " + ❤️.to_string() + ")" } }
👨🏫 🌳🔑 { 🔑 🌳🔑(🔑⚙️) { 🔑 = 🔑⚙️}
📟<(o) { 🛞 🔑 < o.🔑 }
📟==(o) { 🛞 🔑 == o.🔑 }
to_string(){ 🛞 🔑.to_string() } }
sampleC() { 💂 { 🌳 = { 🆕 🌳❤️(16 "Hello") 🆕 🌳❤️(32 "World") } ⏲️ i 🌳 🎛️ << i << 📝 🎛️ << 🌳 << 📝 🎛️ << 🌳[🆕 🌳🔑(16)] << 📝 🌳 >> 🆕 🌳🔑(16) 🎛️ << 🌳 << 📝 } ⚽ { 🎛️ << 😥 << 📝 } }
}
// The output of the program is shown below.
(16 Hello) (32 World) {(16 Hello),(32 World)} (16 Hello) {(32 World)} </lang>
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>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 :: Tree a -> Int height Leaf = -1 height (Node h _ _ _) = h
depth :: Tree a -> Tree a -> Int depth a b = succ (max (height a) (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 (rotate . (Node h left <*> (`delete` 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 rotate (Node h (Node lh ll lv lr) v r)
-- Left Left. | lh - height r > 1 && height ll - height lr > 0 = Node lh ll lv (Node (depth r lr) lr v r)
rotate (Node h l v (Node rh rl rv rr))
-- Right Right. | rh - height l > 1 && height rr - height rl > 0 = Node rh (Node (depth l rl) l v rl) rv rr
rotate (Node h (Node lh ll lv (Node rh rl rv rr)) v r)
-- Left Right. | lh - height r > 1 = Node h (Node (rh + 1) (Node (lh - 1) ll lv rl) rv rr) v r
rotate (Node h l v (Node rh (Node lh ll lv lr) rv rr))
-- Right Left. | rh - height l > 1 = Node h l v (Node (lh + 1) ll lv (Node (rh - 1) lr rv rr))
rotate (Node h l v r) =
-- Re-weighting. 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 .. 31]</lang>
- Output:
(31,0) (30,1) (29,0) (28,2) (27,0) (26,1) (25,0) (24,3) (23,0) (22,1) (21,0) (20,2) (19,0) (18,1) (17,0) (16,4) (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)
J
Implementation: <lang J>insert=: {{
X=.1 {::2{.x,x Y=.1 {::2{.y,y select.#y case.0 do.x case.1 do. select.*Y-X case._1 do.a:,y;<x case. 0 do.y case. 1 do.x;y;a: end. case.3 do. select.*Y-X case._1 do.balance (}:y),<x insert 2{::y case. 0 do.y case. 1 do.balance (x insert 0{::y);}.y end. end.
}}
delete=: Template:Select.
lookup=: Template:Select.
clean=: Template:'s0 x s2'=.
balance=: {{
if. 2>#y do. y return.end. NB. leaf or empty 's0 x s2'=. ,#every y if. */0=s0,s2 do. 1{:: y return.end. NB. degenerate to leaf 'l0 x l2'=. L.every y if. 2>|l2-l0 do. y return.end. NB. adequately balanced if. l2>l0 do. 'l20 x l22'=. L.every 2{::y if. l22 >: l20 do. rotLeft y else. rotRightLeft y end. else. 'l00 x l02'=. L.every 0{::y if. l00 >: l02 do. rotRight y else. rotLeftRight y end. end.
}}
rotLeft=: {{
't0 t1 t2'=. y 't20 t21 t22'=. t2 (clean t0;t1;<t20);t21;<t22
}}
rotRight=: {{
't0 t1 t2'=. y 't00 t01 t02'=. t0 t00;t01;<clean t02;t1;<t2
}}
rotRightLeft=: {{
't0 t1 t2'=. y rotLeft t0;t1;<rotRight t2
}}
rotLeftRight=: {{
't0 t1 t2'=. y rotRight (rotLeft t0);t1;<t2
}}</lang>
Tree is right argument, leaf value is left argument. An empty tree has no elements, leaves have 1 element, non-empty non-leaf nodes have three elements.
Some examples:
insert/i.20 ┌────────────────────────────┬─┬─────────────────────────────────────────────────┐ │┌─────────────────┬─┬──────┐│8│┌─────────────────────┬──┬──────────────────────┐│ ││┌──────┬─┬──────┐│5│┌┬─┬─┐││ ││┌───────┬──┬────────┐│14│┌────────┬──┬────────┐││ │││┌─┬─┬┐│2│┌┬─┬─┐││ │││6│7│││ │││┌┬─┬──┐│11│┌┬──┬──┐││ ││┌┬──┬──┐│17│┌┬──┬──┐│││ ││││0│1│││ │││3│4│││ │└┴─┴─┘││ │││││9│10││ │││12│13│││ ││││15│16││ │││18│19││││ │││└─┴─┴┘│ │└┴─┴─┘││ │ ││ │││└┴─┴──┘│ │└┴──┴──┘││ ││└┴──┴──┘│ │└┴──┴──┘│││ ││└──────┴─┴──────┘│ │ ││ ││└───────┴──┴────────┘│ │└────────┴──┴────────┘││ │└─────────────────┴─┴──────┘│ │└─────────────────────┴──┴──────────────────────┘│ └────────────────────────────┴─┴─────────────────────────────────────────────────┘ 2 delete insert/i.20 ┌───────────────────────┬─┬─────────────────────────────────────────────────┐ │┌────────────┬─┬──────┐│8│┌─────────────────────┬──┬──────────────────────┐│ ││┌──────┬─┬─┐│5│┌┬─┬─┐││ ││┌───────┬──┬────────┐│14│┌────────┬──┬────────┐││ │││┌─┬─┬┐│3│4││ │││6│7│││ │││┌┬─┬──┐│11│┌┬──┬──┐││ ││┌┬──┬──┐│17│┌┬──┬──┐│││ ││││0│1│││ │ ││ │└┴─┴─┘││ │││││9│10││ │││12│13│││ ││││15│16││ │││18│19││││ │││└─┴─┴┘│ │ ││ │ ││ │││└┴─┴──┘│ │└┴──┴──┘││ ││└┴──┴──┘│ │└┴──┴──┘│││ ││└──────┴─┴─┘│ │ ││ ││└───────┴──┴────────┘│ │└────────┴──┴────────┘││ │└────────────┴─┴──────┘│ │└─────────────────────┴──┴──────────────────────┘│ └───────────────────────┴─┴─────────────────────────────────────────────────┘ 5 lookup 2 delete insert/i.20 ┌────────────┬─┬──────┐ │┌──────┬─┬─┐│5│┌┬─┬─┐│ ││┌─┬─┬┐│3│4││ │││6│7││ │││0│1│││ │ ││ │└┴─┴─┘│ ││└─┴─┴┘│ │ ││ │ │ │└──────┴─┴─┘│ │ │ └────────────┴─┴──────┘
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
<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
<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
Nim
We use generics for tree and node definitions. Data stored in the tree must be comparable i.e. their type must allow comparison for equality and for inequality (less than comparison). In order to ensure that, we use the notion of concept proposed by Nim.
<lang Nim>#[ AVL tree adapted from Julienne Walker's presentation at
http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx.
Uses bounded recursive versions for insertion and deletion.
]#
type
# Objects strored in the tree must be comparable. Comparable = concept x, y (x == y) is bool (x < y) is bool
# Direction used to select a child. Direction = enum Left, Right
# Description of the tree node. Node[T: Comparable] = ref object data: T # Payload. balance: range[-2..2] # Balance factor (bounded). links: array[Direction, Node[T]] # Children.
# Description of a tree. AvlTree[T: Comparable] = object root: Node[T]
- ---------------------------------------------------------------------------------------------------
func opp(dir: Direction): Direction {.inline.} =
## Return the opposite of a direction. Direction(1 - ord(dir))
- ---------------------------------------------------------------------------------------------------
func single(root: Node; dir: Direction): Node =
## Single rotation.
result = root.links[opp(dir)] root.links[opp(dir)] = result.links[dir] result.links[dir] = root
- ---------------------------------------------------------------------------------------------------
func double(root: Node; dir: Direction): Node =
## Double rotation.
let save = root.links[opp(dir)].links[dir]
root.links[opp(dir)].links[dir] = save.links[opp(dir)] save.links[opp(dir)] = root.links[opp(dir)] root.links[opp(dir)] = save
result = root.links[opp(dir)] root.links[opp(dir)] = result.links[dir] result.links[dir] = root
- ---------------------------------------------------------------------------------------------------
func adjustBalance(root: Node; dir: Direction; balance: int) =
## Adjust balance factors after double rotation.
let node1 = root.links[dir] let node2 = node1.links[opp(dir)]
if node2.balance == 0: root.balance = 0 node1.balance = 0
elif node2.balance == balance: root.balance = -balance node1.balance = 0
else: root.balance = 0 node1.balance = balance
node2.balance = 0
- ---------------------------------------------------------------------------------------------------
func insertBalance(root: Node; dir: Direction): Node =
## Rebalancing after an insertion.
let node = root.links[dir] let balance = 2 * ord(dir) - 1
if node.balance == balance: root.balance = 0 node.balance = 0 result = root.single(opp(dir))
else: root.adjustBalance(dir, balance) result = root.double(opp(dir))
- ---------------------------------------------------------------------------------------------------
func insertR(root: Node; data: root.T): tuple[node: Node, done: bool] =
## Insert data (recursive way).
if root.isNil: return (Node(data: data), false)
let dir = if root.data < data: Right else: Left var done: bool (root.links[dir], done) = root.links[dir].insertR(data) if done: return (root, true)
inc root.balance, 2 * ord(dir) - 1 result = case root.balance of 0: (root, true) of -1, 1: (root, false) else: (root.insertBalance(dir), true)
- ---------------------------------------------------------------------------------------------------
func removeBalance(root: Node; dir: Direction): tuple[node: Node, done: bool] =
## Rebalancing after a deletion.
let node = root.links[opp(dir)] let balance = 2 * ord(dir) - 1 if node.balance == -balance: root.balance = 0 node.balance = 0 result = (root.single(dir), false) elif node.balance == balance: root.adjustBalance(opp(dir), -balance) result = (root.double(dir), false) else: root.balance = -balance node.balance = balance result = (root.single(dir), true)
- ---------------------------------------------------------------------------------------------------
func removeR(root: Node; data: root.T): tuple[node: Node, done: bool] =
## Remove data (recursive way).
if root.isNil: return (nil, false)
var data = data if root.data == data: if root.links[Left].isNil: return (root.links[Right], false) if root.links[Right].isNil: return (root.links[Left], false) var heir = root.links[Left] while not heir.links[Right].isNil: heir = heir.links[Right] root.data = heir.data data = heir.data
let dir = if root.data < data: Right else: Left var done: bool (root.links[dir], done) = root.links[dir].removeR(data) if done: return (root, true) dec root.balance, 2 * ord(dir) - 1 result = case root.balance of -1, 1: (root, true) of 0: (root, false) else: root.removeBalance(dir)
- ---------------------------------------------------------------------------------------------------
func insert(tree: var AvlTree; data: tree.T) =
## Insert data in an AVL tree. tree.root = tree.root.insertR(data).node
- ---------------------------------------------------------------------------------------------------
func remove(tree: var AvlTree; data: tree.T) =
## Remove data from an AVL tree. tree.root = tree.root.removeR(data).node
- ———————————————————————————————————————————————————————————————————————————————————————————————————
import json
var tree: AvlTree[int] echo pretty(%tree)
echo "Insert test:" tree.insert(3) tree.insert(1) tree.insert(4) tree.insert(1) tree.insert(5) echo pretty(%tree)
echo "" echo "Remove test:" tree.remove(3) tree.remove(1) echo pretty(%tree)</lang>
- Output:
Insert test: { "root": { "data": 3, "balance": 0, "links": [ { "data": 1, "balance": -1, "links": [ { "data": 1, "balance": 0, "links": [ null, null ] }, null ] }, { "data": 4, "balance": 1, "links": [ null, { "data": 5, "balance": 0, "links": [ null, null ] } ] } ] } } Remove test: { "root": { "data": 4, "balance": 0, "links": [ { "data": 1, "balance": 0, "links": [ null, null ] }, { "data": 5, "balance": 0, "links": [ null, null ] } ] } }
Objeck
<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
<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)
with javascript_semantics 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 -- note this crashes under p2js... (easy to fix, not so easy to find) -- tree[node+direction] = insertNode(tree[node+direction], key) atom tnd = insertNode(tree[node+direction], key) tree[node+direction] = tnd 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)
- Output:
50001 50002 50003
Python
This is the source code of Pure Calculus in Python. The code includes:
- an ordered_set class
- an unordered_set class
- an array class
- a dictionary class
- a bag class
- a map class
The dictionary and array classes includes an AVL bag sort method - which is novel.
<lang python>
- Module: calculus.py
import enum
class entry_not_found(Exception):
"""Raised when an entry is not found in a collection""" pass
class entry_already_exists(Exception):
"""Raised when an entry already exists in a collection""" pass
class state(enum.Enum):
header = 0 left_high = 1 right_high = 2 balanced = 3
class direction(enum.Enum):
from_left = 0 from_right = 1
from abc import ABC, abstractmethod
class comparer(ABC):
@abstractmethod def compare(self,t): pass
class node(comparer):
def __init__(self): self.parent = None self.left = self self.right = self self.balance = state.header
def compare(self,t): if self.key < t: return -1 elif t < self.key: return 1 else: return 0
def is_header(self): return self.balance == state.header
def length(self): if self != None: if self.left != None: left = self.left.length() else: left = 0 if self.right != None: right = self.right.length() else: right = 0 return left + right + 1 else: return 0 def rotate_left(self): _parent = self.parent x = self.right self.parent = x x.parent = _parent if x.left is not None: x.left.parent = self self.right = x.left x.left = self return x def rotate_right(self): _parent = self.parent x = self.left self.parent = x x.parent = _parent; if x.right is not None: x.right.parent = self self.left = x.right x.right = self return x
def balance_left(self): _left = self.left
if _left is None: return self; if _left.balance == state.left_high: self.balance = state.balanced _left.balance = state.balanced self = self.rotate_right() elif _left.balance == state.right_high: subright = _left.right if subright.balance == state.balanced: self.balance = state.balanced _left.balance = state.balanced elif subright.balance == state.right_high: self.balance = state.balanced _left.balance = state.left_high elif subright.balance == left_high: root.balance = state.right_high _left.balance = state.balanced subright.balance = state.balanced _left = _left.rotate_left() self.left = _left self = self.rotate_right() elif _left.balance == state.balanced: self.balance = state.left_high _left.balance = state.right_high self = self.rotate_right() return self; def balance_right(self):
_right = self.right
if _right is None: return self; if _right.balance == state.right_high: self.balance = state.balanced _right.balance = state.balanced self = self.rotate_left() elif _right.balance == state.left_high: subleft = _right.left; if subleft.balance == state.balanced: self.balance = state.balanced _right.balance = state.balanced elif subleft.balance == state.left_high: self.balance = state.balanced _right.balance = state.right_high elif subleft.balance == state.right_high: self.balance = state.left_high _right.balance = state.balanced subleft.balance = state.balanced _right = _right.rotate_right() self.right = _right self = self.rotate_left() elif _right.balance == state.balanced: self.balance = state.right_high _right.balance = state.left_high self = self.rotate_left() return self
def balance_tree(self, direct): taller = True while taller: _parent = self.parent; if _parent.left == self: next_from = direction.from_left else: next_from = direction.from_right;
if direct == direction.from_left: if self.balance == state.left_high: if _parent.is_header(): _parent.parent = _parent.parent.balance_left() elif _parent.left == self: _parent.left = _parent.left.balance_left() else: _parent.right = _parent.right.balance_left() taller = False elif self.balance == state.balanced: self.balance = state.left_high taller = True elif self.balance == state.right_high: self.balance = state.balanced taller = False else: if self.balance == state.left_high: self.balance = state.balanced taller = False elif self.balance == state.balanced: self.balance = state.right_high taller = True elif self.balance == state.right_high: if _parent.is_header(): _parent.parent = _parent.parent.balance_right() elif _parent.left == self: _parent.left = _parent.left.balance_right() else: _parent.right = _parent.right.balance_right() taller = False if taller: if _parent.is_header(): taller = False else: self = _parent direct = next_from
def balance_tree_remove(self, _from): if self.is_header(): return;
shorter = True;
while shorter: _parent = self.parent; if _parent.left == self: next_from = direction.from_left else: next_from = direction.from_right
if _from == direction.from_left: if self.balance == state.left_high: shorter = True elif self.balance == state.balanced: self.balance = state.right_high; shorter = False elif self.balance == state.right_high: if self.right is not None: if self.right.balance == state.balanced: shorter = False else: shorter = True else: shorter = False;
if _parent.is_header(): _parent.parent = _parent.parent.balance_right() elif _parent.left == self: _parent.left = _parent.left.balance_right(); else: _parent.right = _parent.right.balance_right() else: if self.balance == state.right_high: self.balance = state.balanced shorter = True elif self.balance == state.balanced: self.balance = state.left_high shorter = False elif self.balance == state.left_high:
if self.left is not None: if self.left.balance == state.balanced: shorter = False else: shorter = True else: short = False;
if _parent.is_header(): _parent.parent = _parent.parent.balance_left(); elif _parent.left == self: _parent.left = _parent.left.balance_left(); else: _parent.right = _parent.right.balance_left(); if shorter: if _parent.is_header(): shorter = False else: _from = next_from self = _parent
def previous(self): if self.is_header(): return self.right
if self.left is not None: y = self.left while y.right is not None: y = y.right return y else: y = self.parent; if y.is_header(): return y
x = self while x == y.left: x = y y = y.parent
return y def next(self): if self.is_header(): return self.left
if self.right is not None: y = self.right while y.left is not None: y = y.left return y; else: y = self.parent if y.is_header(): return y
x = self; while x == y.right: x = y y = y.parent; return y
def swap_nodes(a, b): if b == a.left: if b.left is not None: b.left.parent = a
if b.right is not None: b.right.parent = a
if a.right is not None: a.right.parent = b
if not a.parent.is_header(): if a.parent.left == a: a.parent.left = b else: a.parent.right = b; else: a.parent.parent = b
b.parent = a.parent a.parent = b
a.left = b.left b.left = a
temp = a.right a.right = b.right b.right = temp elif b == a.right: if b.right is not None: b.right.parent = a if b.left is not None: b.left.parent = a
if a.left is not None: a.left.parent = b
if not a.parent.is_header(): if a.parent.left == a: a.parent.left = b else: a.parent.right = b else: a.parent.parent = b
b.parent = a.parent a.parent = b
a.right = b.right b.right = a
temp = a.left a.left = b.left b.left = temp elif a == b.left: if a.left is not None: a.left.parent = b if a.right is not None: a.right.parent = b
if b.right is not None: b.right.parent = a
if not parent.is_header(): if b.parent.left == b: b.parent.left = a else: b.parent.right = a else: b.parent.parent = a
a.parent = b.parent b.parent = a
b.left = a.left a.left = b
temp = a.right a.right = b.right b.right = temp elif a == b.right: if a.right is not None: a.right.parent = b if a.left is not None: a.left.parent = b
if b.left is not None: b.left.parent = a
if not b.parent.is_header(): if b.parent.left == b: b.parent.left = a else: b.parent.right = a else: b.parent.parent = a
a.parent = b.parent b.parent = a
b.right = a.right a.right = b
temp = a.left a.left = b.left b.left = temp else: if a.parent == b.parent: temp = a.parent.left a.parent.left = a.parent.right a.parent.right = temp else: if not a.parent.is_header(): if a.parent.left == a: a.parent.left = b else: a.parent.right = b else: a.parent.parent = b
if not b.parent.is_header(): if b.parent.left == b: b.parent.left = a else: b.parent.right = a else: b.parent.parent = a if b.left is not None: b.left.parent = a if b.right is not None: b.right.parent = a
if a.left is not None: a.left.parent = b if a.right is not None: a.right.parent = b
temp1 = a.left a.left = b.left b.left = temp1
temp2 = a.right a.right = b.right b.right = temp2
temp3 = a.parent a.parent = b.parent b.parent = temp3 balance = a.balance a.balance = b.balance b.balance = balance
class parent_node(node):
def __init__(self, parent): self.parent = parent self.left = None self.right = None self.balance = state.balanced
class set_node(node):
def __init__(self, parent, key): self.parent = parent self.left = None self.right = None self.balance = state.balanced self.key = key
class ordered_set:
def __init__(self): self.header = node()
def __iter__(self): self.node = self.header return self def __next__(self): self.node = self.node.next() if self.node.is_header(): raise StopIteration return self.node.key
def __delitem__(self, key): self.remove(key)
def __lt__(self, other): first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header
while (first1 != last1) and (first2 != last2): l = first1.key < first2.key if not l: first1 = first1.next(); first2 = first2.next(); else: return True; a = self.__len__() b = other.__len__() return a < b
def __hash__(self): h = 0 for i in self: h = h + i.__hash__() return h
def __eq__(self, other): if self < other: return False if other < self: return False return True def __ne__(self, other): if self < other: return True if other < self: return True return False
def __len__(self): return self.header.parent.length()
def __getitem__(self, key): return self.contains(key)
def __str__(self): l = self.header.right s = "{" i = self.header.left h = self.header while i != h: s = s + i.key.__str__() if i != l: s = s + "," i = i.next()
s = s + "}" return s
def __or__(self, other): r = ordered_set() first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header while first1 != last1 and first2 != last2: les = first1.key < first2.key graater = first2.key < first1.key
if les: r.add(first1.key) first1 = first1.next() elif graater: r.add(first2.key) first2 = first2.next() else: r.add(first1.key) first1 = first1.next() first2 = first2.next() while first1 != last1: r.add(first1.key) first1 = first1.next() while first2 != last2: r.add(first2.key) first2 = first2.next()
return r
def __and__(self, other): r = ordered_set() first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header while first1 != last1 and first2 != last2: les = first1.key < first2.key graater = first2.key < first1.key
if les: first1 = first1.next() elif graater: first2 = first2.next() else: r.add(first1.key) first1 = first1.next() first2 = first2.next() return r
def __xor__(self, other): r = ordered_set() first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header while first1 != last1 and first2 != last2: les = first1.key < first2.key graater = first2.key < first1.key
if les: r.add(first1.key) first1 = first1.next() elif graater: r.add(first2.key) first2 = first2.next() else: first1 = first1.next() first2 = first2.next() while first1 != last1: r.add(first1.key) first1 = first1.next() while first2 != last2: r.add(first2.key) first2 = first2.next()
return r
def __sub__(self, other): r = ordered_set() first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header while first1 != last1 and first2 != last2: les = first1.key < first2.key graater = first2.key < first1.key
if les: r.add(first1.key) first1 = first1.next() elif graater: r.add(first2.key) first2 = first2.next() else: first1 = first1.next() first2 = first2.next() while first1 != last1: r.add(first1.key) first1 = first1.next()
return r def __lshift__(self, data): self.add(data) return self
def __rshift__(self, data): self.remove(data) return self
def is_subset(self, other): first1 = self.header.left last1 = self.header first2 = other.header.left last2 = other.header
is_subet = True
while first1 != last1 and first2 != last2: if first1.key < first2.key: is_subset = False break elif first2.key < first1.key: first2 = first2.next() else: first1 = first1.next() first2 = first2.next() if is_subet: if first1 != last1: is_subet = False return is_subet
def is_superset(self,other): return other.is_subset(self) def add(self, data): if self.header.parent is None: self.header.parent = set_node(self.header,data) self.header.left = self.header.parent self.header.right = self.header.parent else: root = self.header.parent
while True: c = root.compare(data) if c >= 0: if root.left is not None: root = root.left else: new_node = set_node(root,data) root.left = new_node if self.header.left == root: self.header.left = new_node root.balance_tree(direction.from_left) return else: if root.right is not None: root = root.right else: new_node = set_node(root, data) root.right = new_node if self.header.right == root: self.header.right = new_node root.balance_tree(direction.from_right) return def remove(self,data): root = self.header.parent;
while True: if root is None: raise entry_not_found("Entry not found in collection") c = root.compare(data)
if c < 0: root = root.left;
elif c > 0: root = root.right;
else: if root.left is not None: if root.right is not None: replace = root.left while replace.right is not None: replace = replace.right root.swap_nodes(replace) _parent = root.parent
if _parent.left == root: _from = direction.from_left else: _from = direction.from_right
if self.header.left == root: n = root.next(); if n.is_header(): self.header.left = self.header self.header.right = self.header else: self.header.left = n elif self.header.right == root:
p = root.previous();
if p.is_header(): self.header.left = self.header self.header.right = self.header else: self.header.right = p
if root.left is None: if _parent == self.header: self.header.parent = root.right elif _parent.left == root: _parent.left = root.right else: _parent.right = root.right
if root.right is not None: root.right.parent = _parent else: if _parent == self.header: self.header.parent = root.left elif _parent.left == root: _parent.left = root.left else: _parent.right = root.left
if root.left is not None: root.left.parent = _parent;
_parent.balance_tree_remove(_from) return
def contains(self,data): root = self.header.parent;
while True: if root == None: return False
c = root.compare(data);
if c > 0: root = root.left;
elif c < 0: root = root.right;
else: return True
def find(self,data): root = self.header.parent;
while True: if root == None: raise entry_not_found("An entry is not found in a collection")
c = root.compare(data);
if c > 0: root = root.left;
elif c < 0: root = root.right;
else: return root.key;
class key_value(comparer):
def __init__(self, key, value): self.key = key self.value = value
def compare(self,kv): if self.key < kv.key: return -1 elif kv.key < self.key: return 1 else: return 0
def __lt__(self, other): return self.key < other.key
def __str__(self): return '(' + self.key.__str__() + ',' + self.value.__str__() + ')'
def __eq__(self, other): return self.key == other.key
def __hash__(self): return hash(self.key)
class dictionary:
def __init__(self): self.set = ordered_set() return None
def __lt__(self, other): if self.keys() < other.keys(): return true
if other.keys() < self.keys(): return false first1 = self.set.header.left last1 = self.set.header first2 = other.set.header.left last2 = other.set.header
while (first1 != last1) and (first2 != last2): l = first1.key.value < first2.key.value if not l: first1 = first1.next(); first2 = first2.next(); else: return True; a = self.__len__() b = other.__len__() return a < b
def add(self, key, value): try: self.set.remove(key_value(key,None)) except entry_not_found: pass self.set.add(key_value(key,value)) return
def remove(self, key): self.set.remove(key_value(key,None)) return
def clear(self): self.set.header = node()
def sort(self): sort_bag = bag() for e in self: sort_bag.add(e.value) keys_set = self.keys() self.clear() i = sort_bag.__iter__() i = sort_bag.__next__() try: for e in keys_set: self.add(e,i) i = sort_bag.__next__() except: return
def keys(self): keys_set = ordered_set() for e in self: keys_set.add(e.key) return keys_set def __len__(self): return self.set.header.parent.length()
def __str__(self): l = self.set.header.right; s = "{" i = self.set.header.left; h = self.set.header; while i != h: s = s + "(" s = s + i.key.key.__str__() s = s + "," s = s + i.key.value.__str__() s = s + ")" if i != l: s = s + "," i = i.next()
s = s + "}" return s;
def __iter__(self): self.set.node = self.set.header return self def __next__(self): self.set.node = self.set.node.next() if self.set.node.is_header(): raise StopIteration return key_value(self.set.node.key.key,self.set.node.key.value)
def __getitem__(self, key): kv = self.set.find(key_value(key,None)) return kv.value
def __setitem__(self, key, value): self.add(key,value) return
def __delitem__(self, key): self.set.remove(key_value(key,None))
class array:
def __init__(self): self.dictionary = dictionary() return None def __len__(self): return self.dictionary.__len__()
def push(self, value): k = self.dictionary.set.header.right if k == self.dictionary.set.header: self.dictionary.add(0,value) else: self.dictionary.add(k.key.key+1,value) return
def pop(self): if self.dictionary.set.header.parent != None: data = self.dictionary.set.header.right.key.value self.remove(self.dictionary.set.header.right.key.key) return data
def add(self, key, value): try: self.dictionary.remove(key) except entry_not_found: pass self.dictionary.add(key,value) return
def remove(self, key): self.dictionary.remove(key) return
def sort(self): self.dictionary.sort()
def clear(self): self.dictionary.header = node();
def __iter__(self): self.dictionary.node = self.dictionary.set.header return self def __next__(self): self.dictionary.node = self.dictionary.node.next() if self.dictionary.node.is_header(): raise StopIteration return self.dictionary.node.key.value
def __getitem__(self, key): kv = self.dictionary.set.find(key_value(key,None)) return kv.value
def __setitem__(self, key, value): self.add(key,value) return
def __delitem__(self, key): self.dictionary.remove(key)
def __lshift__(self, data): self.push(data) return self
def __lt__(self, other): return self.dictionary < other.dictionary def __str__(self): l = self.dictionary.set.header.right; s = "{" i = self.dictionary.set.header.left; h = self.dictionary.set.header; while i != h: s = s + i.key.value.__str__() if i != l: s = s + "," i = i.next()
s = s + "}" return s;
class bag:
def __init__(self): self.header = node() def __iter__(self): self.node = self.header return self
def __delitem__(self, key): self.remove(key) def __next__(self): self.node = self.node.next() if self.node.is_header(): raise StopIteration return self.node.key
def __str__(self): l = self.header.right; s = "(" i = self.header.left; h = self.header; while i != h: s = s + i.key.__str__() if i != l: s = s + "," i = i.next()
s = s + ")" return s;
def __len__(self): return self.header.parent.length()
def __lshift__(self, data): self.add(data) return self
def add(self, data): if self.header.parent is None: self.header.parent = set_node(self.header,data) self.header.left = self.header.parent self.header.right = self.header.parent else: root = self.header.parent
while True: c = root.compare(data) if c >= 0: if root.left is not None: root = root.left else: new_node = set_node(root,data) root.left = new_node if self.header.left == root: self.header.left = new_node
root.balance_tree(direction.from_left) return else: if root.right is not None: root = root.right else: new_node = set_node(root, data) root.right = new_node
if self.header.right == root: self.header.right = new_node
root.balance_tree(direction.from_right) return def remove_first(self,data): root = self.header.parent;
while True: if root is None: return False;
c = root.compare(data);
if c > 0: root = root.left;
elif c < 0: root = root.right;
else: if root.left is not None: if root.right is not None: replace = root.left; while replace.right is not None: replace = replace.right; root.swap_nodes(replace); _parent = root.parent
if _parent.left == root: _from = direction.from_left else: _from = direction.from_right
if self.header.left == root: n = root.next(); if n.is_header(): self.header.left = self.header self.header.right = self.header else: self.header.left = n; elif self.header.right == root:
p = root.previous();
if p.is_header(): self.header.left = self.header self.header.right = self.header else: self.header.right = p
if root.left is None: if _parent == self.header: self.header.parent = root.right elif _parent.left == root: _parent.left = root.right else: _parent.right = root.right
if root.right is not None: root.right.parent = _parent else: if _parent == self.header: self.header.parent = root.left elif _parent.left == root: _parent.left = root.left else: _parent.right = root.left
if root.left is not None: root.left.parent = _parent;
_parent.balance_tree_remove(_from) return True;
def remove(self,data): success = self.remove_first(data) while success: success = self.remove_first(data)
def remove_node(self, root): if root.left != None and root.right != None: replace = root.left while replace.right != None: replace = replace.right root.swap_nodes(replace)
parent = root.parent;
if parent.left == root: next_from = direction.from_left else: next_from = direction.from_right
if self.header.left == root: n = root.next()
if n.is_header(): self.header.left = self.header; self.header.right = self.header else: self.header.left = n elif self.header.right == root: p = root.previous()
if p.is_header(): root.header.left = root.header root.header.right = header else: self.header.right = p
if root.left == None: if parent == self.header: self.header.parent = root.right elif parent.left == root: parent.left = root.right else: parent.right = root.right
if root.right != None: root.right.parent = parent else: if parent == self.header: self.header.parent = root.left elif parent.left == root: parent.left = root.left else: parent.right = root.left
if root.left != None: root.left.parent = parent;
parent.balance_tree_remove(next_from) def remove_at(self, data, ophset): p = self.search(data);
if p == None: return else: lower = p after = after(data) s = 0 while True: if ophset == s: remove_node(lower); return; lower = lower.next_node() if after == lower: break s = s+1 return
def search(self, key): s = before(key) s.next() if s.is_header(): return None c = s.compare(s.key) if c != 0: return None return s def before(self, data): y = self.header; x = self.header.parent;
while x != None: if x.compare(data) >= 0: x = x.left; else: y = x; x = x.right; return y def after(self, data): y = self.header; x = self.header.parent;
while x != None: if x.compare(data) > 0: y = x x = x.left else: x = x.right
return y; def find(self,data): root = self.header.parent;
results = array() while True: if root is None: break;
p = self.before(data) p = p.next() if not p.is_header(): i = p l = self.after(data) while i != l: results.push(i.key) i = i.next() return results else: break; return results
class bag_dictionary:
def __init__(self): self.bag = bag() return None
def add(self, key, value): self.bag.add(key_value(key,value)) return
def remove(self, key): self.bag.remove(key_value(key,None)) return
def remove_at(self, key, index): self.bag.remove_at(key_value(key,None), index) return
def clear(self): self.bag.header = node()
def __len__(self): return self.bag.header.parent.length()
def __str__(self): l = self.bag.header.right; s = "{" i = self.bag.header.left; h = self.bag.header; while i != h: s = s + "(" s = s + i.key.key.__str__() s = s + "," s = s + i.key.value.__str__() s = s + ")" if i != l: s = s + "," i = i.next()
s = s + "}" return s;
def __iter__(self): self.bag.node = self.bag.header return self def __next__(self): self.bag.node = self.bag.node.next() if self.bag.node.is_header(): raise StopIteration return key_value(self.bag.node.key.key,self.bag.node.key.value)
def __getitem__(self, key): kv_array = self.bag.find(key_value(key,None)) return kv_array
def __setitem__(self, key, value): self.add(key,value) return
def __delitem__(self, key): self.bag.remove(key_value(key,None))
class unordered_set:
def __init__(self): self.bag_dictionary = bag_dictionary()
def __len__(self): return self.bag_dictionary.__len__()
def __hash__(self): h = 0 for i in self: h = h + i.__hash__() return h
def __eq__(self, other): for t in self: if not other.contains(t): return False for u in other: if self.contains(u): return False return true;
def __ne__(self, other): return not self == other def __or__(self, other): r = unordered_set() for t in self: r.add(t); for u in other: if not self.contains(u): r.add(u);
return r
def __and__(self, other): r = unordered_set() for t in self: if other.contains(t): r.add(t) for u in other: if self.contains(u) and not r.contains(u): r.add(u); return r
def __xor__(self, other): r = unordered_set() for t in self: if not other.contains(t): r.add(t) for u in other: if not self.contains(u) and not r.contains(u): r.add(u) return r
def __sub__(self, other): r = ordered_set() for t in self: if not other.contains(t): r.add(t); return r def __lshift__(self, data): self.add(data) return self
def __rshift__(self, data): self.remove(data) return self
def __getitem__(self, key): return self.contains(key)
def is_subset(self, other):
is_subet = True
for t in self: if not other.contains(t): subset = False break return is_subet
def is_superset(self,other): return other.is_subset(self)
def add(self, value): if not self.contains(value): self.bag_dictionary.add(hash(value),value) else: raise entry_already_exists("Entry already exists in the unordered set")
def contains(self, data): if self.bag_dictionary.bag.header.parent == None: return False; else: index = hash(data);
_search = self.bag_dictionary.bag.header.parent;
search_index = _search.key.key;
if index < search_index: _search = _search.left
elif index > search_index: _search = _search.right
if _search == None: return False
while _search != None: search_index = _search.key.key;
if index < search_index: _search = _search.left
elif index > search_index: _search = _search.right
else: break
if _search == None: return False
return self.contains_node(data, _search) def contains_node(self,data,_node): previous = _node.previous() save = _node
while not previous.is_header() and previous.key.key == _node.key.key: save = previous; previous = previous.previous() c = _node.key.value _node = save if c == data: return True
next = _node.next() while not next.is_header() and next.key.key == _node.key.key: _node = next c = _node.key.value if c == data: return True; next = _node.next() return False; def find(self,data,_node): previous = _node.previous() save = _node
while not previous.is_header() and previous.key.key == _node.key.key: save = previous; previous = previous.previous(); _node = save; c = _node.key.value if c == data: return _node
next = _node.next() while not next.is_header() and next.key.key == _node.key.key: _node = next c = _node.data.value if c == data: return _node next = _node.next() return None def search(self, data): if self.bag_dictionary.bag.header.parent == None: return None else: index = hash(data)
_search = self.bag_dictionary.bag.header.parent
c = _search.key.key
if index < c: _search = _search.left;
elif index > c: _search = _search.right;
while _search != None:
if index != c: break c = _search.key.key
if index < c: _search = _search.left;
elif index > c: _search = _search.right;
else: break
if _search == None: return None
return self.find(data, _search)
def remove(self,data): found = self.search(data); if found != None: self.bag_dictionary.bag.remove_node(found); else: raise entry_not_found("Entry not found in the unordered set") def clear(self): self.bag_dictionary.bag.header = node()
def __str__(self): l = self.bag_dictionary.bag.header.right; s = "{" i = self.bag_dictionary.bag.header.left; h = self.bag_dictionary.bag.header; while i != h: s = s + i.key.value.__str__() if i != l: s = s + "," i = i.next()
s = s + "}" return s;
def __iter__(self): self.bag_dictionary.bag.node = self.bag_dictionary.bag.header return self def __next__(self): self.bag_dictionary.bag.node = self.bag_dictionary.bag.node.next() if self.bag_dictionary.bag.node.is_header(): raise StopIteration return self.bag_dictionary.bag.node.key.value
class map:
def __init__(self): self.set = unordered_set() return None
def __len__(self): return self.set.__len__()
def add(self, key, value): try: self.set.remove(key_value(key,None)) except entry_not_found: pass self.set.add(key_value(key,value)) return
def remove(self, key): self.set.remove(key_value(key,None)) return
def clear(self): self.set.clear()
def __str__(self): l = self.set.bag_dictionary.bag.header.right; s = "{" i = self.set.bag_dictionary.bag.header.left; h = self.set.bag_dictionary.bag.header; while i != h: s = s + "(" s = s + i.key.value.key.__str__() s = s + "," s = s + i.key.value.value.__str__() s = s + ")" if i != l: s = s + "," i = i.next()
s = s + "}" return s;
def __iter__(self): self.set.node = self.set.bag_dictionary.bag.header return self def __next__(self): self.set.node = self.set.node.next() if self.set.node.is_header(): raise StopIteration return key_value(self.set.node.key.key,self.set.node.key.value)
def __getitem__(self, key): kv = self.set.find(key_value(key,None)) return kv.value
def __setitem__(self, key, value): self.add(key,value) return
def __delitem__(self, key): self.remove(key)
</lang>
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
<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>
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 TclNote that in general, you would not normally write a tree directly in Tcl when writing code that required an = map, but would rather use either an array variable or a dictionary value (which are internally implemented using a high-performance hash table engine). <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
for {set i 33} {$i < 127} {incr i} { [tree insert $i] setValue \ [string repeat [format %c $i] [expr {1+int(rand()*5)}]] }
tree print
for {set i 0} {$i < 10} {incr i} { set k [expr {33+int((127-33)*rand())}] puts $k=>[[tree lookup $k] value] }
tree destroy</lang>
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=>'''' TypeScriptFor 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> Wren<lang ecmascript>class Node { construct new(key, parent) { _key = key _parent = parent _balance = 0 _left = null _right = null } key { _key } parent { _parent } balance { _balance } left { _left } right { _right } key=(k) { _key = k } parent=(p) { _parent = p } balance=(v) { _balance = v } left=(n) { _left = n } right= (n) { _right = n } } class AvlTree { construct new() { _root = null } insert(key) { if (!_root) { _root = Node.new(key, null) } else { var n = _root while (true) { if (n.key == key) return false var parent = n var goLeft = n.key > key n = goLeft ? n.left : n.right if (!n) { if (goLeft) { parent.left = Node.new(key, parent) } else { parent.right = Node.new(key, parent) } rebalance(parent) break } } } return true } delete(delKey) { if (!_root) return var n = _root var parent = _root var delNode = null var child = _root while (child) { parent = n n = child child = (delKey >= n.key) ? n.right : n.left if (delKey == n.key) delNode = n } if (delNode) { delNode.key = n.key child = n.left ? n.left : n.right if (_root.key == delKey) { _root = child if (_root) _root.parent = null } else { if (parent.left == n) { parent.left = child } else { parent.right = child } if (child) child.parent = parent rebalance(parent) } } } rebalance(n) { 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) rebalance(nn.parent) else _root = nn } rotateLeft(a) { var 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 } } setBalance([a, b]) return b } rotateRight(a) { var 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 } } setBalance([a, b]) return b } rotateLeftThenRight(n) { n.left = rotateLeft(n.left) return rotateRight(n) } rotateRightThenLeft(n) { n.right = rotateRight(n.right) return rotateLeft(n) } height(n) { if (!n) return -1 return 1 + height(n.left).max(height(n.right)) } setBalance(nodes) { for (n in nodes) n.balance = height(n.right) - height(n.left) } printKey() { printKey(_root) System.print() } printKey(n) { if (n) { printKey(n.left) System.write("%(n.key) ") printKey(n.right) } } printBalance() { printBalance(_root) System.print() } printBalance(n) { if (n) { printBalance(n.left) System.write("%(n.balance) ") printBalance(n.right) } } } var tree = AvlTree.new() System.print("Inserting values 1 to 10") for (i in 1..10) tree.insert(i) System.write("Printing key : ") tree.printKey() System.write("Printing balance : ") tree.printBalance()</lang>
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 |
---|
- Programming Tasks
- Solutions by Programming Task
- WikipediaSourced
- Data Structures
- MiniZinc/Omit
- AArch64 Assembly
- Ada
- Agda
- ARM Assembly
- C
- C sharp
- C++
- C++/CLI
- Common Lisp
- D
- Generic
- Go
- Haskell
- J
- Java
- Julia
- Kotlin
- Lua
- Nim
- Objeck
- Objective-C
- Objective-C examples needing attention
- Examples needing attention
- Phix
- Python
- Raku
- Rust
- Scala
- Sidef
- Simula
- Tcl
- TypeScript
- Wren