static typeNode* SplitBranch(typeNode* parent,unsigned long index)
{
typeNode* working;
char* data;
unsigned long I;
if ((index < 1) || (index >= parent->Length))
return 0;
working = CreateBranch(0,parent->Data + index,parent->Length - index);
if (working == 0)
return 0;
working->Child = parent->Child;
parent->Child = working;
data = (char*)malloc(index);
if (data == 0)
return 0;
for (I = 0;I < index;I++)
data[I] = parent->Data[I];
free(parent->Data);
parent->Length = index;
parent->Data = data;
return working;
}
static typeNode* SplitBranch(typeNode* parent,unsigned long index)
{
typeNode* node1;
typeNode* node2;
char* data;
unsigned long I;
if ((index < 1) || (index >= parent->Length))
return 0;
node1 = CreateBranch(0,parent->Data,index);
if (node1 == 0)
return 0;
node2 = CreateBranch(0,parent->Data + index,parent->Length - index);
if (node2 == 0)
return 0;
free(parent->Data);
parent->Length = node1->Length;
parent->Data = node1->Data;
free(node1)
node2->Child = parent->Child;
parent->Child = node2;
return working;
}
node1 = CreateBranch(0,parent->Data,index);
if (node1 == 0)
return 0;
node2 = CreateBranch(0,parent->Data + index,parent->Length - index);
if (node2 == 0)
return 0;
free(parent->Data);
parent->Length = node1->Length;
parent->Data = node1->Data;
free(node1)
node2->Child = parent->Child;
parent->Child = node2;
The next two line do something a bit complicated and not really obvious. The nodes inside a trie form strings with their children. The parent is the first part of the string, and each child is part of a separate string. When we split a node, we still need to have a single string. This is why all the children that the split node had before must be moved to the new node we have created, because the parent node and the new node are a single prefix for all the nodes that the parent had before. This means that after the split, nothing has changed. The next to last line in the code above gives all the children of the parent to the new node, and the last line sets the new node as the parent's only child. Later, after the split, the parent will receive new children, that is why we need to split the node.
This is not quite clear yet, but I will try to make a visual explanation later.
