# SnippetAVL Tree

#### Nestharus

##### o-o
JASS:
``````
library AVL /* v1.1.0.4
*************************************************************************************
*
*   An AVL Tree with a Linked List. The Linked List allows one to loop through all the values
*   in the tree in ascendending or descending order. The tree allows on to search for exact or
*   closest values.
*
*   An AVL Tree specializes in searches. The balancing algorithm is a little heftier than its
*   counterpart, the red-black tree. However, the heftier balancing ensures minimal iterations when
*   searching for values.
*
*   Plain value searches are O(1). The AVL Tree uses a hashtable in the background to do
*   extremely fast precise value searches.
*
*   Close value searches are O(1+log n). The value is first looked up in the hashtable
*   to see if it exists. If it doesn&#039;t exist, a close approximiation is looked for. From there,
*   it looks around that approximiation in the linked list for neighboring values that might be
*   closer. The closer approximation is always at most 1 off from the actual value in the list.
*
*************************************************************************************
*
*   */uses/*
*
*       */ Table /*         hiveworkshop.com/forums/jass-functions-413/snippet-new-table-188084/
*
************************************************************************************
*
*   module AVLTree
*
*       Interface:
*           method lessThan takes thistype value returns boolean
*           method greaterThan takes thistype value returns boolean
*
*           -   Tree pointer. Accessible from any node on the tree.
*           -   Root of two children (if root is 0, it&#039;s the tree&#039;s root)
*       readonly thistype down (tree pointer only)
*           -   The tree has only 1 child, the root
*
*
*           -   Value stored in node
*
*       static method create takes nothing returns thistype
*       method destroy takes nothing returns nothing
*
*       method search takes thistype value returns thistype
*           -   Returns the node containing the value
*           -   If the value didn&#039;t exist, it will return 0
*       method searchClose takes thistype value, boolean low returns thistype
*           -   Searches for the best match to the value.
*           -
*           -   Low = True
*           -       Search for the closest value &lt;= to the target value
*           -
*           -   Low = False
*           -       Search for the closest value &gt;= to the target value
*
*       method has takes thistype value returns boolean
*           -   Returns true if a node contains the value
*
*       method add takes thistype value returns thistype
*           -   Returns new node containing added value. If the value
*           -   was already in the tree, it returns the node that already
*           -   contained that value.
*       method delete takes nothing returns nothing
*           -   Deletes node
*
*           -&gt;  Delete the value 15 from the tree if it exists
*           -&gt;  call search(15).delete()
*
*       method clear takes nothing returns thistype
*           -   Clears the tree of all nodes
*           -   Returns tree pointer (just in case some node in the tree was passed in rather than the tree)
*
************************************************************************************/
module AVL
private static Table array table    //for O(1) searches on specific values
private static thistype c=0         //instance count
private static thistype array b     //root
private static thistype array l     //left
private static thistype array r     //right
private static integer array h      //height
private static thistype array p     //parent
private static thistype array v     //value
private static integer array nn     //next node
private static integer array pn     //prev node
private static integer array ro     //root
method operator tree takes nothing returns thistype
return ro[this]
endmethod
method operator root takes nothing returns thistype
return p[this]
endmethod
method operator down takes nothing returns thistype
return b[this]
endmethod
method operator left takes nothing returns thistype
return l[this]
endmethod
method operator right takes nothing returns thistype
return r[this]
endmethod
method operator value takes nothing returns thistype
return v[this]
endmethod
method operator next takes nothing returns thistype
return nn[this]
endmethod
method operator prev takes nothing returns thistype
return pn[this]
endmethod
method operator head takes nothing returns boolean
return 0==p[this]
endmethod
private method getHeight takes nothing returns integer
//return the bigger leaf height
if (h[l[this]]&gt;h[r[this]]) then
return h[l[this]]+1
endif
return h[r[this]]+1
endmethod
private method updateParent takes integer n returns nothing
//only update the parent of a target leaf if that leaf isn&#039;t the original leaf
if (n!=this) then
//update the parent point to
//first leaf
if (0==p[p[this]]) then
set b[p[this]]=n
//left
elseif (l[p[this]]==this) then
set l[p[this]]=n
//right
else
set r[p[this]]=n
endif

