Saturday, February 04, 2006

Adaptive Binary Tree

Here's the node nice and simple if we wanted to generalize it instead of a string we could have an array of T.

    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;

        }

 

    }

Post a Comment