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

Popular Posts