| 09-05-2011, 07:09 AM | #1 |
http://msdn.microsoft.com/en-us/libr...(v=vs.80).aspx  JASS:library AVL /* v1.0.0.0 ************************************************************************************* * * module AVLTree * * Interface: * method lessThan takes thistype value returns boolean * method greaterThan takes thistype value returns boolean * * readonly thistype root * - Root of two children (if root is 0, it's the tree's root) * readonly thistype left * readonly thistype right * readonly thistype down (tree pointer only) * - The tree has only 1 child, the root * readonly thistype value * - 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't exist, it will return the closest node to the value * - If the tree was empty, it will return the tree pointer * 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 thistype value returns nothing * - Deletes node if that node exists * method clear takes nothing returns nothing * - Clears the tree of all nodes * ************************************************************************************/ module AVL private static thistype c=0 //instance count private static thistype array b //root private static thistype array d //recycler 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 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 private method getHeight takes nothing returns integer if (h[l[this]]>h[r[this]]) then return h[l[this]]+1 endif return h[r[this]]+1 endmethod private method updateParent takes integer n, integer t returns nothing if (p[this]==t) then set b[t]=n elseif (l[p[this]]==this) then set l[p[this]]=n else set r[p[this]]=n endif set p[n]=p[this] endmethod private method finishRotate takes thistype n, integer t returns nothing call updateParent(n,t) set p[this]=n set h[this]=getHeight() set h[n]=n.getHeight() endmethod private method rotateLeft takes integer t returns thistype local thistype n=r[this] set r[this]=l[n] set p[l[n]]=this set l[n]=this call finishRotate(n,t) return n endmethod private method rotateRight takes integer t returns thistype local thistype n=l[this] set l[this]=r[n] set p[r[n]]=this set r[n]=this call finishRotate(n,t) return n endmethod 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==d[0]) then set n=c+1 set c=n else set n=d[0] set d[0]=d[n] endif set l[n]=0 set r[n]=0 set b[n]=0 set h[n]=1 return n endmethod static method create takes nothing returns thistype local integer n=allocate() set p[n]=0 return n endmethod private method balance takes integer t 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(t) endif set this=rotateRight(t) return elseif (-2==f) then if (1==r[this].getBalanceFactor()) then call r[this].rotateRight(t) endif set this=rotateLeft(t) return endif set this=p[this] endloop endmethod private method getBottom takes nothing returns thistype if (0!=r[this]) then set this=r[this] loop exitwhen 0==l[this] set this=l[this] endloop endif return this endmethod method search takes thistype val returns thistype if (0==b[this]) then return this endif set this=b[this] loop exitwhen v[this]==val if (val.lessThan(v[this])) then if (0==l[this]) then return this endif set this=l[this] else if (0==r[this]) then return this endif set this=r[this] endif endloop return this endmethod method has takes thistype val returns boolean return val==v[search(val)] endmethod method add takes thistype val returns thistype local thistype t=this local thistype n=search(val) if (val!=v[n]) then set this=allocate() set v[this]=val set p[this]=n if (0==p[n]) then set b[n]=this else if (val.lessThan(v[n])) then set l[n]=this else set r[n]=this endif set h[n]=n.getHeight() call p[n].balance(t) endif return this endif return n endmethod method delete takes thistype val returns nothing local thistype t=this local thistype n local thistype y set this=search(val) if (val==v[this]) then set n=getBottom() set y=p[n] call n.updateParent(r[n],t) set h[y]=y.getHeight() 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] call updateParent(n,t) set h[n]=h[this] call p[y].balance(t) set d[this]=d[0] set d[0]=this endif endmethod method clear takes nothing returns nothing set this=b[this] loop loop loop loop exitwhen 0==l[this] set this=l[this] endloop exitwhen 0==r[this] set this=r[this] endloop exitwhen 0==l[this] endloop exitwhen 0==p[this] set d[this]=d[0] set d[0]=this if (this==l[p[this]]) then set l[p[this]]=0 elseif (this==r[p[this]]) then set r[p[this]]=0 else set b[p[this]]=0 endif set this=p[this] endloop endmethod method destroy takes nothing returns nothing call clear() set d[this]=d[0] set d[0]=this endmethod endmodule endlibrary |
| 09-05-2011, 10:20 PM | #2 |
| 09-06-2011, 01:33 AM | #3 |
| 09-06-2011, 09:53 AM | #4 |
| 09-06-2011, 03:15 PM | #5 |
| 09-08-2011, 12:35 AM | #6 |
| 09-08-2011, 01:03 AM | #7 |
| 09-09-2011, 03:13 AM | #8 |