//update the leaf point back
//if the leaf isn&#039;t null, update the leaf&#039;s parent
if (0!=n) then
set p[n]=p[this]
endif
endif
endmethod
private method finishRotate takes thistype n returns nothing
//this code is identical in rotateLeft and rotateRight, so it has
//been abstracted to a method
call updateParent(n)
set p[this]=n
set h[this]=getHeight()
set h[n]=n.getHeight()
endmethod
private method rotateLeft takes nothing returns thistype
local thistype n=r[this]
set r[this]=l[n]
set p[l[n]]=this
set l[n]=this
call finishRotate(n)
return n
endmethod
private method rotateRight takes nothing returns thistype
local thistype n=l[this]
set l[this]=r[n]
set p[r[n]]=this
set r[n]=this
call finishRotate(n)
return n
endmethod
//return the difference between the left and right leaf heights
private method getBalanceFactor takes nothing returns integer
return h[l[this]]-h[r[this]]
endmethod
private static method allocate takes nothing returns thistype
local integer n
if (0==nn[0]) then
set n=c+1
set c=n
else
set n=nn[0]     //notice that the recycler uses the next pointer
//the reason it is used is for fast clear/destroy and to save
//a variable
set nn[0]=nn[n]
endif
set l[n]=0          //left leaf
set r[n]=0          //right leaf
set b[n]=0          //down leaf (first node of tree)
set h[n]=1          //height (a node will always have at least a height of 1 for itself)
return n
endmethod
static method create takes nothing returns thistype
local integer n=allocate()
set p[n]=0      //the parent of the tree node is 0

//initialize tree next and prev
set nn[n]=n
set pn[n]=n

//tree value table for O(1) searches on specific values
set table[n]=Table.create()

//tree root is itself (allows one to pass any node from the tree into the methods)
set ro[n]=n

return n
endmethod
//balance from the current node up to the root O(log n)
//balancing is rotations wherever rotations need to be done
private method balance takes nothing returns nothing
local integer f
loop
exitwhen 0==p[this]
set h[this]=getHeight()
set f=getBalanceFactor()
if (2==f) then
if (-1==l[this].getBalanceFactor()) then
call l[this].rotateLeft()
endif
set this=rotateRight()
return
elseif (-2==f) then
if (1==r[this].getBalanceFactor()) then
call r[this].rotateRight()
endif
set this=rotateLeft()
return
endif
set this=p[this]
endloop
endmethod
//goes to the very bottom of a node (for deletion)
private method getBottom takes nothing returns thistype
if (0!=r[this]) then
if (0!=l[this]) then
set this=r[this]
loop
exitwhen 0==l[this]
set this=l[this]
endloop
return this
else
return r[this]
endif
elseif (0!=l[this]) then
return l[this]
endif
return this
endmethod
method search takes thistype val returns thistype
return table[ro[this]][val]
endmethod
method has takes thistype val returns boolean
return table[ro[this]].has(val)
endmethod
method searchClose takes thistype val, boolean low returns thistype
local thistype n

//retrieve tree
set this=ro[this]

//if tree is empty, return 0
if (0==b[this]) then
return 0
endif

//check to see if the node exists in the tree and return it if it does
set n=table[this][val]
if (0!=n) then
return n
endif

//perform a standard tree search for the value to the bottom of the tree
//will always be at most 1 off from the best match
set this=b[this]
loop
if (val.lessThan(v[this])) then
exitwhen 0==l[this]
set this=l[this]
else
exitwhen 0==r[this]
set this=r[this]
endif
endloop

