PureBoard

Verfasst: **29.11.2009 12:48**

Hallo,

Ich muss zur Zeit einen AVL Baum in Java schreiben mit einigen Einschränkungen wie z.B. dass ich keine Referenz auf den Vorgängerknoten mitspeichern darf. Diesen Baum hab ich jetzt fertiggestellt und nach PureBasic portiert. Zum Debuggen hab ich mir eine simple grafische Ausgabe geschrieben. Die Methode Draw sollte also nur zu Debug-Zwecken verwendet werden und man sollte wissen was man da tut. Aber damit man den Baum erkennt (Und dass er balanciert ist) hab ich Draw im Beispielprogramm mal verwendet:

Code: Alles auswählen

; 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

Also der Gedanke hinter einem AVL Baum ist ja der, dass für jeden Knoten gilt: die Differenz der Höhe beider Teilbäume ist kleiner als/gleich 1. Somit ist die Gesamthöhe immer in Theta(log n).

[EDIT]
Code etwas erweitert. Nun kann man die Höhe auslesen und das ganze Zeug in inorder/preorder/postorder ausgeben lassen.

Verfasst: **29.11.2009 14:26**

Mich erinnert das an Kettenbriefe. Am Anfang 1DM Einsatz und am Ende ein Haus, wenn die Kette nicht abbricht.

Gruß Falko

Verfasst: **02.12.2009 12:39**

Danke für die Antwort

.

Ich hab jetzt noch die Rebalance Prozedur etwas verkleinert.

Verfasst: **02.12.2009 13:09**

@DarkDragon: mir fehlt jetzt noch der praktische Bezug.
Wofür könnte man so einen AVL Baum einsetzen?

Grüße ... Kiffi

Verfasst: **02.12.2009 13:38**

Kiffi hat geschrieben:@DarkDragon: mir fehlt jetzt noch der praktische Bezug.
Wofür könnte man so einen AVL Baum einsetzen?

Grüße ... Kiffi

Man kann ihn praktisch für alles einsetzen wo man mit größeren Datenmengen hantiert die noch in den Arbeitsspeicher passen. Ich weiß nicht ob das komplett reinpasst in den Arbeitsspeicher, aber vielleicht wäre eine Musikdatenbank passend o.ä..

Wenn du jetzt sequentiell suchst in n Elementen, also mit einer LinkedList oder einem Array einfach alle Elemente durchgehst, dann hast du eine worst-case Laufzeit von n.
Wenn du aber einen AVL Baum nimmst gehst du maximal die Höhe des Baums runter, also log_2(n). Du gehst auch nur log_2(n) runter zum Einfügen oder Löschen. Und wenn du dann das ganze sortiert ausgeben willst, d.h. in inorder durch den Baum durchgehst hast du eine Laufzeit von n * log_2(n).

Und durch die AVL Eigenschaft wird gewährleistet, dass der Baum immer eine minimale Höhe hat.

Verfasst: **02.12.2009 23:11**

Solche Nodes sind auch ein Bestandteil einer Rechenarchitektur von virtuellen Maschinen:

3 * 2 + 5 wird beispielswiese nach dem Lexer und Parser zu:

Code: Alles auswählen

add
  multiply
    3
    2
  5

Das Problem bei einer nicht optimierten Liste wäre folgendes:

Code: Alles auswählen

3 multiply 2 plus 5

Der Interpreter müsste nun die Prioritäten zur Laufzeit beachten, was bei einem AVL-Baum nicht mehr nötig ist, da der Parser schon alles erledigt hat. Außerdem ist ein AVL-Baum wesentlich schneller, da man beispielsweise keine Seperatoren wie "EOL" usw. benötigt, um den Interpreter richtig durch eine Liste aus Token zu lenken.

Nur so als Info, weil ich selbst gerade versuche diese Rechenarchitektur anzuwenden.

PS: Schöner Code Dark Dragon

Verfasst: **03.12.2009 09:27**

Josef Sniatecki hat geschrieben:Solche Nodes sind auch ein Bestandteil einer Rechenarchitektur von virtuellen Maschinen:

3 * 2 + 5 wird beispielswiese nach dem Lexer und Parser zu:
Code: Alles auswählen
add
  multiply
    3
    2
  5
Das Problem bei einer nicht optimierten Liste wäre folgendes:
Code: Alles auswählen
3 multiply 2 plus 5
Der Interpreter müsste nun die Prioritäten zur Laufzeit beachten, was bei einem AVL-Baum nicht mehr nötig ist, da der Parser schon alles erledigt hat. Außerdem ist ein AVL-Baum wesentlich schneller, da man beispielsweise keine Seperatoren wie "EOL" usw. benötigt, um den Interpreter richtig durch eine Liste aus Token zu lenken.

