AVL Tree

Share your advanced PureBasic knowledge/code with the community.
Post Reply
DarkDragon
Addict
Addict
Posts: 2344
Joined: Mon Jun 02, 2003 9:16 am
Location: Germany
Contact:
Contact DarkDragon

AVL Tree

Post by DarkDragon »

Hello,

I've made an avl tree as an excercise at the university and I ported the code to purebasic now. There were some restrictions like: we don't have a pointer to the parent node within a node which made everything a bit harder. But finally it works now. You shouldn't use the draw routine as it was just a debug routine for me but I didn't delete it to show you that reorganisation works quite well.

Code: Select all

; Author:  Daniel Brall (DarkDragon/Bradan)
; Website: http://www.bradan.eu/
;
; Desc.:   This implements an AVL tree for PureBasic.
; Note:    Its heavy to do this without direct knowledge of the parentnode
;          within a node but I made it (it was an excercise for the university).

EnableExplicit

;##############################################################################################################

Procedure.i MaxI(a.i, b.i)
  If a >= b
    ProcedureReturn a
  EndIf

  ProcedureReturn b
EndProcedure

Procedure.i MinI(a.i, b.i)
  If a <= b
    ProcedureReturn a
  EndIf

  ProcedureReturn b
EndProcedure

;##############################################################################################################

Prototype.d ComparatorFunction(*ValueA, *ValueB)

;##############################################################################################################

Interface TreeNode
  SetValue(*Value)
  GetValue.i()

  SetHeight(Height.i)
  GetHeight.i()

  SetLeftChild(*Child.TreeNode)
  SetRightChild(*Child.TreeNode)

  GetLeftChild.i()
  GetRightChild.i()
EndInterface

Structure TreeNodeObject
  *VTable
  *Functions[SizeOf(TreeNode) / SizeOf(Integer)]

  *Value
  Height.i
  *Left.TreeNode
  *Right.TreeNode
EndStructure

Procedure TreeNodeSetValue(*This.TreeNodeObject, *Value)
  *This\Value = *Value
EndProcedure

Procedure.i TreeNodeGetValue(*This.TreeNodeObject)
  ProcedureReturn *This\Value
EndProcedure

Procedure TreeNodeSetHeight(*This.TreeNodeObject, Height)
  If Height > 0
    *This\Height = Height
  Else
    Debug "Error: Height <= 0"
  EndIf
EndProcedure

Procedure.i TreeNodeGetHeight(*This.TreeNodeObject)
  ProcedureReturn *This\Height
EndProcedure

Procedure TreeNodeSetLeftChild(*This.TreeNodeObject, *Child.TreeNode)
  *This\Left = *Child
EndProcedure

Procedure.i TreeNodeGetLeftChild(*This.TreeNodeObject)
  ProcedureReturn *This\Left
EndProcedure

Procedure TreeNodeSetRightChild(*This.TreeNodeObject, *Child.TreeNode)
  *This\Right = *Child
EndProcedure

Procedure.i TreeNodeGetRightChild(*This.TreeNodeObject)
  ProcedureReturn *This\Right
EndProcedure

Procedure TreeNodeConstruct()
  Protected *object.TreeNodeObject

  *object = AllocateMemory(SizeOf(TreeNodeObject))
  If *object
    *object\VTable = @*object\Functions[0]

    CopyMemory(?TreeNodeFunctionsStart, *object\VTable, ?TreeNodeFunctionsEnd - ?TreeNodeFunctionsStart)

    *object\Value   = 0
    *object\Height  = 1
    *object\Left    = 0
    *object\Right   = 0
  EndIf

  ProcedureReturn *object

  DataSection
    TreeNodeFunctionsStart:
    Data.i @TreeNodeSetValue()
    Data.i @TreeNodeGetValue()
    Data.i @TreeNodeSetHeight()
    Data.i @TreeNodeGetHeight()
    Data.i @TreeNodeSetLeftChild()
    Data.i @TreeNodeSetRightChild()
    Data.i @TreeNodeGetLeftChild()
    Data.i @TreeNodeGetRightChild()
    TreeNodeFunctionsEnd:
  EndDataSection
