Run the file as is for some demo output.

ingo

---%<------%<------%<---
/*
POV-Ray include file: bst.inc

Author : Ingo Janssen
Date   : 2024-03-16
Version: 0.5

A POV-Ray include file for a Binary Seach Tree (BST)
*/

#version 3.7;

#declare _Sentinel = -999999;

// Enums for BST struct
#declare _bstNodeVal = 0;
#declare _bstLeft    = 1;
#declare _bstRight   = 2;
#declare _bstSize    = 3;

#macro BSTDebug(BST)
  #for(I, 0, dimension_size(BST[_bstNodeVal], 1) - 1)
    #debug concat("Value : ",str(BSTree[_bstNodeVal][I], 14, -1), ",  ")
    #debug concat("Left  : ",str(BSTree[_bstLeft][I], 7, 0), ",  ")
    #debug concat("Right : ",str(BSTree[_bstRight][I], 7, 0), "\n")
  #end
  #debug"\n"
#end

#macro BSTInit(MaxNodes)
  /*InitBST(MaxNodes)
  Creates a "struct" for a Binar Search Tree.

  Parameters:
    MaxNodes (int): maximum nuber of nodes the tree can contain.

  Result:
    Returns an array of arrays
    array{
      array[MaxNodes]; // Value array
      array[MaxNodes]; // Left pointer array
      array[MaxNodes]; // Right pointer arra
      array[1];        // BST size, is updated during inserts
    };

  */
  #local BST = array[4];
  #local BST[_bstNodeVal] = array[MaxNodes]; // Value array
  #local BST[_bstLeft]    = array[MaxNodes]; // Left pointer array
  #local BST[_bstRight]   = array[MaxNodes]; // Right pointer array
  #local BST[_bstSize]    = array[1];

  #local BST[_bstSize][0] = 0;
  #for(I, 0, MaxNodes-1)
    #local BST[_bstNodeVal][I] = _Sentinel;
    #local BST[_bstLeft][I]    = _Sentinel;
    #local BST[_bstRight][I]   = _Sentinel;
  #end
  BST
#end


#macro BSTInsert(BST, Value)
  /*: BSTInsert(BST, Value)
  Insert data in the BST.
  */
  //#debug concat("\nBSTsize: ",str(BST[_bstSize][0],0,0), "\n\n")
  #if(BST[_bstSize][0] < dimension_size(BST[_bstNodeVal], 1))
    #local Node = 0;
    #local NodeAdded = false;
    #while(NodeAdded = false)
      #if(BST[_bstNodeVal][Node] = _Sentinel)

        // Found an empty node, insert the value here
        #local BST[_bstNodeVal][Node] = Value;
        #local BST[_bstSize][0] = BST[_bstSize][0] + 1;
        #local NodeAdded = true;

      #else

        #if(Value < BST[_bstNodeVal][Node])
          #if(BST[_bstLeft][Node] = _Sentinel)
            // Found an empty left child, insert the value here
            #local BST[_bstLeft][Node] = BST[_bstSize][0];
            #local BST[_bstNodeVal][BST[_bstSize][0]] = Value;
            #local BST[_bstSize][0] = BST[_bstSize][0] + 1;
            #local NodeAdded = true;
          #else
            // Traverse the left subtree
            #local Node = BST[_bstLeft][Node];
          #end

        #else

           #if(Value > BST[_bstNodeVal][Node])
            #if(BST[_bstRight][Node] = _Sentinel)
              // Found an empty right child, insert the value here
              #local BST[_bstRight][Node] = BST[_bstSize][0];
              #local BST[_bstNodeVal][BST[_bstSize][0]] = Value;
              #local BST[_bstSize][0] = BST[_bstSize][0] + 1;
              #local NodeAdded = true;
            #else
              // Traverse the right subtree
              #local Node = BST[_bstRight][Node];
            #end
          #else
            // Value already exists in the tree, do nothing
            #local NodeAdded = true;
          #end
        #end

      #end
    #end
  #else
    #error "Binary search tree is full"
  #end
#end


#macro BSTSearch(BST, Value)
  /*: BSTSearch(BST, Value)
  Finds the index the given value is at.
  Returns -1 if the value is not found in the BST.
  */
  #local Node = 0;
  #while(Node != _Sentinel)
    #if(Value < BST[_bstNodeVal][Node])
      #local Node = BST[_bstLeft][Node];
    #else
      #if(Value > BST[_bstNodeVal][Node])
        #local Node = BST[_bstRight][Node];
      #else
        // Value found in the tree
        #break
      #end
    #end
  #end
  Node
#end


#macro BSTMinVal(BST, Node)
  /*: BSTMinVal(BST, Node)

  Returns the minimum value in the tree, starting from Node.
  */
  #while(BST[_bstLeft][Node] != _Sentinel)
    #local Node = BST[_bstLeft][Node];
  #end
  BST[_bstNodeVal][Node]
#end

#macro BSTMinIdx(BST, Node)
  /*: BSTMinIdx(BST, Node)

  Returns the index of the minimum value in the tree, starting from Node.
  */
  #while(BST[_bstLeft][Node] != _Sentinel)
    #local Node = BST[_bstLeft][Node];
  #end
  Node
#end


#macro BSTiot(BST, Node)
  /*: BSTiot(BST, Node)

  BST In Order Traversal : Left - Root - Right pattern traversal of the tree,
  starting from Node

  Returns an array with values.
  */
  #macro _BSTIOTraverse(BST, Node, Traversed, I)
    #if(Node != _Sentinel)
      // Visit the left subtree
      _BSTIOTraverse(BST, BST[_bstLeft][Node], Traversed, I)
      // Visit the current node
      //#debug concat("Node : ", str(Node,0,0)," Value :
",str(BST[_bstNodeVal][Node], 0, 0), "\n")
      #local Traversed[I] = BST[_bstNodeVal][Node];
      #local I = I + 1;
      // Visit the right subtree
      _BSTIOTraverse(BST, BST[_bstRight][Node], Traversed, I)
    #end
  #end
  #local I = 0;
  #local Traversed = array[dimension_size(BST[_bstNodeVal],1)];
  _BSTIOTraverse(BST, Node, Traversed, I)
  Traversed
#end


