Jump to content

Algorithm Implementation/Trees/AVL tree

From Wikibooks, open books for an open world

A Visual Basic 6.0 implementation (01/11/2014 update)

[edit | edit source]
Option Explicit
'_______________________________________________________________________________
'
'ABSTRACT
'   Provides any amount of requested memory (as long as there is available RAM)
'   and associates that memory with a user-defined alphanumeric key. Features
'   very fast retrieval in sorted order, even faster sequential access (in
'   the chronological order the requests were made).
'_______________________________________________________________________________
'
'DESCRIPTION
'   The alphanumeric keys are associated with a certain quantity of bytes located
'   at a designated position in RAM. That RAM is and remains exclusively reserved
'   for that Key. Via the key the address can be returned, and also the reserved
'   bytes at that address. Keys are internally managed with a balanced binary AVL
'   tree. It is possible to iterate through the whole collection of keys in the
'   order in which these keys were created (and the memory allocated), returning
'   the Key, the Address and the Size. It is also possible to access all the
'   Keys in sorted order (ascending as well as descending). All operations are
'   considerabily faster than VB's Collection object (as far as provided by the
'   Collection).
'_______________________________________________________________________________
'
'USAGE
'   What you do with the provided memory is up to you; however this is optimal
'   to store objects' addresses (available via ObjPtr) to circumvent the slow
'   COM mechanisms.
'_______________________________________________________________________________
'
'WARNINGS
'   * Whatever you do with the allocated memory, do not forget to free it
'     ("Set ThisClassesObject = Nothing" will do), or you soon end up with a lot
'     of blocked RAM which won't be freed until a restart.
'   * Do not attempt to write data beyond the end of the requested and allocated
'     memory fragment! Chances are you get a crash if you do.
'_______________________________________________________________________________
'
'AUTHOR
'   This software is (c) 2005-2014 by Herbert Glarner.
'   The used TypeLib for the IMalloc interface is (c) by Brad Martinez.
'_______________________________________________________________________________
'
'HISTORY
'   04 Apr 2005    1.0          Creation and Access functionality
'   05 Apr 2005    1.1          Replaced StrComp, Keys stored as Byte Arrays
'   07 Apr 2005                 Fixed a bug in IStrComp
'   11 Jan 2014                 Update
'_______________________________________________________________________________
'
'PROJECT FILES
'   SatAVL.cls                  (This file)
'_______________________________________________________________________________
'
'USED TEST FORM
'   SatAVLTest.frm (Test scenarioes and parallel comparison with VB Collection)
'_______________________________________________________________________________
'
'REQUIRED TYPE LIBRARIES
'   ISHF_Ex.tlb                 "IShellFolder Extended type Library v1.2"
'                               (The TypeLib is (c) by Brad Martinez)
'_______________________________________________________________________________
'
'REQUIRED DLLS
'   shell32                     (for "SHGetMalloc")
'_______________________________________________________________________________
'
'REQUIRED CONTROLS
'   -
'_______________________________________________________________________________
'
'EVENTS
'   -
'
'PUBLIC PROPERTIES
'   R           Nodes =     Count               Use to traverse by index 0...n-1
'
'PUBLIC METHODS
'   Address =   Add (Key, Bytes)                already existing: 0, else RAM
'
'LEXICAL ACCESS (SORTED BY KEY)
'   Index =     Lowest/Higher                   ascending, No more items: -1
'   Index =     Highest/Lower                   descending, No more items: -1
'
'DIRECT ACCESS (with result, use sequential access methods "Address" etc.)
'   Index =     Item (Key)                      not existing returns -1
'
'SEQUENTIAL ACCESS (IN APPENDING ORDER), ALSO DIRECT ACCESS WITH KNOWN INDEX
'   Key =       Key (Index)                     Index=0...n-1, n.ex. returns ""
'   Address =   Address (Index)                 Index=0...n-1, n.ex. returns 0
'   Bytes =     Size (Index)                    Index=0...n-1, n.ex. returns 0
'_______________________________________________________________________________
'
'EXTERNAL DLL METHODS

'IMalloc is available via the type library "ISHF_Ex.tlb" which has to be
'included into the project's references when used in the IDE.
Private Const NOERROR = 0
Private Declare Function SHGetMalloc Lib "shell32" _
    (ppMalloc As IMalloc) As Long
'_______________________________________________________________________________
'
'ERRORS (Base Number for this class: 4k)
'(Dont't forget to initialize descriptions in the Constructor)
Private Const ErrClass As String = "SatAVL"
Private Enum ErrNumber
    ErrBase = 4& * 1024&                            'Raised in:
    ErrNoMallocInterface = ErrBase + 0              'Initialize
    ErrFatalAdd = ErrBase + 1                       'Add
    ErrFatalItem = ErrBase + 2                      'Item
    'Always leave as the last entry:
    ErrAutoMax
End Enum
'Descriptions initialized on Construction
Private ErrDesc(ErrBase + 0 To ErrAutoMax - 1) As String
'_______________________________________________________________________________
'
'CONSTANTS

'Increasing elements vPath() if necessary.
Private Const NEWELEMENTS As Long = 10

'Elements in rNode having no pointer to another index.
Private Const sstNoChild As Long = -1
Private Const sstNoParent As Long = -1

'StrComp results.
Private Const sstKeyIsSmaller As Long = -1
Private Const sstKeyIsEqual As Long = 0
Private Const sstKeyIsLarger As Long = 1

'Used in Balance calculation for Height fields of the UDT "rChunk".
Private Const ssmbLeftHeavy As Integer = -2
Private Const ssmbLeftBalanced As Integer = -1
Private Const ssmbBalanced As Integer = 0
Private Const ssmbRightBalanced As Integer = 1
Private Const ssmbRightHeavy As Integer = 2
'_______________________________________________________________________________
'
'ENUMS

'Used in the Direction field of the UDT rPath (see below).
Private Enum ssmDirection
    ssmdLeft
    ssmdRight
End Enum
'_______________________________________________________________________________
'
'UDTS