EndProcedure

;##############################################################################################################

Interface AVLTree
  Contains.i(*Value)

  Delete(*Value)
  Insert(*Value)

  GetNodeCount.i()
  GetHeight.i()

  Inorder(*OrderArray.Integer, ArrayElements.i)
  Preorder(*OrderArray.Integer, ArrayElements.i)
  Postorder(*OrderArray.Integer, ArrayElements.i)

  Draw(X, Y, Scale.d) ; This is just a debug routine for the tree.
EndInterface

Structure AVLTreeObject
  *VTable
  *Functions[SizeOf(AVLTree) / SizeOf(Integer)]

  *Comparator.ComparatorFunction
  *Root.TreeNode
  NodeCount.i
EndStructure

; Private

Procedure.i AVLTreePrivateRotateLeft(*Node.TreeNode)
  Protected *Child.TreeNode
  Protected *NewNode.TreeNode
  Protected Height.i

  If *Node <> 0
    *NewNode = *Node\GetRightChild()
    If *NewNode <> 0
      ; the left tree of the right child is now the right tree of the root
      *Node\SetRightChild(*NewNode\GetLeftChild())
      *NewNode\SetLeftChild(*Node)

      ; recalculate the height of the deeper node first:
      Height = 0
      *Child = *Node\GetLeftChild()
      If *Child <> 0
        Height = *Child\GetHeight()
      EndIf
      *Child = *Node\GetRightChild()
      If *Child <> 0
        Height = MaxI(Height, *Child\GetHeight())
      EndIf
      ; the height is max(leftHeight, rightHeight) + 1
      *Node\SetHeight(Height + 1)

      ; recalculate the height of the higher node now:
      Height = 0
      *Child = *NewNode\GetLeftChild()
      If *Child <> 0
        Height = *Child\GetHeight()
      EndIf
      *Child = *NewNode\GetRightChild()
      If *Child <> 0
        Height = MaxI(Height, *Child\GetHeight())
      EndIf
      ; the height is max(leftHeight, rightHeight) + 1
      *NewNode\SetHeight(Height + 1)

    Else
      ; we can't rotate anymore
      *NewNode = *Node
    EndIf
  EndIf

  ProcedureReturn *NewNode
EndProcedure

Procedure.i AVLTreePrivateRotateRight(*Node.TreeNode)
  Protected *Child.TreeNode
  Protected *NewNode.TreeNode
  Protected Height.i

  If *Node <> 0
    *NewNode = *Node\GetLeftChild()
    If *NewNode <> 0
      ; the right tree of the left child is now the left tree of the root
      *Node\SetLeftChild(*NewNode\GetRightChild())
      *NewNode\SetRightChild(*Node)

      ; recalculate the height of the deeper node first:
      Height = 0
      *Child = *Node\GetLeftChild()
      If *Child <> 0
        Height = *Child\GetHeight()
      EndIf
      *Child = *Node\GetRightChild()
      If *Child <> 0
        Height = MaxI(Height, *Child\GetHeight())
      EndIf
      ; the height is max(leftHeight, rightHeight) + 1
      *Node\SetHeight(Height + 1)

      ; recalculate the height of the higher node now:
      Height = 0
      *Child = *NewNode\GetLeftChild()
      If *Child <> 0
        Height = *Child\GetHeight()
      EndIf
      *Child = *NewNode\GetRightChild()
      If *Child <> 0
        Height = MaxI(Height, *Child\GetHeight())
      EndIf
      ; the height is max(leftHeight, rightHeight) + 1
      *NewNode\SetHeight(Height + 1)

    Else
      ; we can't rotate anymore
      *NewNode = *Node
    EndIf
  EndIf

  ProcedureReturn *NewNode
