C# Simple Binary Tree

-
Today I'm getting a bit into data structures. Recently I've found a need to store a large amount of records (16 million) in memory as a sort of cache. I tried using databases, etc, but it was all too slow. I needed super fast access times, well under a millisecond to speed up a large application with many data look ups. I tried a linked list but while the insert times were great the look ups again were too slow. I finally settled on a binary tree. Building the tree is slow, several minutes, but this data doesn't change and gives me super fast look up times, around .005 ms. To achieve this I wrote a very simple binary tree class.

It uses a node that is fit for my purposes. To make this class even better I would implement in generics with a node class that has to implement IComparable. This way you can make a binary tree for any type of class that can be compared. For now I'm hard coding the key/values for my specific needs. See the rather large code block below. I will add a zip file with the code as well.

using System;
using System.Collections;

namespace BinaryTree
{
   
    /// <summary>
    /// A very basic Binary Search Tree. Not generalized, stores
    /// name/value pairs in the tree nodes. name is the node key.
    /// The advantage of a binary tree is its fast insert and lookup
    /// characteristics. This version does not deal with tree balancing.
    /// </summary>
    public class TreeNode
    {
        #region Fields

        private string _name;
        
        private int[] _codes;
        
        public TreeNode Left, Right;

        #endregion

        #region Properties

        /// <summary>
        /// Gets or sets the name.
        /// </summary>
        /// <value>
        /// The name.
        /// </value>
        public string Name
        {
            get { return _name; }
            set { _name = value; }
        }

        /// <summary>
        /// Gets or sets the codes.
        /// </summary>
        /// <value>
        /// The codes.
        /// </value>
        public int[] Codes
        {
            get { return _codes; }
            set { _codes = value; }
        }
        
        #endregion

        /// <summary>
        /// Initializes a new instance of the <see cref="TreeNode"/> class.
        /// </summary>
        /// <param name="name">The name.</param>
        /// <param name="_codes">The _codes.</param>
        public TreeNode( string name, int[] codes )
        {
            _name = name;
            _codes = codes;
            Left = null;
            Right = null;
        }
    }

    /// <summary>
    /// A basic binary tree with a string, int[] node.  string is the key, int[] is the value
    /// </summary>
    public class BinaryTree
    {
        #region Fields

        // Points to the _root of the tree
        private TreeNode _root;

        // a count of nodes in the tree, duh!
        private int _count = 0;

        #endregion

        #region Properties

        /// <summary>
        /// Returns the number of nodes in the tree
        /// </summary>
        /// <returns>Number of nodes in the tree</returns>
        public int Count
        {
            get { return _count; }
        }

        #endregion

        /// <summary>
        /// Initializes a new instance of the <see cref="BinaryTree"/> class.
        /// </summary>
        public BinaryTree()
        {
            _root = null;
            _count = 0;
        }

        #region Public Methods

        /// <summary>
        /// Clear the binary tree.
        /// </summary>
        public void Clear()
        {
            this.KillTree( ref _root );
            _count = 0;
        }       

        /// <summary>
        /// Find name in tree. Return a reference to the node
        /// if symbol found else return null to indicate failure.
        /// </summary>
        /// <param name="name">Name of node to locate</param>
        /// <returns>Returns null if it fails to find the node, else returns reference to node</returns>
        public TreeNode FindSymbol( string name )
        {
            TreeNode np = _root;

            int cmp;
            
            while( np != null )
            {
                cmp = String.CompareOrdinal( name, np.Name );

                if( cmp == 0 )   // found !
                {
                    return np;
                }

                if( cmp < 0 )
                {
                    np = np.Left;
                }
                else
                {
                    np = np.Right;
                }
            }
            return null;  // Return null to indicate failure to find name
        }

        /// <summary>
        /// Recursively locates an empty slot in the binary tree and inserts the node
        /// </summary>
        /// <param name="node">The node.</param>
        /// <param name="tree">The tree.</param>
        private void Add( TreeNode node, ref TreeNode tree )
        {
            if( tree == null )
            {
                tree = node;
            }
            else
            {
                // If we find a node with the same name then it's 
                // a duplicate and we can't continue
                int comparison = String.CompareOrdinal( node.Name, tree.Name );

                if( comparison == 0 )
                {
                    throw new Exception();
                }

                if( comparison < 0 )
                {
                    Add( node, ref tree.Left );
                }
                else
                {
                    Add( node, ref tree.Right );
                }
            }
        }

