' Red-Black Tree — self-balancing BST with color invariants 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 parent(1000) AS LONG
    LOCAL isRed(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 newnode AS LONG
    LOCAL uncle AS LONG
    LOCAL grandparent AS LONG
    LOCAL temp AS LONG
    LOCAL inorder(1000) AS LONG
    LOCAL inorderCount AS LONG
    LOCAL stack(1000) AS LONG
    LOCAL stackSize AS LONG
    LOCAL lineStr AS STRING
    LOCAL elemStr AS STRING
    LOCAL testCount AS LONG
    LOCAL passCount AS LONG
    LOCAL failCount AS LONG
    LOCAL searchKey AS LONG
    LOCAL found AS LONG
    LOCAL blackCount AS LONG
    LOCAL refCount AS LONG
    LOCAL firstLeafBlack AS LONG
    LOCAL leafBlackCount(1000) AS LONG
    LOCAL blackErrors AS LONG
    testCount = 0
    passCount = 0
    failCount = 0
    PRINT "============================================"
    PRINT "        RED-BLACK TREE"
    PRINT "============================================"
    PRINT ""
    nodeCount = 0
    root = -1
    PRINT "Inserting values:"
    PRINT ""
    FOR i = 0 TO 19
        keyVal = (i * 23 + 7) MOD 60
        PRINT " Insert " + STR$(keyVal)
        IF nodeCount = 0 THEN
            keys(0) = keyVal
            leftChild(0) = -1
            rightChild(0) = -1
            parent(0) = -1
            isRed(0) = 0
            root = 0
            nodeCount = 1
        ELSE
            current = root
            DO WHILE current <> -1
                IF keyVal < keys(current) THEN
                    IF leftChild(current) = -1 THEN
                        EXIT DO
                    END IF
                    current = leftChild(current)
                ELSE
                    IF keyVal > keys(current) THEN
                        IF rightChild(current) = -1 THEN
                            EXIT DO
                        END IF
                        current = rightChild(current)
                    ELSE
                        GOTO skipRbInsert
                    END IF
                END IF
            LOOP
            newnode = nodeCount
            keys(newnode) = keyVal
            leftChild(newnode) = -1
            rightChild(newnode) = -1
            parent(newnode) = current
            isRed(newnode) = 1
            IF keyVal < keys(current) THEN
                leftChild(current) = newnode
            ELSE
                rightChild(current) = newnode
            END IF
            nodeCount = nodeCount + 1
            i = newnode
            DO WHILE parent(i) <> -1 AND isRed(parent(i)) = 1
                IF parent(parent(i)) = -1 THEN
                    EXIT DO
                END IF
                IF leftChild(parent(parent(i))) = parent(i) THEN
                    uncle = rightChild(parent(parent(i)))
                ELSE
                    uncle = leftChild(parent(parent(i)))
                END IF
                IF uncle <> -1 AND isRed(uncle) = 1 THEN
                    isRed(parent(i)) = 0
                    isRed(uncle) = 0
                    isRed(parent(parent(i))) = 1
                    i = parent(parent(i))
                ELSE
                    IF leftChild(parent(parent(i))) = parent(i) THEN
                        IF rightChild(parent(i)) = i THEN
                            temp = leftChild(i)
                            leftChild(i) = parent(i)
                            rightChild(parent(i)) = temp
                            IF temp <> -1 THEN
                                parent(temp) = parent(i)
                            END IF
                            parent(parent(i)) = i
                            parent(i) = i
                        END IF
                        isRed(parent(parent(i))) = 1
                        isRed(parent(i)) = 0
                        IF parent(parent(parent(i))) <> -1 THEN
                            IF leftChild(parent(parent(parent(i)))) = parent(parent(i)) THEN
                                leftChild(parent(parent(parent(i)))) = parent(i)
                            ELSE
                                rightChild(parent(parent(parent(i)))) = parent(i)
                            END IF
                        END IF
                        parent(parent(i)) = parent(parent(parent(i)))
                        temp = rightChild(parent(i))
                        rightChild(parent(i)) = parent(parent(i))
                        leftChild(parent(parent(i))) = temp
                        IF temp <> -1 THEN
                            parent(temp) = parent(parent(i))
                        END IF
                        parent(parent(parent(i))) = parent(i)
                    ELSE
                        IF leftChild(parent(i)) = i THEN
                            temp = rightChild(i)
                            rightChild(i) = parent(i)
                            leftChild(parent(i)) = temp
                            IF temp <> -1 THEN
                                parent(temp) = parent(i)
                            END IF
                            parent(parent(i)) = i
                            parent(i) = i
                        END IF
                        isRed(parent(parent(i))) = 1
                        isRed(parent(i)) = 0
                        IF parent(parent(parent(i))) <> -1 THEN
                            IF leftChild(parent(parent(parent(i)))) = parent(parent(i)) THEN
                                leftChild(parent(parent(parent(i)))) = parent(i)
                            ELSE
                                rightChild(parent(parent(parent(i)))) = parent(i)
                            END IF
                        END IF
                        parent(parent(i)) = parent(parent(parent(i)))
                        temp = leftChild(parent(i))
                        leftChild(parent(i)) = parent(parent(i))
                        rightChild(parent(parent(i))) = temp
                        IF temp <> -1 THEN
                            parent(temp) = parent(parent(i))
                        END IF
                        parent(parent(parent(i))) = parent(i)
                    END IF
                END IF
            LOOP
            isRed(root) = 0
        END IF
skipRbInsert:
    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 ""
    j = 1
    FOR i = 1 TO inorderCount - 1
        IF inorder(i) < inorder(i - 1) THEN
            j = 0
        END IF
    NEXT i
    testCount = testCount + 1
    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 "     RED-BLACK PROPERTY CHECK"
    PRINT "============================================"
    PRINT ""
    blackErrors = 0
    IF isRed(root) = 1 THEN
        blackErrors = blackErrors + 1
        PRINT "ERROR: Root must be black"
    END IF
    FOR i = 0 TO nodeCount - 1
        IF isRed(i) = 1 THEN
            IF leftChild(i) <> -1 AND isRed(leftChild(i)) = 1 THEN
                blackErrors = blackErrors + 1
            END IF
            IF rightChild(i) <> -1 AND isRed(rightChild(i)) = 1 THEN
                blackErrors = blackErrors + 1
            END IF
        END IF
    NEXT i
    IF blackErrors = 0 THEN
        PRINT "Red-black invariants maintained"
        testCount = testCount + 1
        passCount = passCount + 1
    ELSE
        PRINT "Red-black invariants violated: " + STR$(blackErrors)
        failCount = failCount + 1
    END IF
    PRINT ""
    PRINT "============================================"
    PRINT "     SEARCH IN RED-BLACK TREE"
    PRINT "============================================"
    PRINT ""
    FOR searchKey = 0 TO 59
        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 "     BLACK HEIGHT VERIFICATION"
    PRINT "============================================"
    PRINT ""
    FOR i = nodeCount - 1 TO 0 STEP -1
        blackCount = 0
        IF isRed(i) = 0 THEN
            blackCount = 1
        END IF
        IF leftChild(i) = -1 AND rightChild(i) = -1 THEN
            leafBlackCount(i) = blackCount
        ELSE
            IF leftChild(i) <> -1 THEN
                leafBlackCount(i) = leafBlackCount(leftChild(i)) + blackCount
            ELSE
                IF rightChild(i) <> -1 THEN
                    leafBlackCount(i) = leafBlackCount(rightChild(i)) + blackCount
                END IF
            END IF
        END IF
    NEXT i
    PRINT "Black height verification complete"
    PRINT ""
    PRINT "Results: " + STR$(passCount) + " passed, " + STR$(failCount) + " failed of " + STR$(testCount)
    FUNCTION = 0
END FUNCTION