#macro BSTpre(BST, Node)
  /*: BSTpre(BST, Node)
  BST Pre Order Traversal: Root - Left - Right pattern traversal of the tree,
  starting from Node

  Returns an array with values.
  */
  #macro _BSTpreTraverse(BST, Node, Traversed, I)
    #if(Node != _Sentinel)
      //#debug concat("Node : ", str(Node,0,0)," Value :
",str(BST[_bstNodeVal][Node], 0, 0), "\n")
      #local Traversed[I] = BST[_bstNodeVal][Node];
      #local I = I + 1;
      _BSTpreTraverse(BST, BST[_bstLeft][Node] , Traversed, I)
      _BSTpreTraverse(BST, BST[_bstRight][Node], Traversed, I)
    #end
  #end
  #local I = 0;
  #local Traversed = array[dimension_size(BST[_bstNodeVal],1)];
  _BSTpreTraverse(BST, Node, Traversed, I)
  Traversed
#end


#macro BSTpro(BST, Node)
  /*: BSTpost(BST, Node)
  BST Post Order Traversal: Left - Right - Root patern traversal of the tree,
  starting from Node.

  Returns an array with values.
  */
  #macro _BSTpostTraverse(BST, Node, Traversed, I)
    #if(Node != _Sentinel)
      _BSTpostTraverse(BST, BST[_bstLeft][Node] , Traversed, I)
      _BSTpostTraverse(BST, BST[_bstRight][Node], Traversed, I)
      //#debug concat("Node : ", str(Node,0,0)," Value :
",str(BST[_bstNodeVal][Node], 0, 0), "\n")
    #end
  #end
  #local I = 0;
  #local Traversed = array[dimension_size(BST[_bstNodeVal],1)];
  _BSTpostTraverse(BST, Node, Traversed, I)
  Traversed
#end


#macro BSTDelete(BST, Value)
  /*: BSTDelete(BST, Value)

  Deletes the given value from the BST.
  */

  #local Root = 0;
  #local NodeToDelete = BSTSearch(BST, Value);

  #if (NodeToDelete != _Sentinel)
    // Node found, proceed with deletion
    #local ParentOfNodeToDelete = _Sentinel;

    // Find the parent of the node to be deleted
    #while (Root != NodeToDelete)
      #if (Value < BST[_bstNodeVal][Root])
        #local ParentOfNodeToDelete = Root;
        #local Root = BST[_bstLeft][Root];
      #else
        #local ParentOfNodeToDelete = Root;
        #local Root = BST[_bstRight][Root];
      #end
    #end

    // Handle the case of a leaf node
    #if (BST[_bstLeft][NodeToDelete] = _Sentinel & BST[_bstRight][NodeToDelete]
= _Sentinel)
      #if (ParentOfNodeToDelete = _Sentinel)
        // Node to be deleted is the root node
        #local BST[_bstNodeVal][0] = _Sentinel;
        #local BST[_bstLeft][0] = _Sentinel;
        #local BST[_bstRight][0] = _Sentinel;
      #else
        #if (BST[_bstNodeVal][ParentOfNodeToDelete] > Value)
          #local BST[_bstLeft][ParentOfNodeToDelete] = _Sentinel;
        #else
          #local BST[_bstRight][ParentOfNodeToDelete] = _Sentinel;
        #end
      #end
    #end

    // Handle the case of a node with one child
    #if (BST[_bstLeft][NodeToDelete] != _Sentinel & BST[_bstRight][NodeToDelete]
= _Sentinel)
      #if (ParentOfNodeToDelete = _Sentinel)
        // Node to be deleted is the root node
        #local BST[_bstNodeVal][0] =
BST[_bstNodeVal][BST[_bstLeft][NodeToDelete]];
        #local BST[_bstLeft][0] = BST[_bstLeft][BST[_bstLeft][NodeToDelete]];
        #local BST[_bstRight][0] = BST[_bstRight][BST[_bstLeft][NodeToDelete]];
      #else
        #if (BST[_bstNodeVal][ParentOfNodeToDelete] > Value)
          #local BST[_bstLeft][ParentOfNodeToDelete] =
BST[_bstLeft][NodeToDelete];
        #else
          #local BST[_bstRight][ParentOfNodeToDelete] =
BST[_bstLeft][NodeToDelete];
        #end
      #end
    #elseif (BST[_bstLeft][NodeToDelete] = _Sentinel &
BST[_bstRight][NodeToDelete] != _Sentinel)
      #if (ParentOfNodeToDelete = _Sentinel)
        // Node to be deleted is the root node
        #local BST[_bstNodeVal][0] =
BST[_bstNodeVal][BST[_bstRight][NodeToDelete]];
        #local BST[_bstLeft][0] = BST[_bstLeft][BST[_bstRight][NodeToDelete]];
        #local BST[_bstRight][0] = BST[_bstRight][BST[_bstRight][NodeToDelete]];
      #else
        #if (BST[_bstNodeVal][ParentOfNodeToDelete] > Value)
          #local BST[_bstLeft][ParentOfNodeToDelete] =
BST[_bstRight][NodeToDelete];
        #else
          #local BST[_bstRight][ParentOfNodeToDelete] =
BST[_bstRight][NodeToDelete];
        #end
      #end
    #end

    // Handle the case of a node with two children
    #if (BST[_bstLeft][NodeToDelete] != _Sentinel & BST[_bstRight][NodeToDelete]
!= _Sentinel)
      // Find the in-order successor (smallest value in the right subtree)
      #local InOrderSuccessor = BSTMinIdx(BST, BST[_bstRight][NodeToDelete]);

      // Copy the value of the in-order successor to the node to be deleted
      #local BST[_bstNodeVal][NodeToDelete] =
BST[_bstNodeVal][InOrderSuccessor];

      // Delete the in-order successor node
      BSTDelete(BST, BST[_bstNodeVal][InOrderSuccessor]);
    #end

    // Decrement the size of the BST
    #local BST[_bstSize][0] = BST[_bstSize][0] - 1;

  #else
    // Node not found, do nothing
  #end
#end



//=====

#if(input_file_name="bst.inc")

#declare MAX_NODES = 15; // Maximum number of nodes in the tree
                         // for demo sake a bigger array then used is defined
