LONG/LONG : Key/Value : AVL Balanced Binary Tree (DLL & Class)

[Stanley Durham]

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

LONG/LONG : 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 (about half the speed of a hash)
Can handle millions of Key/Value pairs
Tree always in order (and balanced)
Traverse tree in order
Fast inserts and deletes anywhere in tree (unlike an array)
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

 
 
 
'PBCC 5, PBWin 9
    'LONG/LONG : 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 (about half the speed of a hash)
    '    Can handle millions of Key/Value pairs
    '    Tree always in order (and balanced)
    '    Traverse tree in order
    '    Fast inserts and deletes anywhere in tree (unlike an array)
    '    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 "LLTreeC_DLL-1.inc" in same folder as source code
    '#Include Once "LLTreeC_DLL-1.inc"
    '
    'put "LLTreeC_DLL-1.DLL" in same folder as source code
    '
    'LOCAL tree as LLTreeI
    'tree = NewCom ClsId $LLTreeC_GUID Lib "LLTreeC_DLL-1.DLL"
    '   start using
 
$LLTreeC_GUID = Guid$("{B919060D-7654-4E11-B179-E485969A1D7B}")
$LLTreeI_GUID = Guid$("{BDFB0E56-6F6B-4096-8A2A-F1522E40BEB5}")
 
Interface LLTreeI $LLTreeI_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 it 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(ByVal key As Long, ByVal value As Long) As Long
        'add Key/Value to tree
        '   fail if Key exist
        '   return node handle if succeed
        '       return False if fail
 
    Method Set(ByVal key As Long, ByVal value As Long) 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(ByVal key As Long) As Long
        'get Value associated with Key
 
    Method Contains(ByVal key As Long) As Long
        'see if Key in tree
        '   return Node handle if found (non-zero)
        '   FALSE if not found
 
    Method Delete(ByVal Key As Long)
        'remove Key/Value from tree
 
    Method Replace(ByVal oldKey As Long, ByVal newKey As Long)
        '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 Long
        'get Key at current node position
 
    Method GoSetValue(ByVal hNode As Long, ByVal value As Long)
        'change Value at current node position
 
    Method GoGetValue(ByVal hNode As Long) As Long
        'get Value at current node position
 
    Method Store() As String
        'get whole tree as string (persist)
 
    Method Restore(ByVal storedTree As String)
        'build tree from storage string
        '   current contents cleared
 
    Method StoreValidate(ByVal storedTree As String) As Long
        'True/False if string is valid
        '   storage strings protected with two unique DWord validation hashes - front/back
 
End Interface