        /// <summary>
        /// Add a symbol to the tree if it's a new one. Returns reference to the new
        /// node if a new node inserted, else returns null to indicate node already present.
        /// </summary>
        /// <param name="name">Name of node to add to tree</param>
        /// <param name="d">Value of node</param>
        /// <returns> Returns reference to the new node is the node was inserted.
        /// If a duplicate node (same name was located then returns null</returns>
        public TreeNode Insert( string name, int[] codes )
        {
            TreeNode node = new TreeNode( name, codes );
            try
            {
                if( _root == null )
                {
                    _root = node;
                }
                else
                {
                    Add( node, ref _root );
                }
                
                _count++;
                
                return node;

            }
            catch( Exception )
            {
                return null;
            }
        }

        // Searches for a node with name key, name. If found it returns a reference
        // to the node and to thenodes parent. Else returns null.
        private TreeNode FindParent( string name, ref TreeNode parent )
        {
            TreeNode np = _root;
            
            parent = null;
            
            int cmp;

            while( np != null )
            {
                cmp = String.Compare( name, np.Name );
                if( cmp == 0 )   // found !
                    return np;

                if( cmp < 0 )
                {
                    parent = np;
                    np = np.Left;
                }
                else
                {
                    parent = np;
                    np = np.Right;
                }
            }

            return null;  // Return null to indicate failure to find name

        }

        /// <summary>
        /// Find the next ordinal node starting at node startNode.
        /// Due to the structure of a binary search tree, the
        /// successor node is simply the left most node on the right branch.
        /// </summary>
        /// <param name="startNode">Name key to use for searching</param>
        /// <param name="parent">Returns the parent node if search successful</param>
        /// <returns>Returns a reference to the node if successful, else null</returns>
        public TreeNode FindSuccessor( TreeNode startNode, ref TreeNode parent )
        {
            parent = startNode;
            
            // Look for the left-most node on the right side
            startNode = startNode.Right;
            
            while( startNode.Left != null )
            {
                parent = startNode;
                startNode = startNode.Left;
            }

            return startNode;
        }

        /// <summary>
        /// Delete a given node. This is the more complex method in the binary search
        /// class. The method considers three senarios, 1) the deleted node has no
        /// children; 2) the deleted node as one child; 3) the deleted node has two
        /// children. Case one and two are relatively simple to handle, the only
        /// unusual considerations are when the node is the _root node. Case 3) is
        /// much more complicated. It requires the location of the successor node.
        /// The node to be deleted is then replaced by the sucessor node and the
        /// successor node itself deleted. Throws an exception if the method fails
        /// to locate the node for deletion.
        /// </summary>
        /// <param name="key">Name key of node to delete</param>
        public void Delete( string key )
        {
            TreeNode parent = null;

            // First find the node to delete and its parent
            TreeNode nodeToDelete = FindParent( key, ref parent );
            
            if( nodeToDelete == null )
            {
                throw new Exception( "Unable to delete node: " + key.ToString() );  // can't find node, then say so 
            }

            // Three cases to consider, leaf, one child, two children

            // If it is a simple leaf then just null what the parent is pointing to
            if( ( nodeToDelete.Left == null ) && ( nodeToDelete.Right == null ) )
            {
                if( parent == null )
                {
                    _root = null;
                    return;
                }

                // find out whether left or right is associated 
                // with the parent and null as appropriate
                if( parent.Left == nodeToDelete )
                {
                    parent.Left = null;
                }
                else
                {
                    parent.Right = null;
                }

                _count--;
                return;
            }

            // One of the children is null, in this case
            // delete the node and move child up
            if( nodeToDelete.Left == null )
            {
                // Special case if we're at the _root
                if( parent == null )
                {
                    _root = nodeToDelete.Right;
                    return;
                }

                // Identify the child and point the parent at the child
                if( parent.Left == nodeToDelete )
                {
                    parent.Right = nodeToDelete.Right;
                }
                else
                {
                    parent.Left = nodeToDelete.Right;
                }

                // Clean up the deleted node
                nodeToDelete = null; 
                _count--;
                return;

            }

            // One of the children is null, in this case
            // delete the node and move child up
            if( nodeToDelete.Right == null )
            {
                // Special case if we're at the _root            
                if( parent == null )
                {
                    _root = nodeToDelete.Left;
                    return;
                }

                // Identify the child and point the parent at the child
                if( parent.Left == nodeToDelete )
                {
                    parent.Left = nodeToDelete.Left;
                }
                else
                {
                    parent.Right = nodeToDelete.Left;
                }

                // Clean up the deleted node
                nodeToDelete = null; 
                _count--;
                return;

            }

            // Both children have nodes, therefore find the successor, 
            // replace deleted node with successor and remove successor
            // The parent argument becomes the parent of the successor
            TreeNode successor = FindSuccessor( nodeToDelete, ref parent );

            // Make a copy of the successor node
            TreeNode tmp = new TreeNode( successor.Name, successor.Codes );

            // Find out which side the successor parent is pointing to the
            // successor and remove the successor
            if( parent.Left == successor )
            {
                parent.Left = null;
            }
            else
            {
                parent.Right = null;
            }

            // Copy over the successor values to the deleted node position
            nodeToDelete.Name = tmp.Name;
            nodeToDelete.Codes = tmp.Codes;
            _count--;
        }