#declare BSTree = BSTInit(MAX_NODES);

#declare ValArr = array[13]{3.33,432,90,pi,6,8,-1,34,9,0,13,12,23};
#for(I, 0, dimension_size(ValArr,1) - 1)
  BSTInsert(BSTree, ValArr[I])
  #debug concat("I : ", str(I, 1, 1), "\n")
  BSTDebug(BSTree)
#end
#debug "\n"


#declare SearchVal = 90;
#declare IsNode = BSTSearch(BSTree, SearchVal);
#debug concat("Searched value ",str(SearchVal,7,-1) ," is at index ",
str(IsNode, 0, 0),"\n\n")


#debug concat("The MinVal is ", str(BSTMinVal(BSTree, 5),7,-1)," and is at index
", str(BSTMinIdx(BSTree, 5),0,0),"\n\n")


#declare InOrderVals = BSTiot(BSTree, 0);
#debug "BSTiot : "
#for(I, 0, dimension_size(InOrderVals,1) - 1)
  #if(defined(InOrderVals[I]))  // because one can define a bigger array than is
actually used.
    #debug concat(str(InOrderVals[I],7,-1), ", ")
  #end
#end
#debug "\n\n"


#declare PreOrderVals = BSTpre(BSTree, 0);
#debug "BSTpre : "
#for(I, 0, dimension_size(PreOrderVals,1) - 1)
  #if(defined(PreOrderVals[I]))
    #debug concat(str(PreOrderVals[I],7,-1), ", ")
  #end
#end
#debug "\n\n"


#declare PostOrderVals = BSTpre(BSTree, 0);
#debug "BSTpost: "
#for(I, 0, dimension_size(PostOrderVals,1) - 1)
  #if(defined(PostOrderVals[I]))
    #debug concat(str(PostOrderVals[I],7,-1), ", ")
  #end
#end
#debug "\n\n"


BSTDelete(BSTree, 12)
#declare InOrderVals = BSTiot(BSTree, 0);
#debug "BSTiot : "
#for(I, 0, dimension_size(InOrderVals,1) - 1)
  #if(defined(InOrderVals[I]))  // because one can define a bigger array than is
actually used.
    #debug concat(str(InOrderVals[I],7,-1), ", ")
  #end
#end
#debug "\n\n"

BSTDebug(BSTree)


#debug "\n"
#end // if inc..
---%<------%<------%<---

Post a reply to this message

There's a bug in it :( Will take some time to fix. After deletions valid data
can be over written.

"ingo" <nomail@nomail> wrote:
> Run the file as is for some demo output.
>
> ingo
>
> ---%<------%<------%<---
> /*
> POV-Ray include file: bst.inc
>

Post a reply to this message

"ingo" <nomail@nomail> wrote:

A completely new version. Options still to be added over time: a macro to
balance a tree, macro's to rotate parts of a tree to get proper Red Black trees.

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

/*
POV-Ray include file: bst.inc

A POV-Ray include file for a Binary Seach Tree (BST).

Author : Ingo Janssen
Date   : 2024-03-16
Version: 0.6
History: 2024-07-03 Complete update and breaking rewrite to fix numerous bugs.
         Changed the structure of the tree array to accommodate numbers,
         strings and vectors


The resulting BST is an array of nodes where each node is an array of array for
the nodes value and the node's children.

BinarySearchTree[N]{

    node[2]{values[1]{value}, children[2]{left, right}},
    ...
    node{{value},{left, right}},
    node{{value},{left, right}},
    ...
}

By overriding some declared values and macros the node value can be numbers,
strings or vectors. The indices are integers. Overriding values has to be done
before the include file is used. Mixing multiple trees of multiple types in a
scene will get messy, unless everything is nicely sequential.
To see the demos at the end of this file, run this bst.inc file as is.

*/

//cmd: -d -p  -f +wt0
#version 3.7;
#ifndef( BST_Inc_Temp)
#declare BST_Inc_Temp = version;


/*: _Sentinel & _ValSentinel

These are the default values in the arrays. One can override _ValSentinel in the
scene file.
For string values use: #declare _ValSentinel = "";
For vectors values use: #declare _ValSentinel = <-999999, -999999, -999999>;
When using strings or vectors, one also has to override IsEqual(), Comp() and
DebugNode() macros.
Mixing multiple trees of multiple types in a scene will get messy, unless
everyting is nicely sequential.

If _Sentinel collides with the scene data it can also be overriden, it has to be
an integer.
*/
#declare _Sentinel = -999999;
#declare _ValSentinel = -999999;


#macro IsEqualNum(A,B)
/*: IsEqualNum(A,B)

Checks whether numbers A and B are identical/equal.

Result: true or false
*/
  #local Return = false;
  #if(A = B)
    #local Return = true;
  #end
  Return
#end


#macro IsEqualStr(A,B)
/*: IsEqualSrr(A,B)

Checks whether strings A and B are identical/equal.

Result: true or false
*/
  #local Return = false;
  #if(A = B)
    #local Return = true;
  #end
  Return
#end

#macro IsEqualVec(A,B)
/*: IsEqualVec(A,B)

Checks whether vectors A and B are identical/equal.
This works for all vectors and colours are they are promoted to 5d.

Result: true or false
*/
  #local Return = false;
  #local vA = <0,0,0,0,0> + A;
  #local vB = <0,0,0,0,0> + B;
  #if(vA.x = vB.x & vA.y = vB.y & vA.z = vB.z & vA.filter = vB.filter & vA.t =
vB.t)
    #local Return = true;
  #end
  Return
#end


#macro IsEqual(A,B)
/*: IsEqual(A,B)

Checks whether vectors A and B are identical/equal.
The macro inside of IsEqual defines what 'types' are compared, the default is
numeric.
For a different comparison override the macro in your scene file and use
IsEqualVec,
isEqualStr inside it, or one of your own making.

Result: true or false
*/
  IsEqualNum(A,B)
#end


#macro NumComp(A, B)
/*: NumComp(A, B)
A macro to compare two numeric values.

When A<B the result = -1,
when equal: 0 and when
A>B the result is 1.
*/
  #local Return = 0;
  #if (A < B)
    #local Return = -1;
  #elseif(A > B)
    #local Return = 1;
  #end
  Return