//look at the found value&#039;s neighbors on the linked list
if (low) then
//shift down if greater than
if (v[this].greaterThan(val)) then
set this=prev
endif
//return 0 if node wasn&#039;t found
if (0==p[this] or v[this].greaterThan(val)) then
return 0
endif
else
//shift up if less than
if (v[this].lessThan(val)) then
set this=next
endif
//return 0 if node wasn&#039;t found
if (0==p[this] or v[this].lessThan(val)) then
return 0
endif
endif

return this
endmethod
method add takes thistype val returns thistype
local thistype n

//check if the tree already has the value in it
set this=ro[this]
set n=table[this][val]

//if the tree doesn&#039;t have the value in it, add the value
if (0==n) then
set n=this

set this=allocate()
set ro[this]=n              //store tree into leaf
set table[n][val]=this      //store leaf into value table
set v[this]=val             //store value into leaf

//if the tree is empty
if (0==b[n]) then
set b[n]=this           //place as first node
set p[this]=n           //parent of first node is tree

set nn[this]=n
set pn[this]=n
set nn[n]=this
set pn[n]=this
else
//go to the first node in the tree
set n=b[n]

//go to the bottom of the tree with search algorithm
loop
if (val.lessThan(v[n])) then
exitwhen 0==l[n]
set n=l[n]
else
exitwhen 0==r[n]
set n=r[n]
endif
endloop

set p[this]=n
if (val.lessThan(v[n])) then
set l[n]=this
else
set r[n]=this
endif

//update the height of the parent
set h[n]=n.getHeight()

//balance from the parent upwards
call p[n].balance()

if (v[n].greaterThan(v[this])) then
set n=pn[n]
endif
set nn[this]=nn[n]
set pn[this]=n
set pn[nn[n]]=this
set nn[n]=this
endif
return this
endif
return n
endmethod
method delete takes nothing returns nothing
local thistype n
local thistype y

//if the leaf to be deleted isn&#039;t 0 and the leaf isn&#039;t the tree
if (0 != this and 0 != p[this]) then
//remove the leaf from the value table
call table[ro[this]].remove(v[this])

set n=getBottom()       //retrieve the bottom leaf
set y=p[n]              //store the parent here for balancing later

//move the found leaf into the deleted leaf&#039;s position
call n.updateParent(0)
call updateParent(n)
if (this!=n) then
set l[n]=l[this]
set p[l[n]]=n
set r[n]=r[this]
set p[r[n]]=n
set p[n]=p[this]
set h[n]=h[this]
endif

//balance from the found leaf&#039;s old parent upwards
call y.balance()

//remove deleted leaf from list
set nn[pn[this]]=nn[this]
set pn[nn[this]]=pn[this]
set nn[this]=nn[0]
set nn[0]=this
endif
endmethod
method clear takes nothing returns thistype
//quick clear
set this=ro[this]
set nn[pn[this]]=nn[0]
set nn[0]=nn[this]
set nn[this]=this
set pn[this]=this
return this
endmethod
method destroy takes nothing returns nothing
//quick destroy
set this=ro[this]
set nn[pn[this]]=nn[0]
set nn[0]=this
call table[this].destroy()
endmethod
endmodule
endlibrary``````

JASS:
``````
struct Tester extends array
private method lessThan takes thistype val returns boolean
return integer(this)&lt;integer(val)
endmethod
private method greaterThan takes thistype val returns boolean
return integer(this)&gt;integer(val)
endmethod
private method difference takes thistype val returns integer
return integer(this)-integer(val)
endmethod

implement AVL