'Able to handle up to 2G nodes (signed Long referring to indices).
Private Type rNode
    'The key and a reference to its content. (I've tested Key being an
    'Integer() array, converted into a such from an ordinary key via mapping
    'in Add(), so that only new keys needed to be mapped and the existing ones
    'were in Integer() format. However, key comparison takes up to 50% longer
    'time than the already slow string comparison, so it's strings again.)
    
    '(Seems that I could manage a slightly faster string comparison with
    'Byte arrays.)
    ByteKey() As Byte
    'Key As String                       'Provided by user, must be unique
    
    Address As Long                     'Memory allocated via Malloc
    Bytes As Long                       'As per user request, any number
    'Some links regarding the balanced binary tree ("Index" is the index of an
    'array in which this rChunk record is held among all relatives). Here we
    'definitely need Longs to care for more than 2^15 nodes.
    LeftTree As Long                    'Index of left subtree
    RightTree As Long                   'Index of right subtree
    Parent As Long                      'Index of the parent entry
    '(Integers rather Longs here to save 4 bytes; Integers with 2^15 entries for
    'the height should do the job: never encountered something such high due to
    'tree balancing. Approx. 1 million nodes need height < 40. Still I feel
    'that a byte is a risk, and there's also no need to save 2 bytes, since
    'alignment will use them anyway. I've also tested Long'anyway with writing and
    'accessing 1 million nodes: The time difference is not noticeable (once more,
    'once less time).
    LeftHeight As Integer               'This node's left height (excl. this node)
    RightHeight As Integer              'This node's right height (excl. this node)
End Type

'Detailled description see VARIABLES for "vPath()".
Private Type rPath
    Index As Long
    Direction As ssmDirection           'Left or right Path
End Type
'_______________________________________________________________________________
'
'EVENTS
'   None
'_______________________________________________________________________________
'
'VARIABLES

'Holds a reference to the IMalloc Interface, available via the type library
'ISHF_Ex.tlb to which a VB Project reference must be set to use it. Set on
'object construction, and destroyed on object destruction. The pointer is not
'made available to the external world; it is used object internally only to
'allocate resp. free memory.
Private ifMalloc As IMalloc

'This vector holds the balanced binary tree. In case that no "Alloc" was made
'so far, it is completely empty. With the first "Alloc" a first element (the
'root) is allocated.
Private vBinTree() As rNode
Private lBinTreeMax As Long     'The same as UBound(vBinTree)
Private lBinTreeNext As Long    '0=empty, 1=only 0 exists etc.
Private lBinTreeRoot As Long    'Initially 0, later anywhere (due to balancing)

'When adding a node, we need to keep track of the visited path, because we do
'not know before the very insertion if a tree grows higher or not. If it does,
'this may affect some or all nodes back up to the root, which we do not want to
'track again when we already have visited them: Instead their indices and also
'the direction we took (left/right) is held in this vector.
Private vPath() As rPath        'Never shrinks
Private lPathMax As Long        'The same as UBound(vPath)
Private lPathAct As Long        'Current pointer (0=start)

'Last accessed node via "Item", store the continuation points for some public
'methods like "Higher", "Lower" etc.
Private bLastAcc() As Byte      'Last searched Key via "Item".
Private lLastAcc As Long        'It's index; any "Add" invalidates this (-1).
'_______________________________________________________________________________

'CONSTRUCTION AND DESTRUCTION
'
Private Sub Class_Initialize()
    'Load error messages
    ErrDesc(ErrNoMallocInterface) = "Creation of a reference to the IMalloc interface failed."
    ErrDesc(ErrFatalAdd) = "Fatal Error in Add"
    ErrDesc(ErrFatalItem) = "Fatal Error in Item"

    'Returns a reference to the IMalloc interface. With it we can create and
    'destroy memory. Destroyed on object destruction.
    If Not (SHGetMalloc(ifMalloc) = NOERROR) Then
        'We could not obtain a reference to the interface.
        Err.Raise ErrNoMallocInterface, ErrClass, ErrDesc(ErrNoMallocInterface)
    End If

    'Create some initial nodes for the binary tree. Note, that we are going to
    '*double* this as soon as it does not suffice anymore (adding a constant
    'number *always* becomes a bottleneck at some point of time (when adding lots
    'of elements), even if it's 10000).
    lBinTreeMax = 2&
    ReDim vBinTree(0& To lBinTreeMax) As rNode
    lBinTreeNext = 0&
    lBinTreeRoot = 0&

    'Initial vPath() dimensioning to avoid testing for an empty vector.
    lPathMax = NEWELEMENTS - 1&
    ReDim vPath(0& To lPathMax) As rPath
End Sub

Private Sub Class_Terminate()
    'Walking the whole binary tree and freeing all allocated memory.
    If vBinTree(lBinTreeRoot).Address > 0 Then
        FreeMemory lBinTreeRoot
    End If
    Erase vBinTree
    
    'Destroy the reference to the IMalloc object, which was created on object
    'Construction.
    Set ifMalloc = Nothing
End Sub

'Recursive procedure to free all allocated memory on object destruction.
Private Sub FreeMemory(ParentIndex As Long)
    Dim lChildIndex As Long
    
    lChildIndex = vBinTree(ParentIndex).LeftTree
    If lChildIndex <> sstNoChild Then FreeMemory lChildIndex
    lChildIndex = vBinTree(ParentIndex).RightTree
    If lChildIndex <> sstNoChild Then FreeMemory lChildIndex
    
    'Freeing the memory for this ParentIndex
    ifMalloc.Free ByVal vBinTree(ParentIndex).Address
End Sub
'_______________________________________________________________________________

'PUBLIC PROPERTIES

'Returns 0 if there are no nodes at all. Note that indices for sequential access
'methods are 0-based (thus 0...Count-1).
Public Property Get Count() As Long
    Count = lBinTreeNext
End Property
'_______________________________________________________________________________

'PUBLIC METHODS

