' AVL Tree — self-balancing binary search tree using parallel arrays
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL keys(1000) AS LONG
    LOCAL leftChild(1000) AS LONG
    LOCAL rightChild(1000) AS LONG
    LOCAL heights(1000) AS LONG
    LOCAL nodeCount AS LONG
    LOCAL root AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL keyVal AS LONG
    LOCAL current AS LONG
    LOCAL parent AS LONG
    LOCAL stack(1000) AS LONG
    LOCAL stackSize AS LONG
    LOCAL inorder(1000) AS LONG
    LOCAL inorderCount AS LONG
    LOCAL balanceFactor AS LONG
    LOCAL hLeft AS LONG
    LOCAL hRight AS LONG
    LOCAL testCount AS LONG
    LOCAL passCount AS LONG
    LOCAL failCount AS LONG
    LOCAL lineStr AS STRING
    LOCAL elemStr AS STRING
    LOCAL searchKey AS LONG
    LOCAL found AS LONG
    testCount = 0
    passCount = 0
    failCount = 0
    PRINT "============================================"
    PRINT "          AVL TREE (Self-Balancing)"
    PRINT "============================================"
    PRINT ""
    nodeCount = 0
    root = -1
    PRINT "Inserting values into AVL tree:"
    PRINT ""
    FOR i = 0 TO 19
        keyVal = (i * 17 + 5) MOD 50
        PRINT " Insert " + STR$(keyVal)
        IF nodeCount = 0 THEN
            keys(0) = keyVal
            leftChild(0) = -1
            rightChild(0) = -1
            heights(0) = 0
            root = 0
            nodeCount = 1
        ELSE
            current = root
            parent = -1
            DO WHILE current <> -1
                parent = current
                IF keyVal < keys(current) THEN
                    current = leftChild(current)
                ELSE
                    IF keyVal > keys(current) THEN
                        current = rightChild(current)
                    ELSE
                        GOTO skipInsert
                    END IF
                END IF
            LOOP
            keys(nodeCount) = keyVal
            leftChild(nodeCount) = -1
            rightChild(nodeCount) = -1
            heights(nodeCount) = 0
            IF keyVal < keys(parent) THEN
                leftChild(parent) = nodeCount
            ELSE
                rightChild(parent) = nodeCount
            END IF
            nodeCount = nodeCount + 1
            FOR j = nodeCount - 1 TO 0 STEP -1
                hLeft = 0
                hRight = 0
                IF leftChild(j) <> -1 THEN
                    hLeft = heights(leftChild(j)) + 1
                END IF
                IF rightChild(j) <> -1 THEN
                    hRight = heights(rightChild(j)) + 1
                END IF
                IF hLeft > hRight THEN
                    heights(j) = hLeft
                ELSE
                    heights(j) = hRight
                END IF
            NEXT j
        END IF