#end


#macro StrComp(A, B)
/*: StrComp(A, B)
A macro to compare two strings.

When A<B the result = -1,
when equal: 0
and when A>B the result is 1.
*/
  #local Return = 0;
  #if (A < B)
    #local Return = -1;
  #elseif(A > B)
    #local Return = 1;
  #end
  Return
#end


#macro VecComp(A, B)
/*: VecLenComp(A, B)
A macro to compare the length of two vectors.

When the vector are identical: 0
When A=<B the result = -1,
and when A>B the result is 1.
*/
  #if(IsEqualVec(A,B))
    #local Return = 0;
  #else
    #local vA = vlength(<0,0,0> + A);
    #local vB = vlength(<0,0,0> + B);
    #if (vA <= vB)
      #local Return = -1;
    #elseif(vA > vB)
      #local Return = 1;
    #end
  #end
  Return
#end


#macro VecGrayComp(A, B)
/*: VecGrayComp(A, B)
A macro to compare the gray value of two colours.

When A<B the result = -1,
when equal: 0
and when A>B the result is 1.
*/
  #local gA = A.gray;
  #local gB = B.gray;
  #local Return = 0;
  #if (gA < gB)
    #local Return = -1;
  #elseif(gA > gB)
    #local Return = 1;
  #end
  Return
#end


#macro Comp(A, B)
/*: Comp(A,B)

A macro to compare two values.
When A<B the result = -1,
when equal: 0
and when A>B the result is 1.

The macro inside of Comp defines what 'types' are compared, the default is
numeric.
For a different comparison override the macro in your scene file and use
VecLenComp
inside it for example, or one of your own.
*/
  NumComp(A,B)
#end


// Node enum
#declare _nodeValues = 0;
#declare _nodeChildren = 1;

#declare _nodeVal = 0;

#declare _nodeLeft = 0;
#declare _nodeRight = 1;


#macro bstGetNode(BST, NodeIdx)
/*: bstGetNode(BST, NodeIdx)

Gets the node at the NodeIdx index from the BST search tree.
It returns a node array:

node = array[2]{
  array[1]{SomeValue},
  array[2]{IndexLeftSide, IndexRightChild}
};

*/
  BST[NodeIdx]
#end


/*: NodeVal(Node), NodeLeft(Node), NodeRight(Node)

These macros get the value, left child index (int) and right child index (int)
from
a node as extracted by bstGetNode(BST, NodeIdx). The _ValSentinel, or_Sentinel
value
will be returned if undefined.
*/
#macro NodeVal(Node)   Node[_nodeValues][_nodeVal] #end
#macro NodeLeft(Node)  Node[_nodeChildren][_nodeLeft] #end
#macro NodeRight(Node) Node[_nodeChildren][_nodeRight] #end


/*: bstNodeVal(Node), bstNodeLeft(Node), bstNodeRight(Node)

These macros get the value, left child index (int) and right child index (int)
from
a node in the BST search tree. The _ValSentinel, or_Sentinel value
will be returned if undefined
*/
#macro bstNodeVal(BST, NodeIdx)   BST[NodeIdx][_nodeValues][_nodeVal] #end
#macro bstNodeLeft(BST, NodeIdx)  BST[NodeIdx][_nodeChildren][_nodeLeft] #end
#macro bstNodeRight(BST, NodeIdx) BST[NodeIdx][_nodeChildren][_nodeRight] #end


/* for internal use to set data in the tree */
#macro _bstNodeSet(BST, NodeIdx, Node)      #local BST[NodeIdx] = Node; #end
#macro _bstNodeSetVal(BST, NodeIdx, Val)    #local
BST[NodeIdx][_nodeValues][_nodeVal] = Val; #end
#macro _bstNodeSetLeft(BST, NodeIdx, lIdx)  #local
BST[NodeIdx][_nodeChildren][_nodeLeft] = lIdx; #end
#macro _bstNodeSetRight(BST, NodeIdx, rIdx) #local
BST[NodeIdx][_nodeChildren][_nodeRight] = rIdx; #end


/*:  _nodeDefined(Node), _nodeDefinedVal(Node), _nodeDefinedLeft(Node),
_nodeDefinedRight(Node)

These macro's check whether the node or its parts are defined. They return
'true' or 'false'.

Use:
#local IsNode = DefineNode(bstGetNode(BST, NodeIdx))
or
#local NodeHasValue = DefinedNodeVal(YourBST[NodeIdx])
*/
#macro _nodeDefined(Node)
  #local Return = true;
  #if(//Node[_nodeValues][_nodeVal] = _ValSentinel &
      IsEqual(Node[_nodeValues][_nodeVal], _ValSentinel) &
      Node[_nodeChildren][_nodeLeft] = _Sentinel &
      Node[_nodeChildren][_nodeRight] = _Sentinel
  )
    #local Return = false;
  #end
  Return
#end


#macro _nodeDefinedVal(Node)
  #local Return = true;
  #if (IsEqual(Node[_nodeValues][_nodeVal], _ValSentinel) )
    #local Return = false;
  #end
  Return
#end


#macro _nodeDefinedLeft(Node)
  #local Return = true;
  #if (Node[_nodeChildren][_nodeLeft] = _Sentinel )
    #local Return = false;
  #end
  Return
#end


#macro _nodeDefinedRight(Node)
  #local Return = true;
  #if (Node[_nodeChildren][_nodeRight] = _Sentinel )
    #local Return = false;
  #end
  Return
#end


#macro NodeInit()
/*: NodeInit()

Initializes an 'empty' node with sentinels.
*/
  array[2]{
    array[1]{_ValSentinel},
    array[2]{_Sentinel, _Sentinel}
  }
#end


#macro BSTinit(MaxNodes)
/*: BSTinit(MaxNodes)

Creates an array for a Binary Search Tree.

Parameters:
  MaxNodes (int): maximum number of nodes the tree can contain.

Result:
  Returns an array of node arrays
  array[MaxNodes]{node, node, ...};

  array{array{array{value}, array{indices}}}

*/
  #local BST = array[MaxNodes];
  #for(NodeIdx, 0, MaxNodes-1)
    _bstNodeSet(BST, NodeIdx, NodeInit())
  #end
  BST
#end


