Same thing with Claude:

Python: first try

%<------%<------%<------
# Red-Black Tree implementation using arrays
# Colors: RED = True, BLACK = False

# Each node is represented as a tuple in the array:
# (key, color, parent_index, left_child_index, right_child_index)
# NIL nodes are represented by -1 index

def create_tree():
    # Initialize empty tree with just a NIL root
    tree = []
    # Add NIL node (key=None, color=BLACK, parent=-1, left=-1, right=-1)
    tree.append((None, False, -1, -1, -1))
    return tree

def is_nil(tree, index):
    return index == -1 or index == 0

def get_root_index(tree):
    # Root is at index 1 if it exists, otherwise -1
    return 1 if len(tree) > 1 else -1

def left_rotate(tree, x_index):
    # Get node x and its right child y
    x_key, x_color, x_parent, x_left, x_right = tree[x_index]
    y_index = x_right

    if is_nil(tree, y_index):
        return  # Can't rotate if right child is NIL

    y_key, y_color, y_parent, y_left, y_right = tree[y_index]

    # Turn y's left subtree into x's right subtree
    tree[x_index] = (x_key, x_color, x_parent, x_left, y_left)

    if not is_nil(tree, y_left):
        # Update parent of y's left child
        y_left_key, y_left_color, _, y_left_left, y_left_right = tree[y_left]
        tree[y_left] = (y_left_key, y_left_color, x_index, y_left_left,
y_left_right)

    # Link y's parent to x's parent
    tree[y_index] = (y_key, y_color, x_parent, x_index, y_right)

    # Link x's parent to y
    if is_nil(tree, x_parent):
        # x was the root
        pass
    else:
        parent_key, parent_color, parent_parent, parent_left, parent_right =
tree[x_parent]
        if x_index == parent_left:
            tree[x_parent] = (parent_key, parent_color, parent_parent, y_index,
parent_right)
        else:
            tree[x_parent] = (parent_key, parent_color, parent_parent,
parent_left, y_index)

    # Put x on y's left
    tree[x_index] = (x_key, x_color, y_index, x_left, y_left)

def right_rotate(tree, y_index):
    # Get node y and its left child x
    y_key, y_color, y_parent, y_left, y_right = tree[y_index]
    x_index = y_left

    if is_nil(tree, x_index):
        return  # Can't rotate if left child is NIL

    x_key, x_color, x_parent, x_left, x_right = tree[x_index]

    # Turn x's right subtree into y's left subtree
    tree[y_index] = (y_key, y_color, y_parent, x_right, y_right)

    if not is_nil(tree, x_right):
        # Update parent of x's right child
        x_right_key, x_right_color, _, x_right_left, x_right_right =
tree[x_right]
        tree[x_right] = (x_right_key, x_right_color, y_index, x_right_left,
x_right_right)

    # Link x's parent to y's parent
    tree[x_index] = (x_key, x_color, y_parent, x_left, y_index)

    # Link y's parent to x
    if is_nil(tree, y_parent):
        # y was the root
        pass
    else:
        parent_key, parent_color, parent_parent, parent_left, parent_right =
tree[y_parent]
        if y_index == parent_left:
            tree[x_parent] = (parent_key, parent_color, parent_parent, x_index,
parent_right)
        else:
            tree[x_parent] = (parent_key, parent_color, parent_parent,
parent_left, x_index)

    # Put y on x's right
    tree[y_index] = (y_key, y_color, x_index, x_right, y_right)

def rb_insert_fixup(tree, z_index):
    while True:
        # Get z's parent
        _, _, z_parent, _, _ = tree[z_index]

        if is_nil(tree, z_parent):
            # z is the root
            break

        # Get z's parent's info
        _, parent_color, parent_parent, _, _ = tree[z_parent]

        if not parent_color:  # Parent is BLACK
            break

        # If we're here, parent is RED
        # Get grandparent info
        _, _, grandparent_parent, grandparent_left, grandparent_right =
tree[parent_parent]

        # Check if parent is left or right child of grandparent
        if z_parent == grandparent_left:
            y_index = grandparent_right  # y is z's uncle

            if not is_nil(tree, y_index) and tree[y_index][1]:  # Uncle is RED
                # Case 1: z's uncle y is red
                # Make parent and uncle BLACK
                parent_key, _, parent_parent, parent_left, parent_right =
