2
\$\begingroup\$

Since my last question (BinaryTree<T> written in C#), I have rewritten my code based on the responses. My project can be found on my GitHub repo here;

using System;
using System.Diagnostics;
using System.IO;
using System.Runtime.Serialization;
using System.Runtime.Serialization.Formatters.Binary;

namespace BinaryTree
{
    /// <summary>
    ///     Represents a binary tree <seealso href="https://en.wikipedia.org/wiki/Binary_tree" />.
    /// </summary>
    /// <typeparam name="T">The type which this tree should contain.</typeparam>
    [Serializable]
    [DataContract]
    public class BinaryTree<T> where T : IComparable<T>
    {
        [DataMember] private Node _parentNode;

        public BinaryTree()
        {
            Debug.WriteLine("Initializing binary-tree..");

            _parentNode = new Node();
        }

        /// <summary>
        ///     Adds the specific item inside the binary-tree using binary-tree logic.
        /// </summary>
        /// <param name="item">The item that will be added.</param>
        public void Add(T item)
        {
            Debug.WriteLine("Adding an item in this binary-tree..");

            var currentNode = _parentNode;
            while (true)
            {
                if (currentNode.Item.data == null || currentNode.Item.count.Equals(0))
                {
                    currentNode.Item.data = item;
                    currentNode.Item.count = 1;
                    return;
                }

                var comparisonValue = item.CompareTo(currentNode.Item.data);

                if (comparisonValue > 0)
                {
                    if (currentNode.Right == null)
                    {
                        currentNode.Right = new Node(item);
                        return;
                    }

                    Debug.WriteLine($"{item} > {currentNode.Item.data} → move to right lower node..");

                    currentNode = currentNode.Right;
                }
                else if (comparisonValue.Equals(0))
                {
                    currentNode.Item.count++;
                    return;
                }
                else
                {
                    if (currentNode.Left == null)
                    {
                        currentNode.Left = new Node(item);
                        return;
                    }

                    Debug.WriteLine($"{item} < {currentNode.Item.data} → move to left lower node..");

                    currentNode = currentNode.Left;
                }
            }
        }

        /// <summary>
        ///     Removes the specific item inside the binary-tree using binary-tree logic.
        /// </summary>
        /// <param name="item">The item that will be removed.</param>
        /// <param name="fullyRemoval">When set on true will remove said item without any respect towards their count.</param>
        public void Remove(T item, bool fullyRemoval = false)
        {
            Debug.WriteLine("Removing an item in this binary-tree..");

            var currentNode = _parentNode;
            Node prevNode = default;

            while (true)
            {
                if (currentNode.Item.data == null) return;

                var comparisonValue = item.CompareTo(currentNode.Item.data);

                if (comparisonValue > 0)
                {
                    if (currentNode.Right == null) return;

                    (prevNode, currentNode) = (currentNode, currentNode.Right);
                }
                else if (comparisonValue.Equals(0))
                {
                    if (currentNode.Item.count > 1 && !fullyRemoval)
                        currentNode.Item.count--;
                    else
                        SkipNode(prevNode, currentNode);

                    return;
                }
                else
                {
                    if (currentNode.Left == null) return;

                    (prevNode, currentNode) = (currentNode, currentNode.Left);
                }
            }
        }

        private void SkipNode(Node prevNode, Node nodeToSkip)
        {
            var countOfFurtherNodes = 0;

            if (nodeToSkip.Right != null) countOfFurtherNodes++;

            if (nodeToSkip.Left != null) countOfFurtherNodes++;
            if (prevNode == null)
            {
                switch (countOfFurtherNodes)
                {
                    case 0:
                        nodeToSkip.Item = (default(T), 0);
                        return;
                    case 1:
                        nodeToSkip.Item = nodeToSkip.Right?.Item ?? nodeToSkip.Left.Item;
                        return;
                    case 2:
                        var temp = SearchForLeftMostRightNode(nodeToSkip);
                        Remove(temp.Item.data, true);
                        temp.Left = nodeToSkip.Left;
                        temp.Right = nodeToSkip.Right;

                        nodeToSkip.Item = temp.Item;
                        return;
                }
            }

            var rightPath = nodeToSkip.Item.data.CompareTo(prevNode.Item.data);
            switch (countOfFurtherNodes)
            {
                case 0 when rightPath > 0:
                    prevNode.Right = null;
                    break;
                case 0:
                    prevNode.Left = null;
                    break;
                case 1 when rightPath > 0:
                    prevNode.Right = nodeToSkip.Right ?? nodeToSkip.Left;
                    break;
                case 1:
                    prevNode.Left = nodeToSkip.Right ?? nodeToSkip.Left;
                    break;
                case 2 when rightPath > 0:
                    var temp = SearchForLeftMostRightNode(nodeToSkip);
                    Remove(temp.Item.data, true);
                    temp.Left = nodeToSkip.Left;
                    temp.Right = nodeToSkip.Right;

                    prevNode.Right = temp;
                    break;
                case 2:
                    var temp2 = SearchForLeftMostRightNode(nodeToSkip);
                    Remove(temp2.Item.data, true);
                    temp2.Left = nodeToSkip.Left;
                    temp2.Right = nodeToSkip.Right;

                    prevNode.Left = temp2;
                    break;
            }
        }

        private Node SearchForLeftMostRightNode(Node node)
        {
            if (node.Right == null) return node;

            node = node.Right;

            while (node.Left != null) node = node.Left;

            return node;
        }

        /// <summary>
        ///     Searches for a specific item inside this binary-tree using binary-tree logic.
        /// </summary>
        /// <param name="item"></param>
        /// <returns>Returns the count of said item if existing - 0 if otherwise.</returns>
        public int Contains(T item)
        {
            Debug.WriteLine("Searching an item in this binary-tree..");

            var currentNode = _parentNode;
            while (true)
            {
                if (currentNode.Item.data == null) return 0;

                var comparisionValue = item.CompareTo(currentNode.Item.data);

                if (comparisionValue > 0)
                {
                    if (currentNode.Right == null) return 0;

                    Debug.WriteLine($"{item} > {currentNode.Item.data} → search in right lower node..");

                    currentNode = currentNode.Right;
                }
                else if (comparisionValue.Equals(0))
                {
                    return currentNode.Item.count;
                }
                else
                {
                    if (currentNode.Left == null) return 0;


                    Debug.WriteLine($"{item} < {currentNode.Item.data} → search in left lower node..");

                    currentNode = currentNode.Left;
                }
            }
        }

        /// <summary>
        ///     Clears everything out of this binary-tree.
        /// </summary>
        public void Clear()
        {
            Debug.WriteLine("Clearing this binary-tree..");

            _parentNode = new Node();
        }

        public override bool Equals(object obj)
        {
            return obj is BinaryTree<T> tree && tree._parentNode.Equals(_parentNode);
        }

        public void Serialize(string file)
        {
            using (var writer = new StreamWriter(file))
            {
                var bf = new BinaryFormatter();
                bf.Serialize(writer.BaseStream, this);
            }
        }

        public static BinaryTree<T> Deserialize(string file)
        {
            using (var reader = new StreamReader(file))
            {
                var bf = new BinaryFormatter();
                return (BinaryTree<T>) bf.Deserialize(reader.BaseStream);
            }
        }

        public override int GetHashCode()
        {
            return HashCode.Combine(_parentNode);
        }

        /// <summary>
        ///     Represents a node of a binary-tree. This may be either a simple node, a parent, or a leaf.
        /// </summary>
        /// <typeparam name="T">The type which this node should contain.</typeparam>
        [Serializable]
        [DataContract]
        private class Node
        {
            /// <summary>
            ///     Saved data and count of data - inside this specific node.
            /// </summary>
            [DataMember] internal (T data, int count) Item;

            /// <summary>
            ///     Left "lower" arm of current node - this is where everything smaller than this node is getting redirect towards.
            /// </summary>
            [DataMember] internal Node Left;

            /// <summary>
            ///     Right "lower" arm of current node - this is where everything bigger than this node is getting redirect towards.
            /// </summary>
            [DataMember] internal Node Right;

            internal Node(T item)
            {
                Item = (item, 1);
            }

            internal Node()
            {
            }

            public override bool Equals(object obj)
            {
                return obj is Node node &&
                       (node.Right?.Equals(Right) ?? Right == null) &&
                       (node.Item.data?.CompareTo(Item.data).Equals(0) ?? Item.data == null) &&
                       node.Item.count.Equals(Item.count) &&
                       (node.Left?.Equals(Left) ?? Left == null);
            }

            public override int GetHashCode()
            {
                return HashCode.Combine(Right, Item, Left);
            }
        }
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Do you have any unit tests? \$\endgroup\$ – Peter Taylor Feb 13 at 14:59
  • \$\begingroup\$ Yes, you can find those in my repo. \$\endgroup\$ – TheRealVira Feb 13 at 15:59
2
\$\begingroup\$

Here's a new unit test which currently fails. Add

using System.Collections.Generic;
using System.Linq;

and then

    [TestMethod]
    public void TestCombinations()
    {
        // Test all sequences of 5 operations drawn from adding and removing four distinct elements.
        for (int i = 0; i < 1 << 15; i++)
        {
            var list = new List<int>();
            var tree = new BinaryTree<int>();

            var program = i;
            for (int j = 0; j < 5; j++)
            {
                int instruction = program & 1;
                program >>= 1;
                int value = program & 3;
                program >>= 2;

                if (instruction == 0)
                {
                    list.Add(value);
                    tree.Add(value);
                }
                else
                {
                    list.Remove(value);
                    tree.Remove(value);
                }

                for (value = 0; value < 4; value++)
                {
                    Assert.AreEqual(list.Count(elt => elt == value), tree.Contains(value));
                }
            }
        }
    }
\$\endgroup\$
  • \$\begingroup\$ I have updated my repo - your unit-test has been added and the bug fixed! Thank you very much again for your response. \$\endgroup\$ – TheRealVira Feb 13 at 20:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.