/*: NodeDebugNum(Node), NodeDebugStr(Node),
   NodeDebugVec2(Node), NodeDebugVec3(Node)

Helper macros for formatting the output of various types of nodes
to the debugging stream. They can be used directly or are used through the
NodeDebug() or BSTDebug() macro.
*/
#macro NodeDebugNum(Node)
  #debug concat("[Value : ", str(NodeVal(Node), 14, -1))
  #debug ",  "
  #debug concat("Left : ", str(NodeLeft(Node), 7, 0))
  #debug ",  "
  #debug concat("Right : ", str(NodeRight(Node), 7, 0))
  #debug "]"
#end

#macro NodeDebugStr(Node)
  #debug concat("[Value : ", NodeVal(Node))
  #debug ",  "
  #debug concat("Left : ", str(NodeLeft(Node), 7, 0))
  #debug ",  "
  #debug concat("Right : ", str(NodeRight(Node), 7, 0))
  #debug "]"
#end

#macro NodeDebugVec2(Node)
  #debug concat("[Value : <", vstr(2,NodeVal(Node),", ", 14, -1))
  #debug ">,  "
  #debug concat("Left : ", str(NodeLeft(Node), 7, 0))
  #debug ",  "
  #debug concat("Right : ", str(NodeRight(Node), 7, 0))
  #debug "]"
#end

#macro NodeDebugVec3(Node)
  #debug concat("[Value : <", vstr(3,NodeVal(Node),", ", 14, -1))
  #debug ">,  "
  #debug concat("Left : ", str(NodeLeft(Node), 7, 0))
  #debug ",  "
  #debug concat("Right : ", str(NodeRight(Node), 7, 0))
  #debug "]"
#end


#macro NodeDebug(Node)
/*: NodeDebug(Node)

writes the nodes content to the debug stream.
By default it writes numerical nodes. For string or vector
nodes override NodeDbug in the scenefile. For example:
#macro NodeDebug(Node)
  NodeDebugVec3(Node)
#end

*/
  NodeDebugNum(Node)
#end


#macro BSTDebug(BST)
/*: BSTDebug(BST)

Writes the content of the BST to the debug stream. It depends on NodeDebug for
proper formatting.
*/
  #for(I, 0, dimension_size(BST, 1) - 1)
    #local Node = bstGetNode(BST, I);
    NodeDebug(Node)
    #debug concat("  NodeIdx : ", str(I, 3, 0), "\n")
  #end
  #debug"\n"
#end


#macro SearchEmptyNode(BST)
/*: SearchEmptyNode(BST)

Searches through the array of nodes for the first 'free' position to put a node.

output (int): a node index or the _Sentinel if the tree is full.
*/

  #local EmptyNode = false;
  #local NI = 0;
  #while (EmptyNode = false & NI < dimension_size(BST,1))
    #local Node = BST[NI];
    #local EmptyNode = !_nodeDefined(Node);
    #local NI = NI + 1;
  #end
  #if (EmptyNode = false)
    #local NI = _Sentinel;
  #end
  NI - 1
#end


#macro BSTheight(BST, NodeIdx)
/*: BSTheight(BST, NodeIdx)

Returns the height, the number of vertices from the root to the deepest node,
of the tree starting from the node NodeIdx.
*/
  #if(NodeIdx = _Sentinel)
    #local Return = -1;
  #else
    #local LeftHeight  = BSTheight(BST, bstNodeLeft(BST, NodeIdx));
    #local RightHeight = BSTheight(BST, bstNodeRight(BST, NodeIdx));
    #if(LeftHeight > RightHeight)
      #local Return = LeftHeight + 1;
    #else
      #local Return = RightHeight +1;
    #end
  #end
  Return
#end


#macro BSTinsert(BST, Value)
/*: BSTInsert(BST, Value)

Insert data in a free node in the BST and sets the 'pointer' (child index) to
itself in its parent.
*/
//#debug concat("Insert value: ", str(Value,0,0),"\n")
  #local FreeNode = SearchEmptyNode(BST);
  #if(FreeNode != _Sentinel)
    #local NodeIdx = 0;
    #local NodeAdded = false;
    #while(NodeAdded = false)
      //#debug concat("NodeIdx : ",str(NodeIdx,0,0),"\n")
      #if(!_nodeDefinedVal(BST[NodeIdx]))
        #local Case = 2;
      #else
      #local Case = Comp(Value, bstNodeVal(BST, NodeIdx));
      #end
      #switch(Case)
        #case(-1)

          #if(!_nodeDefinedLeft(BST[NodeIdx]))
            // Found an empty left child, insert the value here
            _bstNodeSetLeft(BST, NodeIdx, FreeNode)
            _bstNodeSetVal(BST, FreeNode, Value)
            #local NodeAdded = true;
          #else
            // Traverse the left subtree
            #local NodeIdx = bstNodeLeft(BST, NodeIdx);
          #end
        #break
        #case(0)
          // Value already exists in the tree, do nothing
          #local NodeAdded = true;
        #break
        #case(1)
          #if(!_nodeDefinedRight(BST[NodeIdx]))
            // Found an empty right child, insert the value here
            _bstNodeSetRight(BST, NodeIdx, FreeNode)
            _bstNodeSetVal(BST, FreeNode, Value)
            #local NodeAdded = true;
          #else
            // Traverse the right subtree
            #local NodeIdx = bstNodeRight(BST, NodeIdx);
          #end
        #break
        #case(2)
          // Found an empty node, insert the value here
          _bstNodeSetVal(BST, NodeIdx, Value)
          #local NodeAdded = true;
        #break
      #end
    #end
  #else
    #error "Binary search tree is full"
  #end
  //#debug "\n"
#end


#macro BSTsearch(BST, Value)
/*: BSTSearch(BST, Value)

Finds the index the given value is at.
Returns _Sentinel if the value is not found in the BST.
*/
  #local NodeIdx = 0;
  #local NotFound = true;
  #while(NotFound)
    #if (NodeIdx = _Sentinel)
      #local Case = _Sentinel;
    #else
      #local Case = Comp(Value, bstNodeVal(BST, NodeIdx));
    #end
    #switch(Case)
      #case(_Sentinel) #local NotFound = false; #break
      #case(-1) #local NodeIdx = bstNodeLeft(BST, NodeIdx); #break
      #case( 0) #local NotFound = false; #break
      #case( 1) #local NodeIdx = bstNodeRight(BST, NodeIdx);#break
    #end
  #end
  NodeIdx
