Hi Folks,

I thought I would post source code for a Binary Search Tree Algorithm that I recently worked on.

https://github.com/Romiko/Dev2

In a future post, I will post source code for a Balanced Binary Search Tree (Red Black Tree RBTree).

Remember with an unbalanced Binary Search Tree, if you insert data in order, it will actually resemble a linked list and not a binary tree, hence why it is important to use a Balanced Binary Search Tree.

Of course, you can use built in .NET framework types like SortedSet and SortedDictionary, but for those of you that want to write your own implementation, then this can be a good starting point.

Remember, the rules for a Binary Search Tree, which will also return data in a sorted order, using your IComparer implementation.

I also wrote a method to delete nodes from a Binary Search Tree, which will treats leaf nodes, nodes with one child and nodes with two children differently.

There is allot of articles out there on BST’s, but it is important, that if you want to understand them, that you must understand the rules governing the Insertion, Deletion and Retrieval algorithms.

You can find the source code, at my repository here:
https://github.com/Romiko/Dev2

You will notice that there is also numerous unit tests for the solution as well.

You will notice that the way I delete nodes, uses a Random dice, so not to Degenerate the Binary Tree, if it was balanced, this would not be necessary.

One more thing, I have avoided recursive functions, why? Well, with large binary trees, if you use recursive functions, the stack is going to run out of memory, so avoid them all together.

Here is some code snippets of important algorithms, if you have any questions, or want to contribute to the code, you are welcome to do so.

public void Add(TKey key, TValue value)
        {
            var newNode = new BinaryTreeNode { KeyValue = new KeyValuePair(key, value) };

            if (Root == null)
                Root = newNode;
            else
            {
                var current = Root;
                while (true)
                {
                    var compareResult = Comparer.Compare(key, current.KeyValue.Key);
                    if (compareResult == 0)
                        throw new ArgumentException("Duplicate key found.");

                    if (compareResult  0)
                        if (current.Right != null)
                            current = current.Right;
                        else
                        {
                            current.Right = newNode;
                            newNode.Parent = current;
                            break;
                        }
                }
            }
        }

private void Delete(BinaryTreeNode node)
        {
            var nodeType = GetNodeType(node);

            if (nodeType == NodeType.LeafeNode)
            {
                DeleteLeafNode(node);
                return;
            }
            if (nodeType == NodeType.HasOneChild)
            {
                DeleteNodeWithOneChild(node);
                return;
            }
            DeleteNodeWithTwoChildren(node);
        }

        private void DeleteNodeWithTwoChildren(BinaryTreeNode node)
        {
            // Use random delete method, to avoid degenerate tree structure.
            var replaceInOrderType = RollDiceForSuccessorOrPredecessor();

            if (replaceInOrderType == InOrderNode.Successor)
                UseSuccessor(node);
            else
                UsePredecessor(node);
        }

        private static void DeleteNodeWithOneChild(BinaryTreeNode node)
        {
            var theChild = node.Left ?? node.Right;
            theChild.Parent = node.Parent;
            switch (NodeLinkedToParentAs(node))
            {
                case NodeLinkToParentAs.Right:
                    node.Parent.Right = theChild;
                    break;
                case NodeLinkToParentAs.Left:
                    node.Parent.Left = theChild;
                    break;
                case NodeLinkToParentAs.Root:
                    node.Parent = null;
                    break;
            }
        }

        private static void DeleteLeafNode(BinaryTreeNode node)
        {
            if (NodeLinkedToParentAs(node) == NodeLinkToParentAs.Right)
                node.Parent.Right = null;
            else
                node.Parent.Left = null;
        }

        private void UsePredecessor(BinaryTreeNode node)
        {
            var replaceWith = ReadLastRightNode(node.Left);
            node.KeyValue = replaceWith.KeyValue;
            Delete(replaceWith);
        }

        private void UseSuccessor(BinaryTreeNode node)
        {
            var replaceWith = ReadLastLeftNode(node.Right);
            node.KeyValue = replaceWith.KeyValue;
            Delete(replaceWith);
        }

        private InOrderNode RollDiceForSuccessorOrPredecessor()
        {
            if (ForceDeleteType.HasValue)
                return ForceDeleteType.Value;

            var random = new Random();
            var choice = random.Next(0, 2);
            return choice == 0 ? InOrderNode.Predecessor : InOrderNode.Successor;
        }

https://github.com/Romiko/Dev2

• .Net Development