        /// <summary>
        /// Return the tree depicted as a simple string, useful for debugging, eg
        /// 50(40(30(20, 35), 45(44, 46)), 60)
        /// </summary>
        /// <returns>Returns the tree</returns>
        public string DrawTree()
        {
            return DrawNode( _root );
        }

        /// <summary>
        /// Returns a <see cref="System.String"/> that represents this instance.
        /// </summary>
        /// <returns>
        /// A <see cref="System.String"/> that represents this instance.
        /// </returns>
        public override string ToString()
        {
            return this.DrawTree();
        }

        #endregion

        #region Private Methods

        // Recursive destruction of binary search tree, called by method clear
        // and destroy. Can be used to kill a sub-tree of a larger tree.
        // This is a hanger on from its Delphi origins, it might be dispensable
        // given the garbage collection abilities of .NET
        private void KillTree( ref TreeNode p )
        {
            if( p != null )
            {
                KillTree( ref p.Left );

                KillTree( ref p.Right );

                p = null;

            }
        }

        /// <summary>
        /// Draws the node.
        /// </summary>
        /// <param name="node">The node.</param>
        /// <returns></returns>
        private string DrawNode( TreeNode node )
        {
            if( node == null )
            {
                return "empty";
            }

            if( node.Left == null &&
                node.Right == null )
            {
                return node.Name;
            }
            if( node.Left != null &&
                node.Right == null )
            {
                return String.Format( "{0}({1}, )", node.Name, DrawNode( node.Left ) );
            }
            if( node.Right != null &&
                node.Left == null )
            {
                return String.Format( "{0}(_,{1})", node.Name, DrawNode( node.Right ) );

            }

            return String.Format( "{0}({1},{2})", node.Name, DrawNode( node.Left ), DrawNode( node.Right ) );

        }

        #endregion

    }
}

Comments

Post a Comment

Popular posts from this blog

String.Replace vs Regex.Replace

-
Image
I recently ran into a situation where I had to do some string manipulation. I had to replace some bad text with valid text. All this had to do with creating valid xml element names. So we had to string white space and some other invalid characters and replace them with valid xml element formatting. To do this we ended up using the Regex.Replace static method. Simply because there was some complexity involved that would have entailed using more then 1 String.Replace call when we can do it all with one regular expression. This caused some discussion about how heavy the regex class is and when to use it. I decided to do some testing and these are my results. First the code static void Main( string[] args ) { // this is our test value string testValue = "This is a test string"; int count; // run the regex replace DateTime regexStart = DateTime.Now; for( count = 0; count < 10000000; count++ ) { string newValue = Regex.Replace( testValue, ...
Read more

C# Producer Consumer using Rabbit MQ

-
So I've been learning about the different message queuing systems and discovered rabbit MQ, an open source and very popular message queuing system. I've created a very basic producer/consumer system that sends a message to a rabbit MQ queue. Producer/Consumer is pretty simple, you have two systems a producer that writes to a queue and a consumer that reads from a queue. This is desirable because it splits responsibility and allows for scalability. The code below is going to assume you have a rabbit MQ instance installed on your local machine. You can get rabbit MQ here:  https://www.rabbitmq.com/ Now the code is broken down into 3 parts, the main program, the producer, and the consumer. This is a basic example so its using old school threading rather than the new async/await .net prefers. But this is just to show how to use rabbit MQ in C# and to demonstrate a producer/consumer example. You will need to make sure your project has the rabbit MQ client nuget package installed...
Read more

C# Form Application in Kiosk Mode/Fullscreen

-
Sometimes you need to have a C# windows form application run in full screen mode.  Like you see on a kiosk at a mall or some stand alone machine.  It's fairly easy you just need to set some of the properties on the Form either in it's OnLoad method or directly in the designer. In the OnLoad method of the main Form set these values, or again set them directly in the designer. this.MaximizeBox = false; this.TopMost = true; this.FormBorderStyle = System.Windows.Forms.FormBorderStyle.None; this.WindowState = System.Windows.Forms.FormWindowState.Maximized;
Read more