EndProcedure

Procedure.i AVLTreePrivateNodeBalance(*Node.TreeNode)
  Protected *Child.TreeNode
  Protected LeftHeight.i
  Protected RightHeight.i

  LeftHeight  = 0
  RightHeight = 0

  If *Node <> 0
    *Child = *Node\GetLeftChild()
    If *Child <> 0
      LeftHeight = *Child\GetHeight()
    EndIf

    *Child = *Node\GetRightChild()
    If *Child <> 0
      RightHeight = *Child\GetHeight()
    EndIf
  EndIf

  ProcedureReturn LeftHeight - RightHeight
EndProcedure

Declare AVLTreePrivateDeleteRecursive(*This.AVLTreeObject, *Value, *Node.TreeNode, *Parent.TreeNode)

Procedure AVLTreePrivateRebalanceNode(*This.AVLTreeObject, *Node.TreeNode, *Parent.TreeNode)
  Protected *LeftChild.TreeNode
  Protected *RightChild.TreeNode
  Protected Balance.i

  *LeftChild  = *Node\GetLeftChild()
  *RightChild = *Node\GetRightChild()

  Balance = AVLTreePrivateNodeBalance(*Node)

  If Balance < -1
    If AVLTreePrivateNodeBalance(*RightChild) > 0
      *Node\SetRightChild(AVLTreePrivateRotateRight(*Node\GetRightChild()))
    EndIf

    If *Parent <> 0
      If *Parent\GetLeftChild() = *Node
        *Node = AVLTreePrivateRotateLeft(*Node)
        *Parent\SetLeftChild(*Node)
      ElseIf *Parent\GetRightChild() = *Node
        *Node = AVLTreePrivateRotateLeft(*Node)
        *Parent\SetRightChild(*Node)
      EndIf
    Else
      *Node = AVLTreePrivateRotateLeft(*Node)
      *This\Root = *Node
    EndIf
  ElseIf Balance > 1
    If AVLTreePrivateNodeBalance(*LeftChild) < 0
      *Node\SetLeftChild(AVLTreePrivateRotateLeft(*Node\GetLeftChild()))
    EndIf

    If *Parent <> 0
      If *Parent\GetLeftChild() = *Node
        *Node = AVLTreePrivateRotateRight(*Node)
        *Parent\SetLeftChild(*Node)
      ElseIf *Parent\GetRightChild() = *Node
        *Node = AVLTreePrivateRotateRight(*Node)
        *Parent\SetRightChild(*Node)
      EndIf
    Else
      *Node = AVLTreePrivateRotateRight(*Node)
      *This\Root = *Node
    EndIf
  EndIf
EndProcedure