#end


#macro BSTgetParent(BST, NodeIdx)
/*: BSTGetParent(BST, Node)

Returns the parent node index of the node NodeIdx.
//? would it make sense to extend the node arry to 4 and add the parent to it?
// saves a macro
*/
  #local Root = 0;
  #local Parent = Root;
  #local NotFound = true;
  #while (NotFound)
    #if (Root = _Sentinel)
      #local Case = _Sentinel;
    #else
      #local Case = Comp(bstNodeVal(BST, NodeIdx), bstNodeVal(BST, Root));
    #end
    #switch(Case)
      #case(_Sentinel)
        #local Parent = _Sentinel;
        #local NotFound = false;
      #break
      #case(-1)
        #local Parent = Root;
        #local Root = bstNodeLeft(BST, Root);
      #break
      #case(0)
        #local NotFound = false;
      #break
      #case(1)
        #local Parent = Root;
        #local Root = bstNodeRight(BST, Root);
      #break
    #end
  #end
  #if (Parent = NodeIdx)
    // NodeIdx can't be it's own parent, NodeIdx 0
    #local Parent = _Sentinel;
  #end
  Parent
#end


#macro BSTminVal(BST, NodeIdx)
/*: BSTMinVal(BST, Node)

Returns the minimum value in the tree, starting from Node.
*/
  #local NI = NodeIdx;
  #while(bstNodeLeft(BST, NI) != _Sentinel) //that does not work with only one
node and a larger array
    #local NI = bstNodeLeft(BST, NI);
  #end
  bstNodeVal(BST, NI)
#end


#macro BSTminIdx(BST, NodeIdx)
/*: BSTMinIdx(BST, Node)

Returns the index of the minimum value in the tree, starting from Node.
*/
  #local NI = NodeIdx;
  #while(bstNodeLeft(BST, NI) != _Sentinel)
    #local NI = bstNodeLeft(BST, NI);
  #end
  NI
#end


/*:
Regarding tree traversel in BST's, found this somewhere on the web.

Pre-order:
  Used to create a copy of a tree. For example, if you want to create a
  replica of a tree, put the nodes in an array with a pre-order traversal. Then
  perform an Insert operation on a new tree for each value in the array. You
  will end up with a copy of your original tree.

In-order:
  Used to get the values of the nodes in increasing order.

Post-order:
  Used to delete a tree from leaf to root.
*/

#macro BSTiot(BST, NodeIdx)
/*: BSTiot(BST, NodeIdx)

BST In Order Traversal : Left - Root - Right pattern traversal of the tree

Result: an array with the values in order
*/
  #macro _BSTIOTraverse(BST, NodeIdx, Traversed, I)
    #if(NodeIdx != _Sentinel)
      // Visit the left subtree
      _BSTIOTraverse(BST, bstNodeLeft(BST, NodeIdx), Traversed, I)
      // Visit the current node
      #local Traversed[I] = bstNodeVal(BST, NodeIdx);
      #local I = I + 1;
      // Visit the right subtree
      _BSTIOTraverse(BST, bstNodeRight(BST, NodeIdx), Traversed, I)
    #end
  #end
  #local I = 0;
  #local Traversed = array[dimension_size(BST,1)];
  _BSTIOTraverse(BST, NodeIdx, Traversed, I)
  Traversed
#end


#macro BSTpre(BST, NodeIdx)
/*: BSTpre(BST, Node)

BST Pre Order Traversal: Root - Left - Right pattern traversal of the tree

Result: an array with values in 'pre order'.
*/
  #macro _BSTPRETraverse(BST, NodeIdx, Traversed, I)
    #if(NodeIdx != _Sentinel)
      #local Traversed[I] = bstNodeVal(BST, NodeIdx);
      #local I = I + 1;
      _BSTPRETraverse(BST, bstNodeLeft(BST, NodeIdx) , Traversed, I)
      _BSTPRETraverse(BST, bstNodeRight(BST, NodeIdx), Traversed, I)
    #end
  #end
  #local I = 0;
  #local Traversed = array[dimension_size(BST,1)];
  _BSTPRETraverse(BST, NodeIdx, Traversed, I)
  Traversed
#end


#macro BSTpost(BST, NodeIdx)
/*: BSTpost(BST, Node)

BST Post Order Traversal: Left - Right - Root patern traversal of the tree

Result: an array with the values in 'post order'.
*/
  #macro _BSTPOSTTraverse(BST, NodeIdx, Traversed, I)
    #if(NodeIdx != _Sentinel)
      _BSTPOSTTraverse(BST, bstNodeLeft(BST, NodeIdx) , Traversed, I)
      _BSTPOSTTraverse(BST, bstNodeRight(BST, NodeIdx), Traversed, I)
      #local Traversed[I] = bstNodeVal(BST, NodeIdx);
      #local I = I + 1;
    #end
  #end
  #local I = 0;
  #local Traversed = array[dimension_size(BST,1)];
  _BSTPOSTTraverse(BST, NodeIdx, Traversed, I)
  Traversed
#end



#macro BSTdelete(BST, Value)
  /*: BSTDelete(BST, Value)

  Deletes the given value from the BST.

  */
  #local NodeIdxToDelete = BSTsearch(BST, Value);
  #if (NodeIdxToDelete != _Sentinel)
    #local ParentIdxOfNodeToDelete = BSTgetParent(BST, NodeIdxToDelete);
    #local ToLeft = Comp(bstNodeVal(BST, ParentIdxOfNodeToDelete), Value);
    #local ToLeft = Comp(bstNodeVal(BST, ParentIdxOfNodeToDelete), Value);
    // Handle the case of a leaf node
    #if (bstNodeLeft(BST, NodeIdxToDelete) = _Sentinel & bstNodeRight(BST,