'"Add" requests "Bytes" of memory for free usage and associates this memory
'with "Key". Returns the *ADDRESS* of the allocated memory (ideal for CopyMemory).
'Returns 0 if the Key already exists (treat that as an error or read the
'original node ("Item" method) and react accordingly, but never assign data to
'the memory address 0 because your App would undoubtedly crash).
Public Function Add(ByRef Key As String, Bytes As Long) As Long
    Dim lActNode As Long
    Dim lChildNode As Long
    Dim lActChar As Long
    Dim lNewNode As Long
    Dim lStrComp As Long
    Dim bKey() As Byte
    '___________________________________________________________________________
    
    'Copy the string into a Byte array
    bKey = Key
    '___________________________________________________________________________
    
    'If the tree is still empty, create the first root node directly.
    If lBinTreeNext = 0& Then
        'Create the very first node, being the first root.
        lNewNode = MakeNode(sstNoParent, bKey, Bytes)
        'Return its address to the caller
        Add = vBinTree(lNewNode).Address
        Exit Function
    End If
    '___________________________________________________________________________
    
    'Beginning with the tree's root.
    lActNode = lBinTreeRoot
    
    'Initialize the path vector to trace the nodes we will see. Used to update
    'and balance the binary tree. vPath() was initially dimensioned with 0...9
    'when the object was constructed; later it holds its highest height.
    'Whenever needed, vPath() is increased by 10 elements (due to tree balancing
    'this won't be the case often: even with 1 million elements we usually get
    'away with less than 40 elements). lPathAct points to the actual element.
    lPathAct = 0&
    
    'Looping until we created a new leaf.
    '(No recursion here please, a simple loop will do the job and contributes
    'much to performance.)
    Do
        'Updating the path we took
        vPath(lPathAct).Index = lActNode
        
        'Comparing new key with existing key (StrComp is significantly faster
        'than two string comparisons with "<" and "=". (Adding 1 million nodes
        'in my test with random 8 char long alpha keys results in 20204798
        'string comparisons.)
        '   < and =:    1000000 Adds: 65.2293464672184 sec net excl overhead
        '   lStrComp:   1000000 Adds: 61.7483442728189 sec net excl overhead
        '(Still this comparison is a bottleneck in mass Add: It takes approx.
        '50% of the time of the whole procedure.)
        '"StrComp" seems to return a Variant ...

        '(StrComp() is slower than CLong(StrComp()) and this slower than my function.)
        'lStrComp = StrComp(Key, vBinTree(lActNode).Key, vbBinaryCompare)
        'lStrComp = CLng(StrComp(Key, vBinTree(lActNode).Key, vbBinaryCompare))
        lStrComp = IStrComp(bKey, vBinTree(lActNode).ByteKey)
        
        'Results in lStrComp: -1 when Key smaller, +1 when larger, 0 when equal.
        'We test ssmdRight first, because *all* keys qualify only here if they
        'are fed in sorted order; otherwise (random feed) they are almost
        'equally distributed. (First branch in Ifs is executed slightly faster.)
        If lStrComp = sstKeyIsLarger Then
            'Right child
            'Updating the path we took
            vPath(lPathAct).Direction = ssmdRight
            
            lChildNode = vBinTree(lActNode).RightTree
            If lChildNode = sstNoChild Then
                'Make a new left child node and link it as a child of the
                'actual node (being the parent now for the new node).
                lNewNode = MakeNode(lActNode, bKey, Bytes)
                vBinTree(lActNode).RightTree = lNewNode
                
                'Heights of the path need to be updated
                UpdateHeights
                
                'Return address to caller and leave
                Add = vBinTree(lNewNode).Address
                Exit Function
            End If
        ElseIf lStrComp = sstKeyIsSmaller Then
            'Left child
            'Updating the path we took
            vPath(lPathAct).Direction = ssmdLeft
            
            lChildNode = vBinTree(lActNode).LeftTree
            If lChildNode = sstNoChild Then
                'Make a new left child node and link it as a child of the
                'actual node (being the parent now for the new node).
                lNewNode = MakeNode(lActNode, bKey, Bytes)
                vBinTree(lActNode).LeftTree = lNewNode
                
                'Heights of the path need to be updated
                UpdateHeights
                
                'Return address to caller and leave
                Add = vBinTree(lNewNode).Address
                Exit Function
            End If
        Else
            'This key already exists.
            'We do not interrupt the client's normal program flow with urging him
            'to react on an error here, but we return 0 and expect him to check
            'for this (invalid) value, except when he is sure that no identical
            'keys do exist.
            Add = 0
            Exit Function
        End If
    
        'Redimensioning the vPath() vector in steps of 10 if needed. Will be
        'executed rarely (in general less than 40 elements for 1 million nodes).
        If lPathAct = lPathMax Then
            lPathMax = lPathMax + NEWELEMENTS
            ReDim Preserve vPath(0& To lPathMax) As rPath
        End If
        lPathAct = lPathAct + 1&
        
        'Following the child's left or right child now.
        lActNode = lChildNode
    Loop
    '___________________________________________________________________________
    
    'Not a valid exit point: We never should arrive here.
    Err.Raise ErrFatalAdd, ErrClass, ErrDesc(ErrFatalAdd)
End Function

'This returns the *index* of the memory associated with the provided key (or -1
'if such a key does not exist). With the index, use the very fast index
'functions to retrieve the associated data (methods "Key", "Address", "Size").
Public Function Item(ByRef Key As String) As Long
    Dim lStrComp As Long
    Dim bKey() As Byte
    '___________________________________________________________________________
    
    'Copy string into byte array
    bKey = Key
    
    'Register this access.
    bLastAcc = bKey
    
    'Begin with root node.
    lLastAcc = lBinTreeRoot
    Do
        'StrComp is significantly faster than two comparisons with "<" and "=".
        '   < and =:    Retrieved all 1000000 nodes by key: 22.78 sec (43896/sec)
        '   StrComp:    Retrieved all 1000000 nodes by key: 18.67 sec (53558/sec)
        'Returns -1 if first string is smaller, 1 if larger, 0 if equal.
        '(Still this comparison is a bottleneck: The following line takes up
        'to 60% of the whole procedure's time. StrComp returns a Variant...)

        '(StrComp() is slower than CLong(StrComp()) and this slower than my function.)
        'lStrComp = StrComp(Key, vBinTree(lLastAcc).Key, vbBinaryCompare)
        'lStrComp = CLng(StrComp(Key, vBinTree(lLastAcc).Key, vbBinaryCompare))
        lStrComp = IStrComp(bKey, vBinTree(lLastAcc).ByteKey)

        If lStrComp = sstKeyIsSmaller Then
            'Continue with left subtree
            lLastAcc = vBinTree(lLastAcc).LeftTree
        ElseIf lStrComp = sstKeyIsLarger Then
            'Continue with right subtree
            lLastAcc = vBinTree(lLastAcc).RightTree
        Else
            '0 as the last case: Lowest chances to hit.
            'Found
            Item = lLastAcc
            'lLastAccPred
            Exit Function
        End If
        If lLastAcc = sstNoChild Then
            'Not existing
            bLastAcc = ""
            Item = sstNoChild
            Exit Function
        End If
    Loop
    'Never should arrive here
    Err.Raise ErrFatalItem, ErrClass, ErrDesc(ErrFatalItem)
End Function

