public class Node
{
public char Letter;
public int Count;
public Node Yes = null;
public Node No = null;
public Node(char c)
{
Letter = c;
Count = 1;
}
}
Here's the tree. Everything should work fine.
public class AdaptiveBinaryTree
{
protected Node root = null;
public override string ToString()
{
return root.ToString();
}
/// <summary>
/// Recursively build and sort tree.
/// </summary>
/// <param name="s"></param>
/// <param name="i"></param>
/// <param name="n"></param>
/// <returns></returns>
protected Node InsertData(string s, int i, Node n)
{
if (s.Length == i)
return n;
if (n == null)
{
n = new Node(s[i]);
i++;
n.Yes = InsertData(s, i, n.Yes);
}
else if (n.Letter == s[i])
{
n.Count++;
i++;
n.Yes = InsertData(s, i, n.Yes);
n.Yes = SwitchNodes(n.Yes, n); //Yes should checks it's no child
n.No = SwitchNodes(n.No, n); // no should check it's no child
}
else
{
n.No = InsertData(s, i, n.No);
}
return n;
}
// Node count has just been increased do we need to switch?
private Node SwitchNodes(Node n, Node nParent)
{
//
// Have a or b
//
// a.) p b.) p
// \ /
// n n
// / /
// n.No n.No
if (n == null) return n;
if (n.No == null) return n;
if (n.Count >= n.No.Count) return n;
return SwapWithNoChild(n, nParent);
}
public void Add(string s)
{
root = InsertData(s, 0, root/*, null*/);
}
protected Node SwapWithNoChild(Node n, Node nParent)
{
if (n.No == null) return n;
Node child = n.No;
n.No = child.No;
child.No = n;
if(nParent == null)
return n;
if (nParent.Yes == n)
{
nParent.Yes = child;
}
else
{
nParent.No = child;
}
return child;
}
}
No comments:
Post a Comment