Procedure AVLTreePrivateDeleteNode(*This.AVLTreeObject, *Node.TreeNode, *Parent.TreeNode)
  Protected *IThis.AVLTree = *This
  Protected *MaxNode.TreeNode
  Protected *LeftChild.TreeNode
  Protected *RightChild.TreeNode

  If *Node <> 0
    If *Node\GetLeftChild() <> 0

      If *Node\GetRightChild() <> 0

        ; find a maximum element in the left tree
        *MaxNode = *Node\GetLeftChild()
        While *MaxNode\GetRightChild() <> 0
          *MaxNode = *MaxNode\GetRightChild()
        Wend

        ; now move its contents to the current node and delete that tree instead
        *Node\SetValue(*MaxNode\GetValue())

        *LeftChild = *Node\GetLeftChild()
        *RightChild = *Node\GetRightChild()

        If *LeftChild\GetHeight() > *RightChild\GetHeight()
          *Node\SetHeight(*Node\GetHeight() - 1)
        EndIf

        ; delete the maximum node instead
        AVLTreePrivateDeleteRecursive(*This, *MaxNode\GetValue(), *Node\GetLeftChild(), *Node)

        ; Check if we need to rebalance the node as we had a left and a right child
        AVLTreePrivateRebalanceNode(*This, *Node, *Parent)

      Else

        ; Just move the left child upwards
        If *Parent <> 0
          If *This\Comparator(*Node\GetValue(), *Parent\GetValue()) <= 0
            *Parent\SetLeftChild(*Node\GetLeftChild())
          Else
            *Parent\SetRightChild(*Node\GetLeftChild())
          EndIf
        Else
          *This\Root = *Node\GetLeftChild()
        EndIf
        ; We have deleted a node, so decrement the amount of nodes
        *This\NodeCount - 1

      EndIf

    Else

      ; Just move the right child upwards
      If *Parent <> 0
        If *This\Comparator(*Node\GetValue(), *Parent\GetValue()) <= 0
          *Parent\SetLeftChild(*Node\GetRightChild())
        Else
          *Parent\SetRightChild(*Node\GetRightChild())
        EndIf
      Else
        *This\Root = *Node\GetRightChild()
      EndIf
      ; We have deleted a node, so decrement the amount of nodes
      *This\NodeCount - 1

    EndIf
  EndIf
EndProcedure

Procedure AVLTreePrivateDeleteRecursive(*This.AVLTreeObject, *Value, *Node.TreeNode, *Parent.TreeNode)
  Protected *LeftChild.TreeNode
  Protected *RightChild.TreeNode

  If *Node <> 0
    If *This\Comparator(*Value, *Node\GetValue()) < 0

      AVLTreePrivateDeleteRecursive(*This, *Value, *Node\GetLeftChild(), *Node)

      ; Set the new height
      *LeftChild  = *Node\GetLeftChild()
      *RightChild = *Node\GetRightChild()
      If *LeftChild <> 0
        If *RightChild <> 0
          *Node\SetHeight(MaxI(*LeftChild\GetHeight(), *RightChild\GetHeight()) + 1)
        Else
          *Node\SetHeight(*LeftChild\GetHeight() + 1)
        EndIf
      Else
        If *RightChild <> 0
          *Node\SetHeight(*RightChild\GetHeight() + 1)
        Else
          *Node\SetHeight(1)
        EndIf
      EndIf

      ; Check if we need to rebalance the node
      AVLTreePrivateRebalanceNode(*This, *Node, *Parent)

    ElseIf *This\Comparator(*Value, *Node\GetValue()) > 0

      AVLTreePrivateDeleteRecursive(*This, *Value, *Node\GetRightChild(), *Node)

      ; Set the new height
      *LeftChild  = *Node\GetLeftChild()
      *RightChild = *Node\GetRightChild()
      If *LeftChild <> 0
        If *RightChild <> 0
          *Node\SetHeight(MaxI(*LeftChild\GetHeight(), *RightChild\GetHeight()) + 1)
        Else
          *Node\SetHeight(*LeftChild\GetHeight() + 1)
        EndIf
      Else
        If *RightChild <> 0
          *Node\SetHeight(*RightChild\GetHeight() + 1)
        Else
          *Node\SetHeight(1)
        EndIf
      EndIf

      ; Check if we need to rebalance the node
      AVLTreePrivateRebalanceNode(*This, *Node, *Parent)

    Else

      ; We have found the node to remove, so remove it now within the subroutine
      AVLTreePrivateDeleteNode(*This, *Node, *Parent)
    EndIf
  EndIf
EndProcedure

