|
 |
"ingo" <nomail@nomail> wrote:
> Same thing with Claude:
>
Just saw that Claude 3.7 is available again and gave it a go with the Claude
3.5 and some touch ups by me. It works, I think after a few tests. Deleting
nodes is not implemented. Also it may need some restructuring by putting things
in arrays that act as record/struct/object:
---%<------%<------%<---
// 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
#declare RootIndex = 0; // Track the root index explicitly
// 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] = 0; // NIL parent is itself
#declare TreeLefts[0] = 0; // NIL left is itself
#declare TreeRights[0] = 0; // NIL right is itself
#declare TreeCount = 1; // Reset count to 1
#declare RootIndex = 0; // Empty tree
#debug "Tree initialized\n"
#end
// Check if node is NIL
#macro IsNil(index)
#local result = (index = 0);
result
#end
// Get the root index
#macro GetRootIndex()
#debug concat("GetRootIndex: ", str(RootIndex, 0, 0), "\n")
RootIndex
#end
// Left Rotate operation
#macro LeftRotate(x_index)
#debug concat("LeftRotate: ", str(x_index, 0, 0), "\n")
#local y_index = TreeRights[x_index];
#if(!IsNil(y_index))
// Turn Y's left subtree into X's right subtree
#declare TreeRights[x_index] = TreeLefts[y_index];
#if(!IsNil(TreeLefts[y_index]))
#declare TreeParents[TreeLefts[y_index]] = x_index;
#end
// Link Y's parent to X's parent
#declare TreeParents[y_index] = TreeParents[x_index];
// Link X's parent to Y
#if(IsNil(TreeParents[x_index]))
// X was the root, make Y the new root
#declare RootIndex = y_index;
#else
#if(x_index = TreeLefts[TreeParents[x_index]])
#declare TreeLefts[TreeParents[x_index]] = y_index;
#else
#declare TreeRights[TreeParents[x_index]] = 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)
#debug concat("RightRotate: ", str(y_index, 0, 0), "\n")
#local x_index = TreeLefts[y_index];
#if(!IsNil(x_index))
// Turn X's right subtree into Y's left subtree
#declare TreeLefts[y_index] = TreeRights[x_index];
#if(!IsNil(TreeRights[x_index]))
#declare TreeParents[TreeRights[x_index]] = y_index;
#end
// Link X's parent to Y's parent
#declare TreeParents[x_index] = TreeParents[y_index];
// Link Y's parent to X
#if(IsNil(TreeParents[y_index]))
// Y was the root, make X the new root
#declare RootIndex = x_index;
#else
#if(y_index = TreeLefts[TreeParents[y_index]])
#declare TreeLefts[TreeParents[y_index]] = x_index;
#else
#declare TreeRights[TreeParents[y_index]] = 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)
#debug concat("RBInsertFixup: ", str(z_index, 0, 0), "\n")
// Continue fixing while Z's parent is RED
#while(!IsNil(TreeParents[z_index]) & TreeColors[TreeParents[z_index]] = 1)
#if(TreeParents[z_index] = TreeLefts[TreeParents[TreeParents[z_index]]])
// Parent is left child of grandparent
#local y_index = TreeRights[TreeParents[TreeParents[z_index]]]; //
Uncle
#if(TreeColors[y_index] = 1) // Uncle is RED
// Case 1: Recolor
#declare TreeColors[TreeParents[z_index]] = 0; // Parent to
BLACK
#declare TreeColors[y_index] = 0; // Uncle to BLACK
#declare TreeColors[TreeParents[TreeParents[z_index]]] = 1; //
Grandparent to RED
#local z_index = TreeParents[TreeParents[z_index]]; // Move up
to grandparent
#else
// Uncle is BLACK
#if(z_index = TreeRights[TreeParents[z_index]]) // Z is right
child
// Case 2: Z is right child - Convert to Case 3
#local z_index = TreeParents[z_index];
LeftRotate(z_index)
#end
// Case 3: Z is left child
#declare TreeColors[TreeParents[z_index]] = 0; // Parent to
BLACK
#declare TreeColors[TreeParents[TreeParents[z_index]]] = 1; //
Grandparent to RED
RightRotate(TreeParents[TreeParents[z_index]])
#end
#else
// Parent is right child of grandparent
#local y_index = TreeLefts[TreeParents[TreeParents[z_index]]]; //
Uncle
#if(TreeColors[y_index] = 1) // Uncle is RED
// Case 1: Recolor
#declare TreeColors[TreeParents[z_index]] = 0; // Parent to
BLACK
#declare TreeColors[y_index] = 0; // Uncle to BLACK
#declare TreeColors[TreeParents[TreeParents[z_index]]] = 1; //
Grandparent to RED
#local z_index = TreeParents[TreeParents[z_index]]; // Move up
to grandparent
#else
// Uncle is BLACK
#if(z_index = TreeLefts[TreeParents[z_index]]) // Z is left
child
// Case 2: Z is left child - Convert to Case 3
#local z_index = TreeParents[z_index];
RightRotate(z_index)
#end
// Case 3: Z is right child
#declare TreeColors[TreeParents[z_index]] = 0; // Parent to
BLACK
#declare TreeColors[TreeParents[TreeParents[z_index]]] = 1; //
Grandparent to RED
LeftRotate(TreeParents[TreeParents[z_index]])
#end
#end
#end
// Make sure root is BLACK
#declare TreeColors[RootIndex] = 0;
#end
// Insert a new key into the tree
#macro RBInsert(key)
#debug concat("RBInsert: ", str(key, 0, 0), "\n")
// Create a new node
#local z_index = TreeCount;
#declare TreeCount = TreeCount + 1;
// Initialize node with RED color
#declare TreeKeys[z_index] = key;
#declare TreeColors[z_index] = 1; // RED
#declare TreeLefts[z_index] = 0; // NIL
#declare TreeRights[z_index] = 0; // NIL
// Find insertion position
#local y_index = 0; // NIL
#local x_index = RootIndex;
#while(!IsNil(x_index))
#local y_index = x_index;
#if(key < TreeKeys[x_index])
#local x_index = TreeLefts[x_index];
#else
#local x_index = TreeRights[x_index];
#end
#end
// Insert the node
#declare TreeParents[z_index] = y_index;
#if(IsNil(y_index))
// Tree was empty
#declare RootIndex = z_index;
#else
#if(key < TreeKeys[y_index])
#declare TreeLefts[y_index] = z_index;
#else
#declare TreeRights[y_index] = z_index;
#end
#end
// Fix the red-black properties
RBInsertFixup(z_index)
#debug concat("Insert complete for key: ", str(key, 0, 0), "\n")
#end
// Search for a key in the tree
#macro RBSearch(key)
#debug concat("RBSearch: ", str(key, 0, 0), "\n")
#local found_index = -1;
#local x_index = RootIndex;
#while(!IsNil(x_index) & found_index = -1)
#if(key = TreeKeys[x_index])
#local found_index = x_index;
#elseif(key < TreeKeys[x_index])
#local x_index = TreeLefts[x_index];
#else
#local x_index = TreeRights[x_index];
#end
#end
#debug concat("Search result for key ", str(key, 0, 0), ": ",
str(found_index, 0, 0), "\n")
found_index
#end
// Print the tree structure for debugging
#macro PrintTree()
#debug "Tree structure:\n"
#debug concat("Root index: ", str(RootIndex, 0, 0), "\n")
#debug concat("Tree count: ", str(TreeCount, 0, 0), "\n")
#local i = 0;
#while(i < TreeCount)
#debug concat("Node ", str(i, 0, 0), ": ")
#debug concat("Key=", str(TreeKeys[i], 0, 0), ", ")
#debug concat("Color=", str(TreeColors[i], 0, 0), ", ")
#debug concat("Parent=", str(TreeParents[i], 0, 0), ", ")
#debug concat("Left=", str(TreeLefts[i], 0, 0), ", ")
#debug concat("Right=", str(TreeRights[i], 0, 0), "\n")
#local i = i + 1;
#end
#end
InitTree()
// Insert some values
#debug "1a\n"
RBInsert(10)
#debug "1b\n"
RBInsert(20)
#debug "1c\n"
RBInsert(30)
#debug "1d\n"
RBInsert(15)
#debug "1e\n"
RBInsert(25)
#debug "1f\n"
RBInsert(5)
#debug "1g\n"
RBInsert(35)
PrintTree()
---%<------%<------%<---
ingo
Post a reply to this message
|
|
