C# 二分探索木

ごく一般的な二分探索木のC#による実装。AVL木のようにバランスはしない。

using System;

public sealed class Node<TKey, TValue> where TKey : IComparable<TKey>
{
    private TKey key;
    private TValue value;
    private Node<TKey, TValue> left;
    private Node<TKey, TValue> right;
    public Node(TKey key, TValue value)
    {
        this.key = key;
        this.value = value;
        this.left = null;
        this.right = null;
    }
    public TKey Key
    {
        get { return key; }
        set { key = value; }
    }
    public TValue Value
    {
        get { return value; }
        set { this.value = value; }
    }
    public Node<TKey, TValue> Left
    {
        get { return left; }
        set { left = value; }
    }
    public Node<TKey, TValue> Right
    {
        get { return right; }
        set { right = value; }
    }
}

public sealed class BinarySearchTree<TKey, TValue> where TKey : IComparable<TKey>
{
    private Node<TKey, TValue> root = null;

    public Boolean Add(TKey key, TValue value)
    {
        if (root == null)
        {
            root = new Node<TKey, TValue>(key, value);
            return true;
        }

        Node<TKey, TValue> curr = root;
        while (true)
        {
            Int32 cond = key.CompareTo(curr.Key);
            if (cond < 0)
            {
                if (curr.Left == null)
                {
                    curr.Left = new Node<TKey, TValue>(key, value);
                    break;
                }
                else
                {
                    curr = curr.Left;
                }
            }
            else if (cond > 0)
            {
                if (curr.Right == null)
                {
                    curr.Right = new Node<TKey, TValue>(key, value);
                    break;
                }
                else
                {
                    curr = curr.Right;
                }
            }
            else
            {
                //キーは既に存在している
                return false;
            }
        }

        //追加成功
        return true;
    }

    public Boolean Searech(TKey key, out TValue value)
    {
        Node<TKey, TValue> curr = root;
        while (curr != null)
        {
            Int32 cond = key.CompareTo(curr.Key);
            if (cond < 0)
            {
                curr = curr.Left;
            }
            else if (cond > 0)
            {
                curr = curr.Right;
            }
            else
            {
                value = curr.Value;
                return true;
            }
        }
        value = default(TValue);
        return false;
    }

    public Boolean Remove(TKey key)
    {
        Node<TKey, TValue> curr = root;
        Node<TKey, TValue> parent = null;
        Boolean goToLeftChild = true;
        while (true)
        {
            if (curr == null)
            {
                return false;
            }

            Int32 cond = key.CompareTo(curr.Key);
            if (cond == 0)
            {
                break;
            }
            else
            {
                parent = curr;
                if (cond < 0)
                {
                    goToLeftChild = true;
                    curr = curr.Left;
                }
                else
                {
                    goToLeftChild = false;
                    curr = curr.Right;
                }
            }
        }

        if (curr.Left == null) //左の子がない
        {
            if (curr == root)
            {
            }
            else if (goToLeftChild)
            {
                parent.Right = curr.Right;
            }
            else
            {
                parent.Right = curr.Right;
            }
        }
        else if (curr.Right == null) //右の子がない
        {
            if (curr == root)
            {
                root = curr.Left;
            }
            else if (goToLeftChild)
            {
                parent.Left = curr.Left;
            }
            else
            {
                parent.Right = curr.Left;
            }
        }
        else //子は２つ
        {
            parent = curr;
            Node<TKey, TValue> left = curr.Left;
            goToLeftChild = true;
            while (left.Right != null)
            {
                parent = left;
                left = left.Right;
                goToLeftChild = false;
            }
            curr.Key = left.Key;
            curr.Value = left.Value;
            if (goToLeftChild)
            {
                parent.Left = left.Left;
            }
            else
            {
                parent.Right = left.Left;
            }
        }
        return true;
    }

    private void PrintSubTree(Node<TKey, TValue> node)
    {
        if (node != null)
        {
            //左部分木をキー値昇順に表示
            PrintSubTree(node.Left);

            //nodeを表示
            Console.WriteLine("{0} {1}", node.Key, node.Value);

            //右部分木をキー値昇順に表示
            PrintSubTree(node.Right);
        }
    }

    public void PrintTree()
    {
        PrintSubTree(root);
    }
}

class Program
{
    static void Main()
    {
        BinarySearchTree<Int32, Int32> tree = new BinarySearchTree<Int32, Int32>();
        tree.Add(50, 50);
        tree.Add(25, 25);
        tree.Add(75, 75);
        tree.Add(10, 10);
        tree.Add(20, 20);
        tree.Add(15, 15);
        tree.Add(100, 100);
        tree.Add(30, 30);
        tree.Add(70, 70);
        tree.Add(60, 60);
        tree.Add(65, 65);
        tree.Add(73, 73);
        tree.Add(74, 74);

        tree.PrintTree();

        tree.Remove(75);

        Int32 value;
        if (tree.Searech(30, out value))
        {
            Console.WriteLine(value);
        }
    }
}