AA-Tree (self balancing binary tree)

Share your advanced PureBasic knowledge/code with the community.
Little John
Addict
Addict
Posts: 4519
Joined: Thu Jun 07, 2007 3:25 pm
Location: Berlin, Germany

Re: AA-Tree (self balancing binary tree) 1.10

Post by Little John »

Code: Select all

; Changes in version 1.10m:
; - Replaced in procedure names "AAT_" with "AAT::"
; - Replaced procedure name "New_AAT()" with "AAT::New()"
; - Replaced in constants "#AAT_" with "AAT::#"
; - Changed "#ASSERT_ENABLED = 1" into a comment

; TEST1
; will do some insertions
; will iterate through all items
; will delete all items

EnableExplicit

; #ASSERT_ENABLED = 1

XIncludeFile #PB_Compiler_FilePath + "AA_Tree.pbi"
XIncludeFile #PB_Compiler_FilePath + "TreeView.pb"

Define t = AAT::New()

Define key.String

Debug "> START INSERTING"

AAT::Insert (t, "LIMA")
AAT::Insert (t, "BETA")
AAT::Insert (t, "GAMMA")
AAT::Insert (t, "DELTA")
AAT::Insert (t, "ICS")
AAT::Insert (t, "IPSILON")
AAT::Insert (t, "TETA")
AAT::Insert (t, "MIKE")
AAT::Insert (t, "YOTA")
AAT::Insert (t, "ZULU")
AAT::Insert (t, "TANGO")
AAT::Insert (t, "ALFA")
AAT::Insert (t, "OSCAR")
AAT::Insert (t, "BRAVO")
AAT::Insert (t, "CHARLIE")
AAT::Insert (t, "KILO")
AAT::Insert (t, "ECHO")
AAT::Insert (t, "SIERRA")
AAT::Insert (t, "GOLF")
AAT::Insert (t, "JULIET")

Debug "Total nodes = " + Str(AAT::CountNodes(t))


Debug "> ENUMERATE NODES ASCENDING <"