'Accessing the nodes as per sorted key order (lexicographically).
'These methods return the INDICES and *not* the addresses already; this is because
'the user most likely also wants to access the key, which is cheap when having the
'index. Do *not* store the index: Each additional "Add" might change it drastically.
Public Function Lowest() As Long
    'Begin with root node.
    lLastAcc = lBinTreeRoot
    
    'Follow all left subtrees until there are no more.
    Do While vBinTree(lLastAcc).LeftTree <> sstNoChild
        lLastAcc = vBinTree(lLastAcc).LeftTree
    Loop
    
    'Store as the actual node.
    bLastAcc = vBinTree(lLastAcc).ByteKey
    
    'Return result (INDEX, not address).
    Lowest = lLastAcc
End Function

Public Function Higher() As Long        'Use after Lowest
    'Having an index in lLastAcc we find the successor of that node.
    
    'If lLastAcc has a right child, then its successor is the minimum in the
    'right subtree.
    If vBinTree(lLastAcc).RightTree <> sstNoChild Then
        'Access right subtree.
        lLastAcc = vBinTree(lLastAcc).RightTree
        'From there follow all left subtrees until there are no more.
        Do While vBinTree(lLastAcc).LeftTree <> sstNoChild
            lLastAcc = vBinTree(lLastAcc).LeftTree
        Loop
        'Store as the actual node.
        bLastAcc = vBinTree(lLastAcc).ByteKey
    Else
        'No right subtree. Find the lowest ancestor of lLastAcc, whose
        'left child is also an ancestor of lLastAcc.
        
        'Follow parent pointers from lLastAcc, until reaching a key larger
        'than lLastAcc's key (if there is none, then lLastAcc is the maximum).
        Do
            lLastAcc = vBinTree(lLastAcc).Parent
            If lLastAcc = sstNoParent Then
                'Is already highest item: No successor is available.
                bLastAcc = ""
                Exit Do
            ElseIf IStrComp(vBinTree(lLastAcc).ByteKey, bLastAcc) = sstKeyIsLarger Then
                'Found: Store as the actual node (just because it becomes cheap).
                bLastAcc = vBinTree(lLastAcc).ByteKey
                Exit Do
            End If
        Loop
        'lLastAcc is either the successor or -1 (already highest item)
    End If

    'Return result (INDEX, not address).
    Higher = lLastAcc
End Function

Public Function Highest() As Long
    'Begin with root node.
    lLastAcc = lBinTreeRoot
    
    'Follow all right subtrees until there are no more.
    Do While vBinTree(lLastAcc).RightTree <> sstNoChild
        lLastAcc = vBinTree(lLastAcc).RightTree
    Loop
    
    'Store as the actual node.
    bLastAcc = vBinTree(lLastAcc).ByteKey
    
    'Return result (INDEX, not address).
    Highest = lLastAcc
End Function

Public Function Lower() As Long         'Use after Highest
    'Having an index in lLastAcc we find the predecessor of that node.
    
    'If lLastAcc has a left child, then its predecessor is the maximum in the
    'left subtree.
    If vBinTree(lLastAcc).LeftTree <> sstNoChild Then
        'Access left subtree.
        lLastAcc = vBinTree(lLastAcc).LeftTree
        'From there follow all right subtrees until there are no more.
        Do While vBinTree(lLastAcc).RightTree <> sstNoChild
            lLastAcc = vBinTree(lLastAcc).RightTree
        Loop
        'Store as the actual node (just because it becomes cheap).
        bLastAcc = vBinTree(lLastAcc).ByteKey
    Else
        'No left subtree. Find the lowest ancestor of lLastAcc, whose
        'right child is also an ancestor of lLastAcc.
        
        'Follow parent pointers from lLastAcc, until reaching a key smaller
        'than lLastAcc's key (if there is none, then lLastAcc is the minimum).
        Do
            lLastAcc = vBinTree(lLastAcc).Parent
            If lLastAcc = sstNoParent Then
                'Is already smallest item: No predecessor is available.
                bLastAcc = ""
                Exit Do
            ElseIf IStrComp(vBinTree(lLastAcc).ByteKey, bLastAcc) = sstKeyIsSmaller Then
                'Found: Store as the actual node (just because it becomes cheap).
                bLastAcc = vBinTree(lLastAcc).ByteKey
                Exit Do
            End If
        Loop
        'lLastAcc is either the successor or -1 (already highest item)
    End If

    'Return result (INDEX, not address).
    Lower = lLastAcc
End Function

'Accessing the nodes by their insertion order (0=first, lBinTreeNext-1=last).
'Returns the address of the node, or 0 if there is no such index.
Public Function Address(Index As Long) As Long
    If Index >= lBinTreeNext Then
        Address = 0
    ElseIf Index < 0 Then
        Address = 0
    Else
        Address = vBinTree(Index).Address
    End If
End Function

'Returns the reserved memory of the node 8in bytes), or 0 if there is no such index.
Public Function Size(Index As Long) As Long
    If Index >= lBinTreeNext Then
        Size = 0
    ElseIf Index < 0 Then
        Size = 0
    Else
        Size = vBinTree(Index).Bytes
    End If
End Function

'Returns the key of the node, or a null-length string ("") if there is no
'such index.
Public Function Key(Index As Long) As String
    If Index >= lBinTreeNext Then
        Key = ""
    ElseIf Index < 0 Then
        Key = ""
    Else
        'Return as a string, user is not interested in a Byte Array
        Key = vBinTree(Index).ByteKey
    End If
End Function
'_______________________________________________________________________________

'INTERNAL ROUTINES

'Creating a new node below a given parent. Returns the index into vBinTree().
Private Function MakeNode(ParentIndex As Long, ByRef Key() As Byte, Bytes As Long) As Long
    'If this new node requires that we make new elements to hold more nodes,
    'we expand our vector by doubling it (a constant number of elements *always*
    'becomes a bottleneck at some point of time, even if it's 1000).
    If lBinTreeNext > lBinTreeMax Then
        lBinTreeMax = lBinTreeMax * 2
        ReDim Preserve vBinTree(0 To lBinTreeMax) As rNode
    End If
    
    'lBinTreeNext is the element index into the vector.
    With vBinTree(lBinTreeNext)
        .ByteKey = Key
        .Address = ifMalloc.Alloc(Bytes)
        .Bytes = Bytes
        .Parent = ParentIndex
        .LeftTree = sstNoChild
        .RightTree = sstNoChild
    End With
    
    'Return the index as this function's result
    MakeNode = lBinTreeNext
    
    'Prepare for next node.
    lBinTreeNext = lBinTreeNext + 1&
End Function

