Announcement

Collapse

Forum Guidelines

This forum is for finished source code that is working properly. If you have questions about this or any other source code, please post it in one of the Discussion Forums, not here.
See more
See less

STRING: AVL Balanced Binary Tree (lite obj & class)

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • STRING: AVL Balanced Binary Tree (lite obj & class)

    DLL: PB 4/8 ok
    Class: PB 5/9
    free: use at your own risk

    String/String, Key/Value, AVL Tree
    google "AVL tree"

    Keys must be unique

    Fast - about half the speed of a hash
    find 100,000 strings 0.55 seconds (netbook)

    Keys always in alphabetical order (UCase)
    handle millions of items (memory)
    Values stored in buffers - NULL ok
    no null in Key - mess up compare


    Code:
     
     
     
    'PBCC 5, PBWin 9
        'STRING/STRING : Key/Value : AVL Balanced Binary Tree Class
        '   google "avl tree"
        '   Keys must be unique
        '   used for storing Key/Value pairs
        '   (in C++ STL called "map")
        'Pro:
        '    Extremely fast
        '       find 100,000 strings 0.55 seconds (netbook)
        '    Can handle millions of Key/Value pairs
        '    Tree always in order (and balanced)
        '    Fast inserts and deletes anywhere in tree
        '    Unlike Hash - can traverse in order
        '    Unlike Hash - doesn’t have to rebuild when Key count goes over/under productive range
        'Con:
        '    Uses more resources than an array
        '    Not quite as fast as a Hash
        '    If you don’t need to maintain order - Hash is faster
        'Implementation:
        '    Tree = upside-down tree (root on top)
        '    Tree may be stored/restored to/from string
        '
        'use:
        'put "SSTreeC_DLL-1.inc" in same folder as source code
        '#Include Once "SSTreeC_DLL-1.inc"
        '
        'put "SSTreeC_DLL-1.DLL" in same folder as source code
        '
        'LOCAL tree as SSTreeI
        'tree = NewCom ClsId $SSTreeC_GUID Lib "SSTreeC_DLL-1.DLL"
        '   start using
     
    $SSTreeC_GUID = Guid$("{331DF364-EDCB-4F06-951A-B590F9503595}")
    $SSTreeI_GUID = Guid$("{04471B50-3087-4D12-A29F-2AA70B439AEA}")
     
    Interface SSTreeI $SSTreeI_GUID
        Inherit IUnknown
        'Add() or Set()
        '   use Set() to always set Value
        '       Key added if not in tree
        '   use Add() to avoid overwriting existing Value
        '       Add() will fail if Key already in tree
        '
        'you can move back and forth in tree using cursor function; Go...()
        '   the cursor functions use a Node Handle
        '       you can get Key, get/set Value while using cursor
        'NOTE: once you hit END or BEGINNING of tree;
        '   you have to GoFirst() or GoLast() to get a valid Node Handle
        '
        '   you can't Delete(key) of node you're sitting on while using cursor functions
        '       save Key and move right or left before deleting Key
        '           (Node Handle would become invalid)
     
        Method Clear()
            'delete all data
            '   call Clear() before obj = NOTHING
            '   internal resources will immediately be freed
            '       instead of waiting till obj destroyed
     
        Method Count() As Long
            'get Key/Value count
     
        Method Add(In ByRef key As String, In ByRef value As String) As Long
            'add Key/Value to tree
            '   fail if Key exist
            '   return node handle if succeed
            '       return False if fail
     
        Method Set(In ByRef key As String, In ByRef value As String) As Long
            'set Key's Value
            '   add Key/Value if Key not in tree
            '   return non-zeor if succeed (node handle)
            '   return FALSE if fail
     
        Method Get(In ByRef key As String) As String
            'get Value associated with Key
     
        Method Contains(In ByRef key As String) As Long
            'see if Key in tree
            '   return Node handle if found (non-zero)
            '   FALSE if not found
     
        Method Delete(In ByRef key As String)
            'remove Key/Value from tree
     
        Method Replace(In ByRef oldKey As String, In ByRef newKey As String)
            'replace Old Key with New Key
            '   new Key must not exist
            '   slightly expensive operation
     
        Method GoFirst() As Long
            'got lowest Key in tree - Beginning - Far Left
            '   return Node Handle
            '       NULL if fail
     
        Method GoLast() As Long
            'go to highest Key in tree - End - Far Right
            '   return Node Handle
            '       NULL if fail
     
        Method GoNext(ByVal hNode As Long) As Long
            'go to next node in tree - right
            '   return Node Handle
            '       NULL if past end of tree
     
        Method GoPrev(ByVal hNode As Long) As Long
            'go left - previous node
            '   return Node Handle
            '       NULL if past beginning of tree
     
        Method GoGetKey(ByVal hNode As Long) As String
            'get Key at current node position
     
        Method GoSetValue(ByVal hNode As Long, In ByRef value As String)
            'change Value at current node position
     
        Method GoGetValue(ByVal hNode As Long) As String
            'get Value at current node position
     
        Method Store() As String
            'get whole tree as string (persist)
     
        Method Restore(In ByRef storedTree As String)
            'build tree from storage string
            '   current contents cleared
     
        Method StoreValidate(In ByRef storedTree As String) As Long
            'True/False if string is valid
            '   storage strings protected with two unique DWord validation hashes - front/back
     
    End Interface
    Attached Files
    Last edited by Stanley Durham; 6 May 2009, 01:03 PM.
    stanthemanstan~gmail
    Dead Theory Walking
    Range Trie Tree
    HLib ~ Free Data Container Lib ~ Arrays, Lists, Stacks, Queues, Deques, Trees, Hashes
Working...
X