Nur so als Info, weil ich selbst gerade versuche diese Rechenarchitektur anzuwenden.

PS: Schöner Code Dark Dragon

Aber da würde der AVL Baum die Prioritäten der Operationen durcheinanderbringen und eventuell wären dann Operatoren plötzlich Blattknoten was nicht sein kann bei Infix. Immerhin geht der Parser/Interpreter dann durch den Baum durch und Rechnet bei einem "+" Knoten dann LinkerTeilbaum + RechterTeilbaum.

Verfasst: **03.12.2009 17:56**

Josef Sniatecki hat geschrieben:Solche Nodes sind auch ein Bestandteil einer Rechenarchitektur von virtuellen Maschinen:

3 * 2 + 5 wird beispielswiese nach dem Lexer und Parser zu:
Code: Alles auswählen
add
  multiply
    3
    2
  5
Das Problem bei einer nicht optimierten Liste wäre folgendes:
Code: Alles auswählen
3 multiply 2 plus 5
Der Interpreter müsste nun die Prioritäten zur Laufzeit beachten, was bei einem AVL-Baum nicht mehr nötig ist, da der Parser schon alles erledigt hat. Außerdem ist ein AVL-Baum wesentlich schneller, da man beispielsweise keine Seperatoren wie "EOL" usw. benötigt, um den Interpreter richtig durch eine Liste aus Token zu lenken.

Nur so als Info, weil ich selbst gerade versuche diese Rechenarchitektur anzuwenden.

PS: Schöner Code Dark Dragon

Du verwechselt offenbar AVL-Baum mit Syntaxbaum. Nur so als Info.

Verfasst: **03.12.2009 18:22**

Die geläufigsten Bäume sind

Bäume generell (Jeder Knoten hat Nachfolger, Knoten ohne Nachfolger heißen Blätter, der Knoten ohne Vorgänger heißt Wurzel)
Binäre Bäume (Jeder Knoten hat 2 Kinder)
Binäre Suchbäume (Binärer Baum, bei dem eine Ordnung zwischen linker Teilbaum, Wurzel, rechter Teilbaum besteht)
AVL Bäume (Eine Methode um Binäre Suchbäume in der Höhe zu minimieren)
Rot-Schwarz Bäume (Eine weitere Methode um Binäre Suchbäume zu optimieren)
B-Bäume (Jeder Knoten hat maximal 2 < d Nachfolger, Blätter alle auf einer Ebene, ...)
ISAM Bäume (Statische B-Bäume ohne Erweiterungsmöglichkeiten im Baum an sich - desshalb musste die Suchfunktion hier im Forum auch aktualisiert werden)
Heaps (Linksvollständiger Binärbaum, mit einer Ordnung Wurzel < oder > beide Kinder - vllt. kennt jemand Heapsort)

B-Bäume und ISAM Bäume werden in Datenbanken zur Auslagerung auf die Festplatte verwendet. Die Knoten können dabei riesengroß sein, sodass man diese wiederum mit AVL Bäumen oder Hashing weiter unterteilen kann. D.h. man lagert dann AVL Bäume aus und jeder AVL Baum ist ein Knoten in einem B-Baum ... . Aber kaum ein Baum hat einen derartig riesigen Programmieraufwand wie ein AVL Baum schätze ich.

Syntaxbäume oder Ausdrucksbäume gehören zu den generellen Bäumen.

Btw.: Ich hab einen Bug korrigiert.

Verfasst: **04.12.2009 17:13**

DarkDragon hat geschrieben: Aber da würde der AVL Baum die Prioritäten der Operationen durcheinanderbringen und eventuell wären dann Operatoren plötzlich Blattknoten was nicht sein kann bei Infix. Immerhin geht der Parser/Interpreter dann durch den Baum durch und Rechnet bei einem "+" Knoten dann LinkerTeilbaum + RechterTeilbaum.

OK, ehrlich gesagt verstehe ich jetzt immer noch nicht den Unterschied zwischen einem AVL-Baum und dem
Syntaxbaum, den ich verwendet habe. Die Operatoren sind in meinem Fall Knoten, die maximal zwei weitere
Unterknoten besitzen können, die genau eine Ebene darunter liegen...

PureBoard

AVL Baum

AVL Baum

Re: AVL Baum

Re: AVL Baum

Re: AVL Baum

Re: AVL Baum

Re: AVL Baum

Re: AVL Baum

Re: AVL Baum

Re: AVL Baum

Re: AVL Baum