Procedure AVLTreePrivateInsertRecursive(*This.AVLTreeObject, *Value, *Node.TreeNode, *Parent.TreeNode)
  Protected *LeftChild.TreeNode
  Protected *RightChild.TreeNode
  Protected *NewNode.TreeNode

  If *Node <> 0

    If *This\Comparator(*Value, *Node\GetValue()) < 0

      AVLTreePrivateInsertRecursive(*This, *Value, *Node\GetLeftChild(), *Node)

      *LeftChild = *Node\GetLeftChild()
      *RightChild = *Node\GetRightChild()

      ; Set the new height
      If *RightChild <> 0
        *Node\SetHeight(MaxI(*LeftChild\GetHeight(), *RightChild\GetHeight()) + 1)
      Else
        *Node\SetHeight(*LeftChild\GetHeight() + 1)
      EndIf

      ; Check if we need to rebalance the node
      AVLTreePrivateRebalanceNode(*This, *Node, *Parent)

    Else

      AVLTreePrivateInsertRecursive(*This, *Value, *Node\GetRightChild(), *Node)

      *LeftChild = *Node\GetLeftChild()
      *RightChild = *Node\GetRightChild()

      ; Set the new height
      If *LeftChild <> 0
        *Node\SetHeight(MaxI(*LeftChild\GetHeight(), *RightChild\GetHeight()) + 1)
      Else
        *Node\SetHeight(*RightChild\GetHeight() + 1)
      EndIf

      ; Check if we need to rebalance the node
      AVLTreePrivateRebalanceNode(*This, *Node, *Parent)

    EndIf

  Else

    *NewNode = TreeNodeConstruct()
    *NewNode\SetValue(*Value)
    *NewNode\SetHeight(1)

    If *Parent <> 0

      If *This\Comparator(*Value, *Parent\GetValue()) < 0
        *Parent\SetLeftChild(*NewNode)
      Else
        *Parent\SetRightChild(*NewNode)
      EndIf

    Else

      *This\Root = *NewNode

    EndIf

    *This\NodeCount + 1

  EndIf
EndProcedure

Procedure AVLTreePrivateDrawNode(*Node.TreeNode, X, Y, OldX, OldY, Scale.d)
  If *Node <> 0
    LineXY(X, Y, OldX, OldY, RGB(128, 128, 128))
    If Abs(AVLTreePrivateNodeBalance(*Node)) > 1
      DrawText(X - 10, Y, Str(*Node\GetValue()) + " (" + Str(*Node\GetHeight()) + ")", RGB(255, 0, 0), RGB(255, 255, 255))
    Else
      DrawText(X - 10, Y, Str(*Node\GetValue()) + " (" + Str(*Node\GetHeight()) + ")", RGB(0, 0, 0), RGB(255, 255, 255))
    EndIf

    AVLTreePrivateDrawNode(*Node\GetLeftChild(), X - (100 * Scale), Y + 70, X, Y + 20, Scale * 0.5)
    AVLTreePrivateDrawNode(*Node\GetRightChild(), X + (100 * Scale), Y + 70, X, Y + 20, Scale * 0.5)
  EndIf
EndProcedure

Procedure AVLTreePrivateInorder(*Node.TreeNode, *OrderArray.Integer, ArrayElements.i, Index)
  If *Node <> 0
    Index = AVLTreePrivateInorder(*Node\GetLeftChild(), *OrderArray, ArrayElements, Index)

    If Index < ArrayElements
      PokeI(*OrderArray + Index * SizeOf(Integer), *Node\GetValue())
      Index + 1

      If Index < ArrayElements
        Index = AVLTreePrivateInorder(*Node\GetRightChild(), *OrderArray, ArrayElements, Index)
      EndIf
    EndIf
  EndIf

  ProcedureReturn Index
EndProcedure

Procedure AVLTreePrivatePreorder(*Node.TreeNode, *OrderArray.Integer, ArrayElements.i, Index)
  If *Node <> 0
    PokeI(*OrderArray + Index * SizeOf(Integer), *Node\GetValue())
    Index + 1

    If Index < ArrayElements
      Index = AVLTreePrivateInorder(*Node\GetLeftChild(), *OrderArray, ArrayElements, Index)

      If Index < ArrayElements
        Index = AVLTreePrivateInorder(*Node\GetRightChild(), *OrderArray, ArrayElements, Index)
      EndIf
    EndIf
  EndIf

  ProcedureReturn Index