'BALANCING THE TREE
'Depending on the nodes' actual balances, one of four balancing activities can
'be called (BalanceLL, BalanceRR, BalanceLR or BalanceRL). In a test scenario
'with 1 million nodes with 8 char long RANDOM keys consisting of all upper- and
'lowercase alphabetic characters A...Z and a...z, the balancing routines were
'called so many times:          With 1 mill already SORTED input (key length 4):
'    Rebalances LL 119628            0
'    Rebalances RR 118737       999980
'    Rebalances LR 114924            0
'    Rebalances RL 115005            0
'    Total         468294       999980
Private Sub UpdateHeights()
    Dim lLevel As Long
    Dim lNode As Long
    Dim lLeftTree As Long
    Dim lRightTree As Long
    Dim iUpperBalance As Integer        'Integer to match UDT definition
    Dim iLowerBalance As Integer        'Integer to match UDT definition
    Dim iNewHeight As Integer           'Integer to match UDT definition
    '___________________________________________________________________________
    
    'Must be reverse height, because we might break update for upper levels.
    For lLevel = lPathAct To 0& Step -1&
        lNode = vPath(lLevel).Index
        
        'Increase height along path. Direction is either ssmdLeft or ssmdRight.
        'If the Keys are fed sorted, only ssmdRight will appear (if fed in
        'random order, there are almost equal chances for the left and the right
        'path): For this reason, ssmdRight is tested first (slightly faster).
        If vPath(lLevel).Direction = ssmdRight Then
            iNewHeight = vBinTree(lNode).RightHeight + 1&
            vBinTree(lNode).RightHeight = iNewHeight
            'If right was *not* responsible for a height increase, this breaks
            'the update (no propagation farther up).
            If iNewHeight <= vBinTree(lNode).LeftHeight Then
                Exit For
            End If
        Else
            iNewHeight = vBinTree(lNode).LeftHeight + 1&
            vBinTree(lNode).LeftHeight = iNewHeight
            'If Left was *not* responsible for a height increase, this breaks
            'the update (no propagation farther up).
            If iNewHeight <= vBinTree(lNode).RightHeight Then
                Exit For
            End If
        End If
    
        'Nodes with a too heavy weight left or right cause a tree balancing
        'activity now. Too heavy is, when there is a height difference of +/-2.
        iUpperBalance = vBinTree(lNode).RightHeight - vBinTree(lNode).LeftHeight
        
        'testing right-heavy first because we want RR to be executed as fast as
        'possible to acknowledge that RR type is executed almost always when keys
        'are fed already sorted to Add; whereas the distribution of the 4 types
        'is almost the same (totalling in about 44%) when the keys are fed in
        'random order.
        If iUpperBalance = ssmbRightHeavy Then
            'Node is right-heavy (+2). Examine its right child.
            lRightTree = vBinTree(lNode).RightTree
            iLowerBalance = vBinTree(lRightTree).RightHeight - vBinTree(lRightTree).LeftHeight

            'Testing ssmbRightBalanced first to take care for the case that
            'keys may come in already sorted, in which case 99.8% of all Adds
            'require a RR balancing. If keys are fed random, all 4 types are
            'equally distributed.
            If iLowerBalance = ssmbRightBalanced Then
                'Left child is right-balanced. RR situation.
                BalanceRR lNode
            Else
                'Cannot be ssmbBalanced, and so must be ssmbLeftBalanced.
                BalanceRL lNode
            End If
            'This breaks updates further back!
            Exit For
        ElseIf iUpperBalance = ssmbLeftHeavy Then
            'Node is left-heavy (-2). Examine its left child.
            lLeftTree = vBinTree(lNode).LeftTree
            iLowerBalance = vBinTree(lLeftTree).RightHeight - vBinTree(lLeftTree).LeftHeight

            If iLowerBalance = ssmbRightBalanced Then
                'Left child is right-balanced. LR situation.
                BalanceLR lNode
            Else
                'Cannot be ssmbBalanced, and so must be ssmbLeftBalanced.
                BalanceLL lNode
            End If
            'This breaks updates further back!
            Exit For
        End If
    Next lLevel
End Sub

'_______________________________________________________________________________
'
'INTERNAL ROUTINES TO BALANCE THE BINARY TREE

'LL - A is the node that the rotation is performed on. This rotation is performed
'when A is unbalanced to the left (the left subtree is 2 higher than the right
'subtree) and B is left-heavy (the left subtree of B is 1 higher than the right
'subtree of B). T1, T2 and T3 represent subtrees (a node was added to T1 which
'made B left-heavy and unbalanced A). P is A's parent and listed only because A's
'relationship with P is taken over by B, making relinks necessary.
'
'        P                        P
'        |                        |
'        A                        B
'       / \      ---------->     / \
'      B  T3                    T1  A
'     / \                       ** / \
'    T1 T2                        T2 T3
'    **
'+--+--------+--------+
'|  | Before | After  |
'+--+--+--+--+--+--+--+
'|  |LT|RT|PA|LT|RT|PA|
'+--+--+--+--+--+--+--+
'|A |B |  |P |T2|  |B |
'|B |  |T2|A |  |A |P |
'|T2|  |  |B |  |  |A |
'|P |  A  |  |  B  |  |
'+--+--+--+--+--+--+--+
'
Private Sub BalanceLL(lA As Long)
    Dim lB As Long
    Dim lP As Long
    Dim lT2 As Long
    
    'Indices of old state
    lB = vBinTree(lA).LeftTree
    lT2 = vBinTree(lB).RightTree
    lP = vBinTree(lA).Parent
    
    'New links
    vBinTree(lA).LeftTree = lT2
    If lT2 <> sstNoChild Then vBinTree(lT2).Parent = lA
    vBinTree(lB).RightTree = lA
    vBinTree(lA).Parent = lB
    If lP <> sstNoParent Then
        'A was either P's left or right child, B is taking that place now.
        vBinTree(lB).Parent = lP
        If vBinTree(lP).LeftTree = lA Then
            vBinTree(lP).LeftTree = lB
        Else
            vBinTree(lP).RightTree = lB
        End If
    Else
        'If A was the whole tree's root, then it's role is taken over by B now.
        vBinTree(lB).Parent = sstNoParent
        lBinTreeRoot = lB
    End If
    
    'New weights
    vBinTree(lA).LeftHeight = vBinTree(lA).LeftHeight - 2
    vBinTree(lB).RightHeight = vBinTree(lB).RightHeight + 1