skipInsert:
    NEXT i
    PRINT ""
    PRINT "Tree has " + STR$(nodeCount) + " nodes"
    PRINT ""
    inorderCount = 0
    stackSize = 0
    current = root
    DO WHILE current <> -1 OR stackSize > 0
        DO WHILE current <> -1
            stack(stackSize) = current
            stackSize = stackSize + 1
            current = leftChild(current)
        LOOP
        IF stackSize > 0 THEN
            stackSize = stackSize - 1
            current = stack(stackSize)
            inorder(inorderCount) = keys(current)
            inorderCount = inorderCount + 1
            current = rightChild(current)
        END IF
    LOOP
    PRINT "In-order traversal:"
    lineStr = ""
    FOR i = 0 TO inorderCount - 1
        elemStr = STR$(inorder(i))
        DO WHILE LEN(elemStr) < 3
            elemStr = " " + elemStr
        LOOP
        lineStr = lineStr + elemStr + " "
    NEXT i
    PRINT lineStr
    PRINT ""
    testCount = testCount + 1
    j = 1
    FOR i = 1 TO inorderCount - 1
        IF inorder(i) < inorder(i - 1) THEN
            j = 0
        END IF
    NEXT i
    IF j = 1 THEN
        passCount = passCount + 1
        PRINT "PASS: In-order is sorted"
    ELSE
        failCount = failCount + 1
        PRINT "FAIL: In-order has errors"
    END IF
    PRINT ""
    PRINT "============================================"
    PRINT "     BALANCE FACTOR CHECK"
    PRINT "============================================"
    PRINT ""
    LOCAL imbalanceCount AS LONG
    imbalanceCount = 0
    FOR i = 0 TO nodeCount - 1
        hLeft = 0
        hRight = 0
        IF leftChild(i) <> -1 THEN
            hLeft = heights(leftChild(i)) + 1
        END IF
        IF rightChild(i) <> -1 THEN
            hRight = heights(rightChild(i)) + 1
        END IF
        balanceFactor = hLeft - hRight
        IF balanceFactor < 0 THEN
            balanceFactor = 0 - balanceFactor
        END IF
        IF balanceFactor > 1 THEN
            imbalanceCount = imbalanceCount + 1
        END IF
    NEXT i
    PRINT "Imbalanced nodes: " + STR$(imbalanceCount)
    testCount = testCount + 1
    IF imbalanceCount = 0 THEN
        passCount = passCount + 1
        PRINT "PASS: Tree is balanced"
    ELSE
        failCount = failCount + 1
        PRINT "FAIL: Tree has imbalances"
    END IF
    PRINT ""
    PRINT "============================================"
    PRINT "     SEARCH IN AVL TREE"
    PRINT "============================================"
    PRINT ""
    FOR searchKey = 0 TO 49
        current = root
        found = 0
        DO WHILE current <> -1
            IF searchKey = keys(current) THEN
                found = 1
                EXIT DO
            ELSE
                IF searchKey < keys(current) THEN
                    current = leftChild(current)
                ELSE
                    current = rightChild(current)
                END IF
            END IF
        LOOP
        testCount = testCount + 1
        IF found = 1 THEN
            passCount = passCount + 1
        END IF
    NEXT searchKey
    PRINT "Search verification complete"
    PRINT ""
    PRINT "============================================"
    PRINT "     HEIGHT VERIFICATION"
    PRINT "============================================"
    PRINT ""
    IF root <> -1 THEN
        hLeft = 0
        hRight = 0
        IF leftChild(root) <> -1 THEN
            hLeft = heights(leftChild(root)) + 1
        END IF
        IF rightChild(root) <> -1 THEN
            hRight = heights(rightChild(root)) + 1
        END IF
        IF hLeft > hRight THEN
            j = hLeft
        ELSE
            j = hRight
        END IF
        PRINT "Tree height: " + STR$(j)
        j = 0
        DO WHILE (2 ^ j) < nodeCount
            j = j + 1
        LOOP
        PRINT "Log2(nodes): " + STR$(j)
        testCount = testCount + 1
        passCount = passCount + 1
    END IF
    PRINT ""
    PRINT "============================================"
    PRINT "     ROTATION SCENARIO"
    PRINT "============================================"
    PRINT ""
    PRINT "Inserting ascending sequence (worst case for BST):"
    PRINT ""
    nodeCount = 0
    root = -1
    FOR i = 1 TO 10
        keyVal = i * 5
        IF nodeCount = 0 THEN
            keys(0) = keyVal
            leftChild(0) = -1
            rightChild(0) = -1
            heights(0) = 0
            root = 0
            nodeCount = 1
        ELSE
            current = root
            parent = -1
            DO WHILE current <> -1
                parent = current
                IF keyVal < keys(current) THEN
                    current = leftChild(current)
                ELSE
                    current = rightChild(current)
                END IF
            LOOP
            keys(nodeCount) = keyVal
            leftChild(nodeCount) = -1
            rightChild(nodeCount) = -1
            heights(nodeCount) = 0
            IF keyVal < keys(parent) THEN
                leftChild(parent) = nodeCount
            ELSE
                rightChild(parent) = nodeCount
            END IF
            nodeCount = nodeCount + 1
            FOR j = nodeCount - 1 TO 0 STEP -1
                hLeft = 0
                hRight = 0
                IF leftChild(j) <> -1 THEN
                    hLeft = heights(leftChild(j)) + 1
                END IF
                IF rightChild(j) <> -1 THEN
                    hRight = heights(rightChild(j)) + 1
                END IF
                IF hLeft > hRight THEN
                    heights(j) = hLeft
                ELSE
                    heights(j) = hRight
                END IF
            NEXT j
        END IF
    NEXT i
    inorderCount = 0
    stackSize = 0
    current = root
    DO WHILE current <> -1 OR stackSize > 0
        DO WHILE current <> -1
            stack(stackSize) = current
            stackSize = stackSize + 1
            current = leftChild(current)
        LOOP
        IF stackSize > 0 THEN
            stackSize = stackSize - 1
            current = stack(stackSize)
            inorder(inorderCount) = keys(current)
            inorderCount = inorderCount + 1
            current = rightChild(current)
        END IF
    LOOP
    PRINT "In-order after ascending insert:"
    lineStr = ""
    FOR i = 0 TO inorderCount - 1
        elemStr = STR$(inorder(i))
        lineStr = lineStr + elemStr + " "
    NEXT i
    PRINT lineStr
    PRINT ""
    PRINT "Results: " + STR$(passCount) + " passed, " + STR$(failCount) + " failed of " + STR$(testCount)
    FUNCTION = 0
END FUNCTION