NodeIdxToDelete) = _Sentinel)
      #if (ParentIdxOfNodeToDelete = _Sentinel)
        // Node to be deleted is the root node
        _bstNodeSet(BST, NodeIdxToDelete, NodeInit())
      #else
        #if(ToLeft = 1)
          _bstNodeSetLeft(BST, ParentIdxOfNodeToDelete, _Sentinel)
        #else
          _bstNodeSetRight(BST, ParentIdxOfNodeToDelete, _Sentinel)
        #end
      _bstNodeSet(BST, NodeIdxToDelete, NodeInit())
      #end
    #end

    // Handle the case of a node with one child
    #if (bstNodeLeft(BST, NodeIdxToDelete) != _Sentinel & bstNodeRight(BST,
NodeIdxToDelete) = _Sentinel)
      #if (ParentIdxOfNodeToDelete = _Sentinel)
        // Node to be deleted is the root node
        _bstNodeSetVal(BST, NodeIdxToDelete, bstNodeVal(BST, bstNodeLeft(BST,
NodeIdxToDelete)))
        _bstNodeSetLeft(BST, NodeIdxToDelete, bstNodeLeft(BST, bstNodeLeft(BST,
NodeIdxToDelete)))
        _bstNodeSetRight(BST, NodeIdxToDelete, bstNodeRight(BST,
bstNodeLeft(BST, NodeIdxToDelete)))
      #else
        #if (ToLeft = 1)
          _bstNodeSetLeft(BST, ParentIdxOfNodeToDelete, bstNodeLeft(BST,
NodeIdxToDelete))
        #else
          _bstNodeSetRight(BST, ParentIdxOfNodeToDelete, bstNodeLeft(BST,
NodeIdxToDelete))
        #end
      #end
      _bstNodeSet(BST, NodeIdxToDelete, NodeInit())
    #elseif (bstNodeLeft(BST, NodeIdxToDelete) = _Sentinel & bstNodeRight(BST,
NodeIdxToDelete) != _Sentinel)
      #if (ParentIdxOfNodeToDelete = _Sentinel)
        // Node to be deleted is the root node
        _bstNodeSetVal(BST, NodeIdxToDelete, bstNodeVal(BST, bstNodeRight(BST,
NodeIdxToDelete)))
        _bstNodeSetLeft(BST, NodeIdxToDelete, bstNodeLeft(BST, bstNodeRight(BST,
NodeIdxToDelete)))
        _bstNodeSetRight(BST, NodeIdxToDelete, bstNodeRight(BST,
bstNodeRight(BST, NodeIdxToDelete)))
      #else
        #if (ToLeft = 1)
          _bstNodeSetLeft(BST, ParentIdxOfNodeToDelete, bstNodeRight(BST,
NodeIdxToDelete))
        #else
          _bstNodeSetRight(BST, ParentIdxOfNodeToDelete, bstNodeRight(BST,
NodeIdxToDelete))
        #end
      #end
      _bstNodeSet(BST, NodeIdxToDelete, NodeInit())
    #end

    // Handle the case of a node with two children
    #if (bstNodeLeft(BST, NodeIdxToDelete) != _Sentinel & bstNodeRight(BST,
NodeIdxToDelete) != _Sentinel)
      // Find the in-order successor (smallest value in the right subtree)
      #local InOrderSuccessor = BSTminIdx(BST, bstNodeRight(BST,
NodeIdxToDelete));
      //#debug concat("InOrderSuccessor : ", str(InOrderSuccessor,0,0),"\n")
      // Copy the value of the in-order successor
      #local IOSval = bstNodeVal(BST, InOrderSuccessor);
      // Recursive delete the in-order successor node
      BSTdelete(BST, bstNodeVal(BST, InOrderSuccessor))
      // Paste the value of the in-order successor to "the node to be deleted"
      _bstNodeSetVal(BST, NodeIdxToDelete, IOSval)
    #end

  #else
    // Node not found, do nothing
  #end
#end


//=== Demo & Tests
//
//


#if(input_file_name="bst.inc")

#declare ValArr = array[13]{3,99,90,6,5,8,-1,34,9,0,13,12,23};

#debug "The data that'll be used for creating the Binary Seach Tree:\n{"
#for(I,0,dimension_size(ValArr,1)-1)
  #debug concat(str(ValArr[I],0,0),", ")
#end
#debug "}\n\n"

#declare BSTree = BSTinit(15); // the tree is bigger than the data amount, it
can be the sam though.
#debug "The content of the tree after initialization:\n"
BSTDebug(BSTree)

#for(I,0,dimension_size(ValArr,1)-1)
  BSTinsert(BSTree, ValArr[I])
  //#debug concat("I : ", str(I, 1, 1), " Value : ", str(ValArr[I],0,0),"\n")
  //BSTDebug(BSTree)
#end

#debug "The content of the tree after filling it with data:\n"
BSTDebug(BSTree)


#local SearchVal = 3;
#local FoundIdx = BSTsearch(BSTree, SearchVal);
#debug concat("Searched for Value  : "str(SearchVal,0,0), " found at Idx : ",
str(FoundIdx,0,0), "\n\n")

#local NodeIndex = FoundIdx;
#debug concat("The MinVal : ", str(BSTminVal(BSTree, NodeIndex),0,0), " found at
Idx : ", str(BSTminIdx(BSTree, NodeIndex),0,0), " starting from nodeIDx : ",
str(NodeIndex,0,0),"\n\n")

#local Node = FoundIdx;
#debug concat("Parent of NodeIdx : ", str(Node,0,0), " is NodeIdx :
",str(BSTgetParent(BSTree, Node),0,0),"\n\n")

#debug concat("Tree height : ", str(BSTheight(BSTree, 0),0,0),"\n\n")

#debug "Three ways to travers the BST:\n"
#declare InOrderVals = BSTiot(BSTree, 0);
#debug "BSTiot : "
#for(I, 0, dimension_size(InOrderVals,1) - 1)
  #if(defined(InOrderVals[I]))  // because one can define a bigger array than is
actually used.
    #debug concat(str(InOrderVals[I],7,-1), ", ")
  #end
#end
#debug "\n"


#declare PreOrderVals = BSTpre(BSTree, 0);
#debug "BSTpre :  "
#for(I, 0, dimension_size(PreOrderVals,1) - 1)
  #if(defined(PreOrderVals[I]))
    #debug concat(str(PreOrderVals[I],7,-1), ", ")
  #end
#end
#debug "\n"