End Sub
'
'RR - A is the node that the rotation is performed on. This rotation is performed
'when A is unbalanced to the right (the right subtree is 2 higher than the left
'subtree) and B is rightheavy (the right subtree of B is 1 higher than the left
'subtree of B). T1, T2 and T3 represent subtrees (a node was added to T3 which
'made B right-heavy and unbalanced A). P is A's parent and listed only because A's
'relationship with P is taken over by B, making relinks necessary.
'(This rotation is performed on almost every node if the keys are added in already
'sorted order, and no other rotations are performed at all then.)
'
'        P                        P
'        |                        |
'        A                        B
'       / \      ---------->     / \
'      T1  B                    A  T3
'         / \                  / \ **
'        T2  T3               T1 T2
'            **
'+--+--------+--------+
'|  | Before | After  |
'+--+--+--+--+--+--+--+
'|  |LT|RT|PA|LT|RT|PA|
'+--+--+--+--+--+--+--+
'|A |  |B |P |  |T2|B |
'|B |T2|  |A |A |  |P |
'|T2|  |  |B |  |  |A |
'|P |  A  |  |  B  |  |
'+--+--+--+--+--+--+--+
'
Private Sub BalanceRR(lA As Long)
    Dim lB As Long
    Dim lP As Long
    Dim lT2 As Long
    
    'Indices of old state
    lB = vBinTree(lA).RightTree
    lP = vBinTree(lA).Parent
    lT2 = vBinTree(lB).LeftTree
    
    'New links
    vBinTree(lA).RightTree = lT2
    If lT2 <> sstNoChild Then vBinTree(lT2).Parent = lA
    vBinTree(lB).LeftTree = lA
    vBinTree(lA).Parent = lB
    If lP <> sstNoParent Then
        'A was either P's left or right child, B is taking that place now.
        vBinTree(lB).Parent = lP
        If vBinTree(lP).LeftTree = lA Then
            vBinTree(lP).LeftTree = lB
        Else
            vBinTree(lP).RightTree = lB
        End If
    Else
        'If A was the whole tree's root, then it's role is taken over by B now.
        vBinTree(lB).Parent = sstNoParent
        lBinTreeRoot = lB
    End If
    
    'New weights
    vBinTree(lA).RightHeight = vBinTree(lA).RightHeight - 2
    vBinTree(lB).LeftHeight = vBinTree(lB).LeftHeight + 1
End Sub
'
'LR - C is the node that the rotation is performed on. This rotation is performed
'when C is unbalanced to the left (the left subtree is 2 higher than the right
'subtree), A is rightheavy (the right subtree of A is 1 higher than the left
'subtree of A) and B is leftheavy. T1, T2, T3, and T4 represent subtrees (a node
'was added to T2 which made B leftheavy, made A rightheavy and unbalanced C).
'This consists of a single left rotation at node A, followed by a single right
'at node C. P is C's parent and listed only because C's relationship with P is
'taken over by B, making relinks necessary.
'
'        P                         P
'        |                         |
'        C                         B
'       / \      ---------->     /   \
'      A  T4                    A     C
'     / \                      / \   / \
'    T1  B                    T1 T2 T3 T4
'       / \                      **
'      T2 T3
'      **
'+--+--------+--------+
'|  | Before | After  |
'+--+--+--+--+--+--+--+
'|  |LT|RT|PA|LT|RT|PA|
'+--+--+--+--+--+--+--+
'|A |  |B |C |  |T2|B |
'|B |T2|T3|A |A |C |P |
'|C |A |  |P |T3|  |B |
'|T2|  |  |B |  |  |A |
'|T3|  |  |B |  |  |C |
'|P |  C  |  |  B  |  |
'+--+--+--+--+--+--+--+
'
Private Sub BalanceLR(lC As Long)
    Dim lA As Long
    Dim lB As Long
    Dim lT2 As Long
    Dim lT3 As Long
    Dim lP As Long
    
    'Indices of old state
    lA = vBinTree(lC).LeftTree
    lB = vBinTree(lA).RightTree
    lP = vBinTree(lC).Parent
    lT2 = vBinTree(lB).LeftTree
    lT3 = vBinTree(lB).RightTree

    'New links
    vBinTree(lA).RightTree = lT2
    vBinTree(lA).Parent = lB
    vBinTree(lB).LeftTree = lA
    vBinTree(lB).RightTree = lC
    vBinTree(lC).LeftTree = lT3
    vBinTree(lC).Parent = lB
    If lT2 <> sstNoChild Then vBinTree(lT2).Parent = lA
    If lT3 <> sstNoChild Then vBinTree(lT3).Parent = lC
    If lP <> sstNoParent Then
        'C was either P's left or right child, B is taking that place now.
        vBinTree(lB).Parent = lP
        If vBinTree(lP).LeftTree = lC Then
            vBinTree(lP).LeftTree = lB
        Else
            vBinTree(lP).RightTree = lB
        End If
    Else
        'If C was the whole tree's root, then it's role is taken over by B now.
        vBinTree(lB).Parent = sstNoParent
        lBinTreeRoot = lB
    End If
    
    'New weights
    vBinTree(lA).RightHeight = vBinTree(lA).RightHeight - 1
    vBinTree(lB).LeftHeight = vBinTree(lB).LeftHeight + 1
    vBinTree(lB).RightHeight = vBinTree(lB).RightHeight + 1
    vBinTree(lC).LeftHeight = vBinTree(lC).LeftHeight - 2