EndProcedure

Procedure AVLTreePrivatePostorder(*Node.TreeNode, *OrderArray.Integer, ArrayElements.i, Index)
  If *Node <> 0
    Index = AVLTreePrivatePostorder(*Node\GetLeftChild(), *OrderArray, ArrayElements, Index)

    If Index < ArrayElements
      Index = AVLTreePrivatePostorder(*Node\GetRightChild(), *OrderArray, ArrayElements, Index)

      If Index < ArrayElements
        PokeI(*OrderArray + Index * SizeOf(Integer), *Node\GetValue())
        Index + 1
      EndIf
    EndIf
  EndIf

  ProcedureReturn Index
EndProcedure

; Public

Procedure.i AVLTreeContains(*This.AVLTreeObject, *Value)
  Protected *Node.TreeNode
  Protected Result = 0
  Protected CompareResult.d

  *Node = *This\Root
  While *Node <> 0
    CompareResult = *This\Comparator(*Value, *Node\GetValue())
    If CompareResult < 0
      *Node = *Node\GetLeftChild()
    ElseIf CompareResult > 0
      *Node = *Node\GetRightChild()
    Else
      Result = 1
      Break
    EndIf
  Wend

  ProcedureReturn Result
EndProcedure

Procedure AVLTreeDelete(*This.AVLTreeObject, *Value)
  AVLTreePrivateDeleteRecursive(*This, *Value, *This\Root, 0)
EndProcedure

Procedure AVLTreeInsert(*This.AVLTreeObject, *Value)
  Protected *IThis.AVLTree = *This

  If *IThis\Contains(*Value) = 0
    AVLTreePrivateInsertRecursive(*This, *Value, *This\Root, 0)
  EndIf
EndProcedure

Procedure.i AVLTreeGetNodeCount(*This.AVLTreeObject)
  ProcedureReturn *This\NodeCount
EndProcedure

Procedure.i AVLTreeGetHeight(*This.AVLTreeObject)
  If *This\Root <> 0
    ProcedureReturn *This\Root\GetHeight()
  EndIf

  ProcedureReturn 0
EndProcedure

Procedure AVLTreeInorder(*This.AVLTreeObject, *OrderArray.Integer, ArrayElements.i)
  AVLTreePrivateInorder(*This\Root, *OrderArray, ArrayElements, 0)
EndProcedure

Procedure AVLTreePreorder(*This.AVLTreeObject, *OrderArray.Integer, ArrayElements.i)
  AVLTreePrivatePreorder(*This\Root, *OrderArray, ArrayElements, 0)
EndProcedure

Procedure AVLTreePostorder(*This.AVLTreeObject, *OrderArray.Integer, ArrayElements.i)
  AVLTreePrivatePostorder(*This\Root, *OrderArray, ArrayElements, 0)
EndProcedure

Procedure AVLTreeDraw(*This.AVLTreeObject, X, Y, Scale.d)
  AVLTreePrivateDrawNode(*This\Root, X, Y, X, Y, Scale)
EndProcedure

Procedure AVLTreeConstruct(*Comparator.ComparatorFunction)
  Protected *object.AVLTreeObject

  If *Comparator <> 0
    *object = AllocateMemory(SizeOf(AVLTreeObject))
    If *object
      *object\VTable = @*object\Functions[0]

      CopyMemory(?AVLTreeFunctionsStart, *object\VTable, ?AVLTreeFunctionsEnd - ?AVLTreeFunctionsStart)

      *object\Comparator = *Comparator
      *object\Root = 0
      *object\NodeCount = 0
    EndIf
  EndIf

  ProcedureReturn *object

  DataSection
    AVLTreeFunctionsStart:
    Data.i @AVLTreeContains()
    Data.i @AVLTreeDelete()
    Data.i @AVLTreeInsert()
    Data.i @AVLTreeGetNodeCount()
    Data.i @AVLTreeGetHeight()
    Data.i @AVLTreeInorder()
    Data.i @AVLTreePreorder()
    Data.i @AVLTreePostorder()
    Data.i @AVLTreeDraw()
    AVLTreeFunctionsEnd:
  EndDataSection