tree[z_parent]
                tree[z_parent] = (parent_key, False, parent_parent, parent_left,
parent_right)

                y_key, _, y_parent, y_left, y_right = tree[y_index]
                tree[y_index] = (y_key, False, y_parent, y_left, y_right)

                # Make grandparent RED
                grandparent_key, _, grandparent_parent, grandparent_left,
grandparent_right = tree[parent_parent]
                tree[parent_parent] = (grandparent_key, True,
grandparent_parent, grandparent_left, grandparent_right)

                # Move z to grandparent and continue
                z_index = parent_parent
            else:
                # Uncle is BLACK or NIL
                if z_index == parent_right:
                    # Case 2: z is a right child
                    z_index = z_parent
                    left_rotate(tree, z_index)
                    _, _, z_parent, _, _ = tree[z_index]

                # Case 3: z is a left child
                parent_key, _, parent_parent, parent_left, parent_right =
tree[z_parent]
                tree[z_parent] = (parent_key, False, parent_parent, parent_left,
parent_right)

                grandparent_key, _, grandparent_parent, grandparent_left,
grandparent_right = tree[parent_parent]
                tree[parent_parent] = (grandparent_key, True,
grandparent_parent, grandparent_left, grandparent_right)

                right_rotate(tree, parent_parent)
                break
        else:
            # Mirror image of above
            y_index = grandparent_left  # y is z's uncle

            if not is_nil(tree, y_index) and tree[y_index][1]:  # Uncle is RED
                # Case 1: z's uncle y is red
                # Make parent and uncle BLACK
                parent_key, _, parent_parent, parent_left, parent_right =
tree[z_parent]
                tree[z_parent] = (parent_key, False, parent_parent, parent_left,
parent_right)

                y_key, _, y_parent, y_left, y_right = tree[y_index]
                tree[y_index] = (y_key, False, y_parent, y_left, y_right)

                # Make grandparent RED
                grandparent_key, _, grandparent_parent, grandparent_left,
grandparent_right = tree[parent_parent]
                tree[parent_parent] = (grandparent_key, True,
grandparent_parent, grandparent_left, grandparent_right)

                # Move z to grandparent and continue
                z_index = parent_parent
            else:
                # Uncle is BLACK or NIL
                if z_index == parent_left:
                    # Case 2: z is a left child
                    z_index = z_parent
                    right_rotate(tree, z_index)
                    _, _, z_parent, _, _ = tree[z_index]

                # Case 3: z is a right child
                parent_key, _, parent_parent, parent_left, parent_right =
tree[z_parent]
                tree[z_parent] = (parent_key, False, parent_parent, parent_left,
parent_right)

                grandparent_key, _, grandparent_parent, grandparent_left,
grandparent_right = tree[parent_parent]
                tree[parent_parent] = (grandparent_key, True,
grandparent_parent, grandparent_left, grandparent_right)

                left_rotate(tree, parent_parent)
                break

    # Make root black
    root_index = get_root_index(tree)
    if not is_nil(tree, root_index):
        root_key, _, root_parent, root_left, root_right = tree[root_index]
        tree[root_index] = (root_key, False, root_parent, root_left, root_right)

def rb_insert(tree, key):
    # Create a new node
    new_node_index = len(tree)
    # Initially colored RED, with NIL children
    tree.append((key, True, -1, 0, 0))

    # Find the correct position for the new node
    y_index = 0  # NIL
    x_index = get_root_index(tree)

    while not is_nil(tree, x_index):
        y_index = x_index
        x_key, _, _, x_left, x_right = tree[x_index]

        if key < x_key:
            x_index = x_left
        else:
            x_index = x_right

    # Set parent of the new node
    tree[new_node_index] = (key, True, y_index, 0, 0)

    # Insert the new node as a child of y
    if is_nil(tree, y_index):
        # Tree was empty, new node is the root
        pass
    else:
        y_key, y_color, y_parent, y_left, y_right = tree[y_index]

        if key < y_key:
            tree[y_index] = (y_key, y_color, y_parent, new_node_index, y_right)
        else:
            tree[y_index] = (y_key, y_color, y_parent, y_left, new_node_index)

    # Fix the red-black properties
    rb_insert_fixup(tree, new_node_index)

def rb_search(tree, key):
    x_index = get_root_index(tree)

    while not is_nil(tree, x_index):
        x_key, _, _, x_left, x_right = tree[x_index]

        if key == x_key:
            return x_index
        elif key < x_key:
            x_index = x_left
        else:
            x_index = x_right

    return -1  # Key not found