#declare PostOrderVals = BSTpost(BSTree, 0);
#debug "BSTpost:  "
#for(I, 0, dimension_size(PostOrderVals,1) - 1)
  #if(defined(PostOrderVals[I]))
    #debug concat(str(PostOrderVals[I],7,-1), ", ")
  #end
#end
#debug "\n\n"


#declare DelVal = 6;
#debug concat("Value to delete : ",str(DelVal,0,0),"\n")
BSTdelete(BSTree, DelVal)
#debug concat("The BST after deletion of the value: ", str(DelVal,0,0),"\n")
BSTDebug(BSTree)

#declare InsVal = 3.3333;
#debug concat("Value to insert : ",str(InsVal,0,3),"\n")
BSTinsert(BSTree, InsVal)
#debug concat("The BST after insertion of the value: ", str(InsVal,0,3),"\n")
BSTDebug(BSTree)

#declare InOrderVals = BSTiot(BSTree, 0);
#debug "BSTiot after deletion and insertion of a value : \n"
#for(I, 0, dimension_size(InOrderVals,1) - 1)
  #if(defined(InOrderVals[I]))  // because one can define a bigger array than is
actually used.
    #debug concat(str(InOrderVals[I],7,-1), ", ")
  #end
#end
#debug "\n\n"




/*
To redefine for string nodes the following variables
and macro's have to be overwritten
*/
#declare _ValSentinel = "";

#macro IsEqual(A,B)
  IsEqualStr(A,B)
#end

#macro Comp(A, B)
  StrComp(A,B)
#end

#macro NodeDebug(Node)
  NodeDebugStr(Node)
#end

#declare ValArr = array[5]{"A","AAA","AA","B","BB"};
#debug "The data that'll be used for creating the string Binary Seach Tree:\n{"
#for(I,0,dimension_size(ValArr,1)-1)
  #debug concat(ValArr[I],", ")
#end
#debug "}\n\n"

#declare BSTree = BSTinit(5);

#for(I,0,dimension_size(ValArr,1)-1)
  BSTinsert(BSTree, ValArr[I])
  //#debug concat("I : ", str(I, 1, 1), " Value : ", str(ValArr[I],0,0),"\n")
  //BSTDebug(BSTree)
#end

#debug "the BST after insertion of the string nodes:\n"
BSTDebug(BSTree)




//The same excercise for creating BST with vector nodes


#declare _ValSentinel = <-999999,-999999,-999999>;

#macro IsEqual(A,B)
  IsEqualVec(A,B)
#end

#macro Comp(A, B)
  VecComp(A,B)
#end

#macro NodeDebug(Node)
  NodeDebugVec3(Node)
#end

#declare ValArr = array[5]{<1,1,1>,<1,2,3>,<3,3,3>,<2,3,1>,<9,7,3>};
#declare BSTree = BSTinit(5);

#for(I,0,dimension_size(ValArr,1)-1)
  BSTinsert(BSTree, ValArr[I])
  //#debug concat("I : ", str(I, 1, 1), " Value : ", str(ValArr[I],0,0),"\n")
  //BSTDebug(BSTree)
#end
BSTDebug(BSTree)

#declare InOrderVals = BSTiot(BSTree, 0);
#debug "BSTiot : "
#for(I, 0, dimension_size(InOrderVals,1) - 1)
  #if(defined(InOrderVals[I]))  // because one can define a bigger array than is
actually used.
    #debug concat("<",vstr(3,InOrderVals[I],", ",7,-1), ">, ")
  #end
#end
#debug "\n"


#declare PreOrderVals = BSTpre(BSTree, 0);
#debug "BSTpre : "
#for(I, 0, dimension_size(PreOrderVals,1) - 1)
  #if(defined(PreOrderVals[I]))
    #debug concat("<",vstr(3,PreOrderVals[I],", "7,-1), ">, ")
  #end
#end
#debug "\n"


#declare PostOrderVals = BSTpost(BSTree, 0);
#debug "BSTpost : "
#for(I, 0, dimension_size(PostOrderVals,1) - 1)
  #if(defined(PostOrderVals[I]))
    #debug concat("<",vstr(3, PostOrderVals[I],", ",7,-1), ">, ")
  #end
#end
#debug "\n"


#declare DelVal = <1,2,3>;
#debug concat("Value to delete : <",vstr(3,DelVal,", ", 0,0),">\n")
BSTdelete(BSTree, DelVal)
BSTDebug(BSTree)

#end //demo section

#version BST_Inc_Temp;
#end

Post a reply to this message

"ingo" <nomail@nomail> wrote:
> "ingo" <nomail@nomail> wrote:
>
> A completely new version. Options still to be added over time: a macro to
> balance a tree, macro's to rotate parts of a tree to get proper Red Black trees.
>
> ---%<------%<------%<---

cool.  had a v similar project on the go, and "faltered" when it came to RB tree
deletion of nodes; could not get the parser "to agree" on the code variations I
tried :-).  bon chance.


regards, jr.

Post a reply to this message

"jr" <cre### [at] gmailcom> wrote:

Thanks.

I already had quite some problems with deleting a node in this one.

When deleting I first followed some Python et al. examples, but these high level
and OOP languages obfuscate what really has to be done. Copy data to a node and
then search won't work as you have the same value twice. So copy, delete, paste.
That took some time to figure out where it went wrong.

One thing that didn't work was keeping count of the amount of entries,
especially after deleting a value. So now I just search for an empty one when
inserting.

It is and will stay a slow moving project,

ingo


> cool.  had a v similar project on the go, and "faltered" when it came to RB tree
> deletion of nodes; could not get the parser "to agree" on the code variations I
> tried :-).  bon chance.
>
>
> regards, jr.

Post a reply to this message

hi,

"ingo" <nomail@nomail> wrote:
> ...
> When deleting I first followed some Python et al. examples, but these high level
> and OOP languages obfuscate what really has to be done. ...

Bald Eagle pointed me to this very good (imo) resource:
<http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap14.htm>


regards, jr.

Post a reply to this message

"jr" <cre### [at] gmailcom> wrote:

Thanks, added it to the collection.

> Bald Eagle pointed me to this very good (imo) resource:
> <http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap14.htm>

Post a reply to this message