AAT::EnumStart (t, AAT::#EnumAscending)
While AAT::EnumNext (t)
   Debug AAT::GetNodeKey(t)
Wend
AAT::EnumEnd(t)

TreeView(t)


Debug "> ENUMERATE NODES DESCENDING <"

AAT::EnumStart(t, AAT::#EnumDescending)
While AAT::EnumNext (t)
   Debug AAT::GetNodeKey(t)         
Wend
AAT::EnumEnd (t)

TreeView(t)


Debug "> START DELETING <"

AAT::Delete (t, "BETA")
AAT::Delete (t, "KILO")
AAT::Delete (t, "LIMA")
AAT::Delete (t, "OSCAR")
AAT::Delete (t, "BRAVO")
AAT::Delete (t, "GAMMA")
AAT::Delete (t, "DELTA")
AAT::Delete (t, "TETA")
AAT::Delete (t, "IPSILON")
AAT::Delete (t, "MIKE")
AAT::Delete (t, "YOTA")
AAT::Delete (t, "ZULU")
AAT::Delete (t, "TANGO")
AAT::Delete (t, "ALFA")
AAT::Delete (t, "ICS")
AAT::Delete (t, "SIERRA")
AAT::Delete (t, "CHARLIE")
AAT::Delete (t, "JULIET")
AAT::Delete (t, "ECHO")
AAT::Delete (t, "GOLF")

Debug "Total nodes = " + Str(AAT::CountNodes(t))

AAT::Clear (t)

AAT::Destroy (t)

Code: Select all

; Changes in version 1.10m:
; - Replaced in procedure names "AAT_" with "AAT::"
; - Replaced procedure name "New_AAT()" with "AAT::New()"
; - Changed "#ASSERT_ENABLED = 1" into a comment

; TEST2
; will do a lot of insertions
; will show the tree
; will do some deletions
; will show again the tree to verify it's still balanced

EnableExplicit

; #ASSERT_ENABLED = 1

XIncludeFile #PB_Compiler_FilePath + "AA_Tree.pbi"
XIncludeFile #PB_Compiler_FilePath + "TreeView.pb"

Define t = AAT::New()

Define k, key$

Procedure.s Fmt(val)
   ProcedureReturn RSet(Str(val),3,"0")
EndProcedure

Debug "> START INSERTING"

; to re-generate the same pseudorandom values for debugging
RandomSeed(123321) 

For k = 1 To 100 ; insert up to 100 random nodes
   key$ = Fmt(Random(100))
   
   If AAT::Insert (t, key$) ; 1 inserted, 0 already present
      Debug key$ + " inserted"
   EndIf
Next

Debug "Nodes inserted = " + Str (AAT::CountNodes(t))


TreeView (t)


For k = 1 To 100 ; now delete some of them (0 - 100)   
   key$ = Fmt(Random(100))
   
   If AAT::Delete (t, key$) ; 1 deleted, 0 not there
      Debug key$ + " deleted"       
   EndIf   
Next

Debug "Remaining nodes = " + Str (AAT::CountNodes(t))

TreeView (t)

AAT::Clear (t)

AAT::Destroy (t)

Code: Select all

; Changes in version 1.10m:
; - Replaced in procedure names "AAT_" with "AAT::"
; - Replaced procedure name "New_AAT()" with "AAT::New()"
; - Replaced in constants "#AAT_" with "AAT::#"
; - Changed "#ASSERT_ENABLED = 1" into a comment

; TEST3
; like TEST1 but using external data through a pointer

EnableExplicit

; #ASSERT_ENABLED = 1

XIncludeFile #PB_Compiler_FilePath + "AA_Tree.pbi"
XIncludeFile #PB_Compiler_FilePath + "TreeView.pb"

Structure T_MYDATA
   key.s   
   str1.s
   num1.i
EndStructure

Procedure.i AllocMyData (key.s, str1.s, num1)
   Protected *p.T_MYDATA = AllocateMemory(SizeOf(T_MYDATA))
   
   *p\key = key
   *p\str1 = str1
   *p\num1 = num1
   
   ProcedureReturn *p
EndProcedure

Define key.String
Define *item.T_MYDATA
Define t = AAT::New()

Debug "> START INSERTING"

AAT::Insert (t, "LIMA", AllocMyData("LIMA", "l1", 1))
AAT::Insert (t, "BETA", AllocMyData("BETA", "b1", 2))
AAT::Insert (t, "GAMMA", AllocMyData("GAMMA", "g1", 3))
AAT::Insert (t, "DELTA", AllocMyData("DELTA", "d1", 4))
AAT::Insert (t, "ICS", AllocMyData("ICS", "i1", 5))
AAT::Insert (t, "IPSILON", AllocMyData("IPSILON", "i2", 6))
AAT::Insert (t, "TETA", AllocMyData("TETA", "t2", 7))
AAT::Insert (t, "MIKE", AllocMyData("MIKE", "m1", 8))
AAT::Insert (t, "YOTA", AllocMyData("YOTA", "y1", 9))
AAT::Insert (t, "ZULU", AllocMyData("ZULU", "z1", 10))
AAT::Insert (t, "TANGO", AllocMyData("TANGO", "t1", 11))
AAT::Insert (t, "ALFA", AllocMyData("ALFA", "a1", 12))
AAT::Insert (t, "OSCAR", AllocMyData("OSCAR", "o1", 13))
AAT::Insert (t, "BRAVO", AllocMyData("BRAVO", "b2", 14))
AAT::Insert (t, "CHARLIE", AllocMyData("CHARLIE", "c1", 15))
AAT::Insert (t, "KILO", AllocMyData("KILO", "k1", 16))
AAT::Insert (t, "ECHO", AllocMyData("ECHO", "e1", 17))
AAT::Insert (t, "SIERRA", AllocMyData("SIERRA", "s1", 18))
AAT::Insert (t, "GOLF", AllocMyData("GOLF", "g2", 19))
AAT::Insert (t, "JULIET", AllocMyData("JULIET", "j1", 20))

Debug "Total nodes = " + Str(AAT::CountNodes(t))

Debug "> ENUMERATE NODES ASCENDING <"

AAT::EnumStart (t, AAT::#EnumAscending)
While AAT::EnumNext (t)
   *item = AAT::GetNodeValue(t)
   Debug AAT::GetNodeKey(t) + " , " + *item\str1 + ", " + *item\num1
Wend
AAT::EnumEnd(t)

TreeView(t)

Debug "> ENUMERATE NODES DESCENDING <"

AAT::EnumStart(t, AAT::#EnumDescending)
While AAT::EnumNext (t)
   *item = AAT::GetNodeValue(t)
   Debug AAT::GetNodeKey(t) + " , " + *item\str1 + ", " + *item\num1
Wend
AAT::EnumEnd (t)

TreeView(t)

Debug "> START DELETING <"

; delete the item from the tree
AAT::Delete (t, "BETA", @*item)
; manually deallocate the associated data
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "KILO", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "LIMA", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "OSCAR", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "BRAVO", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "GAMMA", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "DELTA", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "TETA", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "IPSILON", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "MIKE", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "YOTA", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "ZULU", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "TANGO", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "ALFA", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "ICS", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "SIERRA", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "CHARLIE", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "JULIET", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "ECHO", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

AAT::Delete (t, "GOLF", @*item)
ClearStructure(*item, T_MYDATA) : FreeMemory(*item)

Debug "Total nodes = " + Str(AAT::CountNodes(t))

AAT::Clear (t)

AAT::Destroy (t)

Code: Select all

; Changes in version 1.10m:
; - Replaced in procedure names "AAT_" with "AAT::"
; - Replaced procedure name "New_AAT()" with "AAT::New()"
; - Replaced in constants "#AAT_" with "AAT::#"
; - Changed "#ASSERT_ENABLED = 1" into a comment

; TEST4
; like TEST3 but using a callback to automate external data deallocation

EnableExplicit

; #ASSERT_ENABLED = 1

XIncludeFile #PB_Compiler_FilePath + "AA_Tree.pbi"
XIncludeFile #PB_Compiler_FilePath + "TreeView.pb"

Structure T_MYDATA
   key.s   
   str1.s
   num1.i
EndStructure

Procedure FreeMyData (*item.T_MYDATA)
   Debug "Freeing -> " + *item\key 
   ClearStructure(*item, T_MYDATA) : FreeMemory(*item)
EndProcedure

Procedure.i AllocMyData (key.s, str1.s, num1)
   Protected *p.T_MYDATA = AllocateMemory(SizeOf(T_MYDATA))
   
   *p\key = key
   *p\str1 = str1
   *p\num1 = num1
   
   ProcedureReturn *p
EndProcedure

Define key.String
Define *item.T_MYDATA
Define t = AAT::New (@FreeMyData()) ; using a callback

Debug "> START INSERTING"

AAT::Insert (t, "LIMA", AllocMyData("LIMA", "l1", 1))
AAT::Insert (t, "BETA", AllocMyData("BETA", "b1", 2))
AAT::Insert (t, "GAMMA", AllocMyData("GAMMA", "g1", 3))
AAT::Insert (t, "DELTA", AllocMyData("DELTA", "d1", 4))
AAT::Insert (t, "ICS", AllocMyData("ICS", "i1", 5))
AAT::Insert (t, "IPSILON", AllocMyData("IPSILON", "i2", 6))
AAT::Insert (t, "TETA", AllocMyData("TETA", "t2", 7))
AAT::Insert (t, "MIKE", AllocMyData("MIKE", "m1", 8))
AAT::Insert (t, "YOTA", AllocMyData("YOTA", "y1", 9))
AAT::Insert (t, "ZULU", AllocMyData("ZULU", "z1", 10))
AAT::Insert (t, "TANGO", AllocMyData("TANGO", "t1", 11))
AAT::Insert (t, "ALFA", AllocMyData("ALFA", "a1", 12))
AAT::Insert (t, "OSCAR", AllocMyData("OSCAR", "o1", 13))
AAT::Insert (t, "BRAVO", AllocMyData("BRAVO", "b2", 14))
AAT::Insert (t, "CHARLIE", AllocMyData("CHARLIE", "c1", 15))
AAT::Insert (t, "KILO", AllocMyData("KILO", "k1", 16))
AAT::Insert (t, "ECHO", AllocMyData("ECHO", "e1", 17))
AAT::Insert (t, "SIERRA", AllocMyData("SIERRA", "s1", 18))
AAT::Insert (t, "GOLF", AllocMyData("GOLF", "g2", 19))
AAT::Insert (t, "JULIET", AllocMyData("JULIET", "j1", 20))

Debug "Total nodes = " + Str(AAT::CountNodes(t))


Debug "> ENUMERATE NODES ASCENDING <"

AAT::EnumStart (t, AAT::#EnumAscending)
While AAT::EnumNext (t)
   *item = AAT::GetNodeValue(t)
   Debug AAT::GetNodeKey(t) + " , " + *item\str1 + ", " + *item\num1
Wend
AAT::EnumEnd(t)

TreeView(t)


Debug "> ENUMERATE NODES DESCENDING <"

AAT::EnumStart(t, AAT::#EnumDescending)
While AAT::EnumNext (t)
   *item = AAT::GetNodeValue(t)
   Debug AAT::GetNodeKey(t) + " , " + *item\str1 + ", " + *item\num1
Wend
AAT::EnumEnd (t)

TreeView(t)


Debug "> START DELETING <"

AAT::Delete (t, "BETA") ; automatic deallocation of the user data through the callback
AAT::Delete (t, "KILO")
AAT::Delete (t, "LIMA")
AAT::Delete (t, "OSCAR")
AAT::Delete (t, "BRAVO")
AAT::Delete (t, "GAMMA")
AAT::Delete (t, "DELTA")
AAT::Delete (t, "TETA")
AAT::Delete (t, "IPSILON")
AAT::Delete (t, "MIKE")
AAT::Delete (t, "YOTA")
AAT::Delete (t, "ZULU")
AAT::Delete (t, "TANGO")
AAT::Delete (t, "ALFA")
AAT::Delete (t, "ICS")
AAT::Delete (t, "SIERRA")
AAT::Delete (t, "CHARLIE")
AAT::Delete (t, "JULIET")
AAT::Delete (t, "ECHO")
AAT::Delete (t, "GOLF")

Debug "Total nodes = " + Str(AAT::CountNodes(t))

AAT::Clear (t) ; even this will use the callback if there are nodes in the tree (comment out some ATT_Delete() above)

AAT::Destroy (t) ; and this one too

Code: Select all

; Changes in version 1.10m:
; - Replaced in procedure names "AAT_" with "AAT::"
; - Replaced procedure name "New_AAT()" with "AAT::New()"
; - Changed "#ASSERT_ENABLED = 1" into a comment

; TEST5
; test insertion (with error reported when key duplicated)
; seek back all the keys inserted in the tree

EnableExplicit

; #ASSERT_ENABLED = 1

XIncludeFile #PB_Compiler_FilePath + "AA_Tree.pbi"
XIncludeFile #PB_Compiler_FilePath + "TreeView.pb"

#ITEMS = 50

Define t = AAT::New()

Define k, key$

Procedure.s KeyGen()
   ProcedureReturn RSet(Str(Random(99)),2,"0")
EndProcedure

Dim items$(#ITEMS - 1)

Debug "> START INSERTING <"

; to re-generate the same pseudorandom values for debugging enable this:
; RandomSeed(123321) 

For k = 0 To #ITEMS - 1 ; insert up to #ITEMS random nodes
   key$ = KeyGen()
   items$(k) = key$
   
   If AAT::Insert (t, key$) ; 1 inserted, 0 already present
      Debug key$ + " inserted"
   Else
      Debug key$ + " NOT inserted (already there)"
   EndIf
Next

Debug "Nodes inserted = " + Str (AAT::CountNodes(t))


Debug "> START SEARCHING <"

For k = 0 To #ITEMS - 1 ; now search for each one
   key$ = items$(k)   
   
   If AAT::Search(t, key$) ; 1 found, 0 not there
      Debug key$ + " found (pathlen = " + AAT::GetLastPathLength(t) + ")"
   Else
      Debug key$ + " NOT found !!!"
   EndIf   
Next

TreeView(t)

AAT::Clear (t)

Debug "nodes = " + Str (AAT::CountNodes(t))

AAT::Destroy (t)

Code: Select all

; Changes in version 1.10m:
; - Replaced in procedure names "AAT_" with "AAT::"
; - Replaced procedure name "New_AAT()" with "AAT::New()"
; - Replaced in constants "#AAT_" with "AAT::#"
; - Changed "#ASSERT_ENABLED = 1" into a comment

; TEST6
; will do some insertions
; will iterate through all items
; will iterate through the items below a specific node (subtree)
; will manually navigate from a specific node or from the root

EnableExplicit

; #ASSERT_ENABLED = 1

XIncludeFile #PB_Compiler_FilePath + "AA_Tree.pbi"
XIncludeFile #PB_Compiler_FilePath + "TreeView.pb"

Define t = AAT::New()

Define key.String

Debug "> START INSERTING"

AAT::Insert (t, "LIMA")
AAT::Insert (t, "BETA")
AAT::Insert (t, "GAMMA")
AAT::Insert (t, "DELTA")
AAT::Insert (t, "ICS")
AAT::Insert (t, "IPSILON")
AAT::Insert (t, "TETA")
AAT::Insert (t, "MIKE")
AAT::Insert (t, "YOTA")
AAT::Insert (t, "ZULU")
AAT::Insert (t, "TANGO")
AAT::Insert (t, "ALFA")
AAT::Insert (t, "OSCAR")
AAT::Insert (t, "BRAVO")
AAT::Insert (t, "CHARLIE")
AAT::Insert (t, "KILO")
AAT::Insert (t, "ECHO")
AAT::Insert (t, "SIERRA")
AAT::Insert (t, "GOLF")
AAT::Insert (t, "JULIET")


Debug "Total nodes = " + Str(AAT::CountNodes(t))


Debug "> ENUMERATE NODES ASCENDING (STANDARD FROM THE ROOT) <"

AAT::EnumStart (t, AAT::#EnumAscending)

While AAT::EnumNext (t)
   Debug AAT::GetNodeKey(t) + " (" + AAT::GetNodeValue(t) + ")"; value not used in this example
Wend

AAT::EnumEnd(t)

TreeView(t)

Debug "> ENUMERATE NODES ASCENDING FROM A SPECIFIC NODE: 'GAMMA' <"

If AAT::Search(t, "GAMMA") ; from this node
   AAT::EnumStartFromCurrent(t, AAT::#EnumAscending)
   
   While AAT::EnumNext (t)
      Debug AAT::GetNodeKey(t) + " (" + AAT::GetNodeValue(t) + ")"; value not used in this example
   Wend
   
   AAT::EnumEnd(t)
   
   TreeView(t)
EndIf

Debug "> NAVIGATION DOWN AND RIGHT FROM A SPECIFIC NODE: 'KILO' <"

If AAT::Search(t, "KILO") ; from this node
   Debug AAT::GetNodeKey(t)
   
   While AAT::GoRight(t) ; always to the right
      Debug AAT::GetNodeKey(t)
   Wend
   
   TreeView(t)
EndIf

Debug "> NAVIGATION DOWN AND LEFT FROM THE ROOT <"

If AAT::GoRoot(t) ; from the root
   Debug AAT::GetNodeKey(t)
   
   While AAT::GoLeft(t) ; always to the left
      Debug AAT::GetNodeKey(t)
   Wend
EndIf

TreeView(t)

AAT::Clear (t)

AAT::Destroy (t)
User avatar
luis
Addict
Addict
Posts: 3876
Joined: Wed Aug 31, 2005 11:09 pm
Location: Italy

Re: AA-Tree (self balancing binary tree) 1.20

Post by luis »

New version.
"Have you tried turning it off and on again ?"
A little PureBasic review
User avatar
Kwai chang caine
Always Here
Always Here
Posts: 5342
Joined: Sun Nov 05, 2006 11:42 pm
Location: Lyon - France

Re: AA-Tree (self balancing binary tree) 1.20

Post by Kwai chang caine »

Very nice work LUIS
Thanks for sharing 8)
ImageThe happiness is a road...
Not a destination
Post Reply