def inorder_traverse(tree, node_index, result):
    if is_nil(tree, node_index):
        return

    node_key, node_color, _, node_left, node_right = tree[node_index]

    inorder_traverse(tree, node_left, result)
    result.append((node_key, "RED" if node_color else "BLACK"))
    inorder_traverse(tree, node_right, result)

def print_tree(tree):
    result = []
    root_index = get_root_index(tree)
    inorder_traverse(tree, root_index, result)
    return result

# Example usage
def example():
    tree = create_tree()

    # Insert some values
    for key in [10, 20, 30, 15, 25, 5, 35]:
        rb_insert(tree, key)

    # Search for a key
    found_index = rb_search(tree, 15)
    if found_index != -1:
        print(f"Found key 15 at index {found_index}")
    else:
        print("Key 15 not found")

    # Print the tree in order
    print("Inorder traversal (with colors):")
    result = print_tree(tree)
    for key, color in result:
        print(f"{key} ({color})")

if __name__ == "__main__":
    example()
%<------%<------%<------


POV-Ray: first try


%<------%<------%<------
// Red-Black Tree implementation in POV-Ray using macros
// Colors: RED = 1, BLACK = 0

// Global arrays to store the tree
// Each node contains: key, color, parent_index, left_child_index,
right_child_index
#declare TreeSize = 100; // Maximum size of the tree
#declare TreeKeys = array[TreeSize];
#declare TreeColors = array[TreeSize];
#declare TreeParents = array[TreeSize];
#declare TreeLefts = array[TreeSize];
#declare TreeRights = array[TreeSize];
#declare TreeCount = 1; // Start at 1 because 0 is reserved for NIL

// Initialize the tree with a NIL node at index 0
#macro InitTree()
    #declare TreeKeys[0] = -1;    // NIL key (arbitrary value)
    #declare TreeColors[0] = 0;   // NIL is BLACK
    #declare TreeParents[0] = -1; // NIL parent
    #declare TreeLefts[0] = -1;   // NIL left
    #declare TreeRights[0] = -1;  // NIL right
    #declare TreeCount = 1;       // Reset count to 1
#end

// Check if node is NIL
#macro IsNil(index)
    #local result = (index = 0 | index = -1);
    result
#end

// Get the root index
#macro GetRootIndex()
    #local result = 1;
    #if(TreeCount <= 1)
        #local result = -1;
    #end
    result
#end

// Left Rotate operation
#macro LeftRotate(x_index)
    #local x_key = TreeKeys[x_index];
    #local x_color = TreeColors[x_index];
    #local x_parent = TreeParents[x_index];
    #local x_left = TreeLefts[x_index];
    #local x_right = TreeRights[x_index];
    #local y_index = x_right;

    #if(!IsNil(y_index))
        #local y_key = TreeKeys[y_index];
        #local y_color = TreeColors[y_index];
        #local y_left = TreeLefts[y_index];
        #local y_right = TreeRights[y_index];

        // Turn y's left subtree into x's right subtree
        #declare TreeRights[x_index] = y_left;

        #if(!IsNil(y_left))
            #declare TreeParents[y_left] = x_index;
        #end

        // Link y's parent to x's parent
        #declare TreeParents[y_index] = x_parent;

        // Link x's parent to y
        #if(IsNil(x_parent))
            // x was the root, do nothing
        #else
            #if(x_index = TreeLefts[x_parent])
                #declare TreeLefts[x_parent] = y_index;
            #else
                #declare TreeRights[x_parent] = y_index;
            #end
        #end

        // Put x on y's left
        #declare TreeLefts[y_index] = x_index;
        #declare TreeParents[x_index] = y_index;
    #end
#end

// Right Rotate operation
#macro RightRotate(y_index)
    #local y_key = TreeKeys[y_index];
    #local y_color = TreeColors[y_index];
    #local y_parent = TreeParents[y_index];
    #local y_left = TreeLefts[y_index];
    #local y_right = TreeRights[y_index];
    #local x_index = y_left;

    #if(!IsNil(x_index))
        #local x_key = TreeKeys[x_index];
        #local x_color = TreeColors[x_index];
        #local x_left = TreeLefts[x_index];
        #local x_right = TreeRights[x_index];

        // Turn x's right subtree into y's left subtree
        #declare TreeLefts[y_index] = x_right;

        #if(!IsNil(x_right))
            #declare TreeParents[x_right] = y_index;
        #end

        // Link x's parent to y's parent
        #declare TreeParents[x_index] = y_parent;

        // Link y's parent to x
        #if(IsNil(y_parent))
            // y was the root, do nothing
        #else
            #if(y_index = TreeLefts[y_parent])
                #declare TreeLefts[y_parent] = x_index;
            #else
                #declare TreeRights[y_parent] = x_index;
            #end
        #end

        // Put y on x's right
        #declare TreeRights[x_index] = y_index;
        #declare TreeParents[y_index] = x_index;
    #end