End Sub
'
'RL - A is the node that the rotation is performed on. This rotation is performed
'when A is unbalanced to the right (the right subtree is 2 higher than the left
'subtree), C is leftheavy (the left subtree of A is 1 higher than the right
'subtree of A) and B is rightheavy. T1, T2, T3, and T4 represent subtrees (a node
'was added to T3 which made B rightheavy, made C leftheavy and unbalanced A).
'This consists of a single right at node C, followed by a single left at node A.
'P is A's parent and listed only because A's relationship with P is taken over
'by B, making relinks necessary.
'
'        P                         P
'        |                         |
'        A                         B
'       / \      ---------->     /   \
'      T1  C                    A     C
'         / \                  / \   / \
'        B  T4                T1 T2 T3 T4
'       / \                         **
'      T2 T3
'         **
'+--+--------+--------+
'|  | Before | After  |
'+--+--+--+--+--+--+--+
'|  |LT|RT|PA|LT|RT|PA|
'+--+--+--+--+--+--+--+
'|A |  |C |P |  |T2|B |
'|B |T2|T3|C |A |C |P |
'|C |B |  |A |T3|  |B |
'|T2|  |  |B |  |  |A |
'|T3|  |  |B |  |  |C |
'|P |  A  |  |  B  |  |
'+--+--+--+--+--+--+--+
'
Private Sub BalanceRL(lA As Long)
    Dim lB As Long
    Dim lC As Long
    Dim lT2 As Long
    Dim lT3 As Long
    Dim lP As Long
    
    'Indices of old state
    lP = vBinTree(lA).Parent
    lC = vBinTree(lA).RightTree
    lB = vBinTree(lC).LeftTree
    lT2 = vBinTree(lB).LeftTree
    lT3 = vBinTree(lB).RightTree
    
    'New links
    vBinTree(lA).RightTree = lT2
    vBinTree(lA).Parent = lB
    vBinTree(lB).LeftTree = lA
    vBinTree(lB).RightTree = lC
    vBinTree(lC).LeftTree = lT3
    vBinTree(lC).Parent = lB
    If lT2 <> sstNoChild Then vBinTree(lT2).Parent = lA
    If lT3 <> sstNoChild Then vBinTree(lT3).Parent = lC
    If lP <> sstNoParent Then
        'A was either P's left or right child, B is taking that place now.
        vBinTree(lB).Parent = lP
        If vBinTree(lP).LeftTree = lA Then
            vBinTree(lP).LeftTree = lB
        Else
            vBinTree(lP).RightTree = lB
        End If
    Else
        'If A was the whole tree's root, then its role is taken over by B now.
        vBinTree(lB).Parent = sstNoParent
        lBinTreeRoot = lB
    End If
    
    'New weights
    vBinTree(lA).RightHeight = vBinTree(lA).RightHeight - 2
    vBinTree(lB).LeftHeight = vBinTree(lB).LeftHeight + 1
    vBinTree(lB).RightHeight = vBinTree(lB).RightHeight + 1
    vBinTree(lC).LeftHeight = vBinTree(lC).LeftHeight - 1
End Sub
'_______________________________________________________________________________

'Searching for a fast replacement of the slow StrComp.
Private Function IStrComp(ByRef bStr() As Byte, ByRef bCmp() As Byte) As Long
'    Dim lSameChars As Long
'
'(As per MSDN October 2002, RTLCompareMemory() is only included in Win2K and XP.)
'Private Declare Function CompareMemory Lib "ntdll" Alias "RtlCompareMemory" _
'    (buffA As Any, buffB As Any, ByVal Length As Long) As Long