EndProcedure

;##############################################################################################################
;# Example Program                                                                                            #
;##############################################################################################################

Procedure.d IntegerComparator(*a, *b)
  ProcedureReturn *a - *b
EndProcedure

Define *Tree.AVLTree

OpenWindow(0, 0, 0, 1000, 500, "Test")

SmartWindowRefresh(0, 1)

*Tree = AVLTreeConstruct(@IntegerComparator())

CreateImage(0, 2200, 800)

If *Tree <> 0

  Define k.i
  Define Number.i

  *Tree\Insert(5)
  *Tree\Insert(3)
  *Tree\Insert(6)
  *Tree\Insert(4)
  *Tree\Insert(1)

  Number = *Tree\GetNodeCount()
  Dim OrderArray.i(Number - 1)
  *Tree\Inorder(@OrderArray(), Number)

  For k = 0 To Number - 1
    *Tree\Delete(OrderArray(k))
    Debug OrderArray(k)
  Next k
  Debug "---"
  
  For k = 1 To 100
    Number = Random(99) + 1
    *Tree\Insert(Number)
  Next k

  For k = 1 To 100
    *Tree\Delete(Random(99) + 1)
  Next k
  
  StartDrawing(ImageOutput(0))
  Box(0, 0, ImageWidth(0), ImageHeight(0), RGB(255, 255, 255))
  *Tree\Draw(1100, 100, 5.1)
  StopDrawing()

  Repeat
    StartDrawing(WindowOutput(0))
    DrawImage(ImageID(0), 0, 0, WindowWidth(0), WindowHeight(0))
    StopDrawing()
  Until WaitWindowEvent() = #PB_Event_CloseWindow

EndIf
Have fun with it!
Last edited by DarkDragon on Thu Dec 03, 2009 10:30 am, edited 3 times in total.
bye,
Daniel
Top
+18
Enthusiast
Enthusiast
Posts: 228
Joined: Fri Oct 24, 2008 2:07 pm

Re: AVL Tree

Post by +18 »

COOL ONE, tanks DarkDragon :D
Top
User avatar
idle
Always Here
Always Here
Posts: 5836
Joined: Fri Sep 21, 2007 5:52 am
Location: New Zealand

Re: AVL Tree

Post by idle »

Trees are always useful.
Top
Mistrel
Addict
Addict
Posts: 3415
Joined: Sat Jun 30, 2007 8:04 pm

Re: AVL Tree

Post by Mistrel »

Excellent, thank you! I've been looking for something like this for a while. :)
Top
DarkDragon
Addict
Addict
Posts: 2344
Joined: Mon Jun 02, 2003 9:16 am
Location: Germany
Contact:
Contact DarkDragon

Re: AVL Tree

Post by DarkDragon »

Thanks for your answers :-) .

I've made the rebalance procedure a bit smaller now.
bye,
Daniel
Top
kinglestat
Enthusiast
Enthusiast
Posts: 746
Joined: Fri Jul 14, 2006 8:53 pm
Location: Malta
Contact:
Contact kinglestat

Re: AVL Tree

Post by kinglestat »

It is funny...I have finished doing balanced AVL and BST trees for PB...but in C...(PB was too slow for my particular scenario). I just need to finish my new threaded memory manager for release.. Nice post by the way

cheers
I may not help with your coding
Just ask about mental issues!

http://www.lulu.com/spotlight/kingwolf
http://www.sen3.net
Top
Post Reply

Return to “Tricks 'n' Tips”