#end

// Fix red-black properties after insertion
#macro RBInsertFixup(z_index)
    #local continue_loop = true;

    #while(continue_loop)
        #local z_parent = TreeParents[z_index];

        #if(IsNil(z_parent))
            // z is the root
            #local continue_loop = false;
        #else
            #local parent_color = TreeColors[z_parent];

            #if(parent_color = 0) // Parent is BLACK
                #local continue_loop = false;
            #else
                // Parent is RED
                #local parent_parent = TreeParents[z_parent];

                #if(z_parent = TreeLefts[parent_parent]) // Parent is left child
                    #local y_index = TreeRights[parent_parent]; // Uncle

                    #if(!IsNil(y_index) & TreeColors[y_index] = 1) // Uncle is
RED
                        // Case 1: Uncle is red
                        #declare TreeColors[z_parent] = 0; // Parent -> BLACK
                        #declare TreeColors[y_index] = 0;  // Uncle -> BLACK
                        #declare TreeColors[parent_parent] = 1; // Grandparent
-> RED
                        #local z_index = parent_parent;
                    #else
                        // Uncle is BLACK or NIL
                        #if(z_index = TreeRights[z_parent]) // z is right child
                            // Case 2: z is right child
                            #local z_index = z_parent;
                            LeftRotate(z_index)
                            #local z_parent = TreeParents[z_index];
                        #end

                        // Case 3: z is left child
                        #declare TreeColors[z_parent] = 0; // Parent -> BLACK
                        #declare TreeColors[parent_parent] = 1; // Grandparent
-> RED
                        RightRotate(parent_parent)
                        #local continue_loop = false;
                    #end
                #else // Parent is right child
                    #local y_index = TreeLefts[parent_parent]; // Uncle

                    #if(!IsNil(y_index) & TreeColors[y_index] = 1) // Uncle is
RED
                        // Case 1: Uncle is red
                        #declare TreeColors[z_parent] = 0; // Parent -> BLACK
                        #declare TreeColors[y_index] = 0;  // Uncle -> BLACK
                        #declare TreeColors[parent_parent] = 1; // Grandparent
-> RED
                        #local z_index = parent_parent;
                    #else
                        // Uncle is BLACK or NIL
                        #if(z_index = TreeLefts[z_parent]) // z is left child
                            // Case 2: z is left child
                            #local z_index = z_parent;
                            RightRotate(z_index)
                            #local z_parent = TreeParents[z_index];
                        #end

                        // Case 3: z is right child
                        #declare TreeColors[z_parent] = 0; // Parent -> BLACK
                        #declare TreeColors[parent_parent] = 1; // Grandparent
-> RED
                        LeftRotate(parent_parent)
                        #local continue_loop = false;
                    #end
                #end
            #end
        #end
    #end

    // Make root black
    #local root_index = GetRootIndex();
    #if(!IsNil(root_index))
        #declare TreeColors[root_index] = 0;
    #end
#end

// Insert a new key into the tree
#macro RBInsert(key)
    // Create a new node
    #local new_node_index = TreeCount;
    #declare TreeCount = TreeCount + 1;

    // Initialize node as RED with NIL children
    #declare TreeKeys[new_node_index] = key;
    #declare TreeColors[new_node_index] = 1; // RED
    #declare TreeParents[new_node_index] = -1;
    #declare TreeLefts[new_node_index] = 0; // NIL
    #declare TreeRights[new_node_index] = 0; // NIL

    // Find the correct position for the new node
    #local y_index = 0; // NIL
    #local x_index = GetRootIndex();

    #while(!IsNil(x_index))
        #local y_index = x_index;
        #local x_key = TreeKeys[x_index];

        #if(key < x_key)
            #local x_index = TreeLefts[x_index];
        #else
            #local x_index = TreeRights[x_index];
        #end
    #end

    // Set parent of the new node
    #declare TreeParents[new_node_index] = y_index;

    // Insert the new node as a child of y
    #if(IsNil(y_index))
        // Tree was empty, new node is the root
        // Do nothing, already set up correctly
    #else
        #if(key < TreeKeys[y_index])
            #declare TreeLefts[y_index] = new_node_index;
        #else
            #declare TreeRights[y_index] = new_node_index;
        #end
    #end

    // Fix the red-black properties
    RBInsertFixup(new_node_index)