'    'CompareMemory returns how many byte elements are the same.
'    lSameChars = CompareMemory(bStr(0), bCmp(0), UBound(bStr))
'    If bStr(lSameChars) > bCmp(lSameChars) Then
'        IStrComp = sstKeyIsLarger
'        Exit Function
'    ElseIf bStr(lSameChars) < bCmp(lSameChars) Then
'        IStrComp = sstKeyIsSmaller
'        Exit Function
'    End If
'    'Else returning 0 (doing nothing as it's the default result)
    
    Dim lPos As Long

    For lPos = 0 To UBound(bStr) Step 2&     'Step 2 for ANSI test, else 1
        'bCmp might end sooner than bStr, but be otherwise equal. In this
        'case bStr is larger.
        If lPos > UBound(bCmp) Then
            IStrComp = sstKeyIsSmaller
            Exit Function
        'Instead of comparing each char twice (once for larger and once for
        'smaller), we compare once for inequality. Only if not equal we do a
        'final test on how it was not equal. ("<>" is faster than ">" or "<"
        'alone, so even more when testing both.)
        ElseIf bStr(lPos) <> bCmp(lPos) Then
            If bStr(lPos) > bCmp(lPos) Then
                IStrComp = sstKeyIsLarger
            Else
                IStrComp = sstKeyIsSmaller
            End If
            Exit Function
        End If
    Next lPos
    'Strings are equal if Cmp ends as well, or Cmp is longer and thus larger.
    If UBound(bStr) <> UBound(bCmp) Then IStrComp = sstKeyIsLarger
    'Else implicitly returning sstKeyIsEqual = 0
End Function

A C++ implementation

[edit | edit source]
// NOTE: All the member functions are inline in the following code.
//       This is not recommended. Only simple straight forward functions should be made inline.
class AVLTree
{
	private:
		class Node
		{
			private:
				int data;
				int height;
				Node * parent;
				Node * left_child;
				Node * right_child;
			public:
				Node(int val)
				{
					data = val;
					height = 0;
					parent = (Node*)0;
					left_child = (Node*)0;
					right_child = (Node*)0;
				}
				int getData()
				{
					return data;
				}
				int getHeight()
				{
					return height;
				}
				int updateHeight()
				{
					if(left_child != 0 && right_child != 0)
					{
						if(left_child->getHeight() > right_child->getHeight())
							height = left_child->getHeight() + 1;
						else
							height = right_child->getHeight() + 1;
					}
					else if(left_child != 0)
						height = left_child->getHeight() + 1;
					else if(right_child != 0)
						height = right_child->getHeight() + 1;
					else
						height = 0;
					return height;
				}
				int getBalance()
				{
					Node * n = this;
					if(n->getLeftChild() != 0 && n->getRightChild() !=0)
						return n->getLeftChild()->getHeight() - n->getRightChild()->getHeight();
					else if(n->getLeftChild() != 0)
						return n->getLeftChild()->getHeight() + 1;
					else if(n->getRightChild() != 0)
						return (-1) * (n->getRightChild()->getHeight() + 1);
					else
						return 0;
				}
				Node* getParent()
				{
					return parent;
				}
				void removeParent()
				{
					parent = (Node*)0;
				}
				Node* getLeftChild()
				{
					return left_child;
				}
				Node* setLeftChild(Node* new_left)
				{
					if(new_left != 0) new_left->parent = this;
					left_child = new_left;
					updateHeight();
					return left_child;
				}
				Node* getRightChild()
				{
					return right_child;
				}
				Node* setRightChild(Node* new_right)
				{
					if(new_right != 0) new_right->parent = this;
					right_child = new_right;
					updateHeight();
					return right_child;
				}
		};

		void setRoot(Node* n)
		{
			root = n;
			if(root != 0) root->removeParent();
		}

		Node* findNode(int val)
		{
			Node* temp = root;
			while(temp != 0)
			{
				if(val == temp->getData())
					return temp;

				else if(val < temp->getData())
					temp = temp->getLeftChild();

				else
					temp = temp->getRightChild();
			}
			return (Node*)0;
		}
		void rotateLeft(Node * n)
		{
			Node * p = n->getParent();
			enum {left, right} side;
			if(p != 0)
			{
				if(p->getLeftChild() == n)
					side = left;
				else
					side = right;
			}
			Node * temp = n->getRightChild();
			n->setRightChild(temp->getLeftChild());
			temp->setLeftChild(n);
			// Now attach the subtree to the parent (or root)
			if(p != 0)
			{
				if(side == left)
					p->setLeftChild(temp);
				if(side == right)
					p->setRightChild(temp);
			}
			else
			{
				setRoot(temp);
			}
		}

		void rotateRight(Node * n)
		{
			Node * p = n->getParent();
			enum {left, right} side;
			if(p != 0)
			{
				if(p->getLeftChild() == n)
					side = left;
				else
					side = right;
			}
			Node * temp = n->getLeftChild();
			n->setLeftChild(temp->getRightChild());
			temp->setRightChild(n);
			// Now attach the subtree to the parent (or root)
			if(p != 0)
			{
				if(side == left)
					p->setLeftChild(temp);
				if(side == right)
					p->setRightChild(temp);
			}
			else
			{
				setRoot(temp);
			}
		}
		
		// This function does balancing at the given node
		void balanceAtNode(Node* n)
		{			
			int bal = n->getBalance();
			if(bal > 1)
			{
				if(n->getLeftChild()->getBalance() < 0)
					rotateLeft(n->getLeftChild());
				rotateRight(n);
			}
			else if(bal < -1)
			{
				if(n->getRightChild()->getBalance() > 0)
					rotateRight(n->getRightChild());
				rotateLeft(n);
			}
		}
		
		Node * root;

	public:
		AVLTree()
		{
			root = (Node*)0;
		}

		AVLTree(int val)
		{
			root = new Node(val);
		}

		AVLTree * findSubtree(int val)
		{
			Node* target;
			target = findNode(val);

			if(target != 0)
			{
				AVLTree* subtree = new AVLTree();
				subtree->root = target;
				return subtree;
			}
			else
				return (AVLTree*)0;
		}

		// Returns:
		// 		true: If addition is successful
		// 		false: If item already exists
		//
		bool insert(int val)
		{
			Node* added_node;
			if(root == 0)
			{
				root = new Node(val);
			}
			else
			{
				Node* temp = root;

				while(true)
				{
					if(temp->getData() > val)
					{
						if((temp->getLeftChild()) == 0)
						{
							added_node = temp->setLeftChild(new Node(val));
							break;
						}
						else
						{
							temp = temp->getLeftChild();
						}
						
					}
					else if(temp->getData() < val)
					{
						if((temp->getRightChild()) == 0)
						{
							added_node = temp->setRightChild(new Node(val));
							break;
						}
						else
						{
							temp = temp->getRightChild();
						}
						
					}
					else
					{
						return false;
					}
				}
				// The following code is for updating heights and balancing.
				temp = added_node;
				while(temp != 0)
				{
					temp->updateHeight();
					balanceAtNode(temp);
					temp = temp->getParent();
				}
			}
			return true;
		}

		// Returns:
		// 		true: If removal is successful
		// 		false: If item is not found in the tree
		//
		bool remove(int val)
		{
			if(root == 0) return false;
			Node *replacement, *replacement_parent, *temp_node;
			Node * to_be_removed = findNode(val);			
			if(to_be_removed == 0) return false;

			Node * p = to_be_removed->getParent();
			
			enum {left, right} side;
			if(p != 0)
			{
				if(p->getLeftChild() == to_be_removed) side = left;
				else side = right;
			}

			int bal = to_be_removed->getBalance();

			if(to_be_removed->getLeftChild() == 0 && to_be_removed->getRightChild() == 0)
			{
				if(p != 0)
				{
					if(side == left) p->setLeftChild((Node*)0);
					else p->setRightChild((Node*)0);
					
					delete to_be_removed;
					p->updateHeight();
					balanceAtNode(p);
				}
				else
				{
					setRoot((Node*)0);
					delete to_be_removed;
				}

			}
			else if(to_be_removed->getRightChild() == 0)
			{
				if(p != 0)
				{
					if(side == left) p->setLeftChild(to_be_removed->getLeftChild());
					else p->setRightChild(to_be_removed->getLeftChild());
					
					delete to_be_removed;
					p->updateHeight();
					balanceAtNode(p);
				}
				else
				{
					setRoot(to_be_removed->getLeftChild());
					delete to_be_removed;
				}
			}

			else if(to_be_removed->getLeftChild() == 0)
			{
				if(p != 0)
				{
					if(side == left) p->setLeftChild(to_be_removed->getRightChild());
					else p->setRightChild(to_be_removed->getRightChild());
					
					delete to_be_removed;
					p->updateHeight();
					balanceAtNode(p);
				}
				else
				{
					setRoot(to_be_removed->getRightChild());
					delete to_be_removed;
				}
			}
			else
			{
				if(bal > 0)
				{
					if(to_be_removed->getLeftChild()->getRightChild() == 0)
					{
						replacement = to_be_removed->getLeftChild();
						replacement->setRightChild(to_be_removed->getRightChild());
						
						temp_node = replacement;
						
					
					}
					else
					{
						replacement = to_be_removed->getLeftChild()->getRightChild();
						while(replacement->getRightChild() != 0)
						{
							replacement = replacement->getRightChild();
						}
						replacement_parent = replacement->getParent();
						replacement_parent->setRightChild(replacement->getLeftChild());

						temp_node = replacement_parent;

						replacement->setLeftChild(to_be_removed->getLeftChild());
						replacement->setRightChild(to_be_removed->getRightChild());
					}
				}
				else
				{
					if(to_be_removed->getRightChild()->getLeftChild() == 0)
					{
						replacement = to_be_removed->getRightChild();
						replacement->setLeftChild(to_be_removed->getLeftChild());
						
						temp_node = replacement;
						
					
					}
					else
					{
						replacement = to_be_removed->getRightChild()->getLeftChild();
						while(replacement->getLeftChild() != 0)
						{
							replacement = replacement->getLeftChild();
						}
						replacement_parent = replacement->getParent();
						replacement_parent->setLeftChild(replacement->getRightChild());

						temp_node = replacement_parent;

						replacement->setLeftChild(to_be_removed->getLeftChild());
						replacement->setRightChild(to_be_removed->getRightChild());
					}
				}		
				if(p != 0)
				{
					if(side == left) p->setLeftChild(replacement);
					else p->setRightChild(replacement);
					
					delete to_be_removed;
				}
				else
				{
					setRoot(replacement);
					delete to_be_removed;
				}
				
				balanceAtNode(temp_node);
			}

			return true;
		}
		int getHeight()
		{
			return root->getHeight();
		}
};