private static method init takes nothing returns nothing
local thistype this=create()
//call clear()
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,&quot;               &quot;+I2S(down.value))
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,&quot;      &quot;+I2S(down.left.value)+&quot;               &quot;+I2S(down.right.value))
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,&quot;  &quot;+I2S(down.left.left.value)+&quot;      &quot;+I2S(down.left.right.value)+&quot;       &quot;+I2S(down.right.left.value)+&quot;      &quot;+I2S(down.right.right.value))
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,I2S(down.left.left.left.value)+&quot;  &quot;+I2S(down.left.left.right.value)+&quot;  &quot;+I2S(down.left.right.left.value)+&quot;  &quot;+I2S(down.left.right.right.value)+&quot;  &quot;+I2S(down.right.left.left.value)+&quot;  &quot;+I2S(down.right.left.right.value)+&quot;  &quot;+I2S(down.right.right.left.value)+&quot;  &quot;+I2S(down.right.right.right.value))
call DestroyTimer(GetExpiredTimer())
endmethod
private static method onInit takes nothing returns nothing
call TimerStart(CreateTimer(),0,false,function thistype.init)
endmethod
endstruct``````

JASS:
``````
struct Tester extends array
private method lessThan takes thistype val returns boolean
return integer(this)&lt;integer(val)
endmethod
private method greaterThan takes thistype val returns boolean
return integer(this)&gt;integer(val)
endmethod
private method difference takes thistype val returns integer
return integer(this)-integer(val)
endmethod

implement AVL

private static method init takes nothing returns nothing
local thistype this=create()
local thistype s
local string str=&quot;&quot;

loop
set this=next
if (str==&quot;&quot;) then
set str=I2S(value)
else
set str=str+&quot;,&quot;+I2S(value)
endif
endloop
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,str)

set s = searchClose(22,false)
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,&quot;22 High -&gt; &quot;+I2S(s.value))
set s = searchClose(22,true)
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,&quot;22 Low -&gt; &quot;+I2S(s.value))

call DestroyTimer(GetExpiredTimer())
endmethod
private static method onInit takes nothing returns nothing
call TimerStart(CreateTimer(),0,false,function thistype.init)
endmethod
endstruct``````

Graveyarded.

If you're wanting me to write what an AVL tree is, that's never going to happen.

Ok, since I added a lot of stuff that isn't customary to an AVL Tree, this now has documentation on what it is : P.

General chit-chat
Help Users
• No one is chatting at the moment.
• The Helper:
News portal has been retired. Main page of site goes to Headline News forum now
• The Helper:
I am working on getting access to the old news portal under a different URL for those that would rather use that for news before we get a different news view.
• Ghan:
Easily done
+1
• The Helper:
https://www.thehelper.net/pages/news/ is a link to the old news portal - i will integrate it into the interface somewhere when i figure it out
• Ghan:
Need to try something
• Ghan:
Hopefully this won't cause problems.
• Ghan:
Hmm
• Ghan:
I have converted the Headline News forum to an Article type forum. It will now show the top 20 threads with more detail of each thread.
• Ghan:
See how we like that.
• The Helper:
I do not see a way to go past the 1st page of posts on the forum though
• The Helper:
It is OK though for the main page to open up on the forum in the view it was before. As long as the portal has its own URL so it can be viewed that way I do want to try it as a regular forum view for a while
• Ghan:
Yeah I'm not sure what the deal is with the pagination.
• Ghan:
It SHOULD be there so I think it might just be an artifact of having an older style.
• Ghan:
I switched it to a "Standard" article forum. This will show the thread list like normal, but the threads themselves will have the first post set up above the rest of the "comments"
• The Helper:
I don't really get that article forum but I think it is because I have never really seen it used on a multi post thread
• Ghan:
RpNation makes more use of it right now as an example: https://www.rpnation.com/news/
• The Helper:
• The Helper:
What do you think Tom?
• tom_mai78101:
I will have to get used to this.
• tom_mai78101:
The latest news feed looks good
• The Helper:
I would like to see it again like Ghan had it the first time with pagination though - without the pagination that view will not work but with pagination it just might...
• The Helper:
This drink recipe I have had more than a few times back in the day! Mind Eraser https://www.thehelper.net/threads/cocktail-mind-eraser.194720/

### Members online

No members online now.