#end

// Search for a key in the tree
#macro RBSearch(key)
    #local found_index = -1;
    #local x_index = GetRootIndex();

    #while(!IsNil(x_index) & found_index = -1)
        #local x_key = TreeKeys[x_index];

        #if(key = x_key)
            #local found_index = x_index;
        #elseif(key < x_key)
            #local x_index = TreeLefts[x_index];
        #else
            #local x_index = TreeRights[x_index];
        #end
    #end

    found_index
#end

// Visualization macros

// Draw a single node
#macro DrawNode(index, x, y, z, level)
    #local node_radius = 0.2;
    #local color_value = rgb <1,0,0>;  // RED
    #if(TreeColors[index] = 0)
        #local color_value = rgb <0,0,0>;  // BLACK
    #end

    sphere {
        <x, y, z>, node_radius
        pigment { color color_value }
        finish {
            ambient 0.2
            diffuse 0.8
            specular 0.5
        }
    }

    // Add text for the key value
    #local key_str = str(TreeKeys[index], 0, 0);
    text {
        ttf "arial.ttf", key_str, 0.1, <0, 0, 0>
        pigment { color rgb <1, 1, 1> }  // White text
        scale 0.15
        translate <x-0.1, y-0.05, z+node_radius+0.01>
    }

    // Draw left child
    #local left_index = TreeLefts[index];
    #if(!IsNil(left_index))
        #local x_offset = 2.0 / pow(2, level);
        #local new_x = x - x_offset;
        #local new_y = y - 1;
        #local new_z = z;

        cylinder {
            <x, y, z>, <new_x, new_y, new_z>, 0.03
            pigment { color rgb <0.5, 0.5, 0.5> }
        }

        DrawNode(left_index, new_x, new_y, new_z, level + 1)
    #end

    // Draw right child
    #local right_index = TreeRights[index];
    #if(!IsNil(right_index))
        #local x_offset = 2.0 / pow(2, level);
        #local new_x = x + x_offset;
        #local new_y = y - 1;
        #local new_z = z;

        cylinder {
            <x, y, z>, <new_x, new_y, new_z>, 0.03
            pigment { color rgb <0.5, 0.5, 0.5> }
        }

        DrawNode(right_index, new_x, new_y, new_z, level + 1)
    #end
#end

// Visualize the entire tree
#macro VisualizeTree()
    #local root_index = GetRootIndex();

    #if(!IsNil(root_index))
        DrawNode(root_index, 0, 0, 0, 1)
    #end
#end

// Print information about a node (for debugging)
#macro PrintNode(index)
    #debug concat(
        "Node ", str(index, 0, 0), ": ",
        "Key=", str(TreeKeys[index], 0, 0), ", ",
        "Color=", str(TreeColors[index], 0, 0), ", ",
        "Parent=", str(TreeParents[index], 0, 0), ", ",
        "Left=", str(TreeLefts[index], 0, 0), ", ",
        "Right=", str(TreeRights[index], 0, 0), "\n"
    )
#end

// Example usage in a POV-Ray scene
#macro ExampleTree()
    InitTree()

    // Insert some values
    RBInsert(10)
    RBInsert(20)
    RBInsert(30)
    RBInsert(15)
    RBInsert(25)
    RBInsert(5)
    RBInsert(35)

    // Search for a key
    #local found_index = RBSearch(15);
    #if(found_index != -1)
        #debug concat("Found key 15 at index ", str(found_index, 0, 0), "\n")
    #else
        #debug "Key 15 not found\n"
    #end

    // Print all nodes
    #debug "Tree contents:\n"
    #for(i, 1, TreeCount-1)
        PrintNode(i)
    #end

    VisualizeTree()
#end

// Scene setup
camera {
    location <0, 0, -10>
    look_at <0, 0, 0>
    angle 30
}

light_source {
    <5, 5, -10>
    color rgb <1, 1, 1>
}

light_source {
    <-5, 5, -10>
    color rgb <0.5, 0.5, 0.5>
}

background { color rgb <1, 1, 1> }

// Run the example
ExampleTree()

%<------%<------%<------

Post a reply to this message