Бинарное дерево поиска

  Сегодня я хочу представить вашему вниманию свою реализацию бинарного дерева поиска. Пример написан только для себя, чтобы освежить в памяти особенности разных структур данных, ну и конечно изучить что-то новое.  То есть эксперимент носит скорее учебный характер.
  Про бинарное дерево поиска очень много информации в интернете, так что выдумывать ничего не придется. Нужно только сделать свою реализацию.

Для начала определимся с узлами дерева

/// <summary>
/// Узел для дерева
/// </summary>
/// <typeparam name="TKey">Тип используемого ключа</typeparam>
/// <typeparam name="TValue">Тип значения для хранения</typeparam>
public class TreeNode<TKey, TValue>
 where TKey : IComparable<TKey> // Чтобы ключи можно было сравнивать
 where TValue : class // Чтобы значения могли принимать нулевые значения
{
 /// <summary>
 /// Значение ключа в текущем узле
 /// </summary>
 public TKey Key { get; private set; }

 /// <summary>
 /// Значение, хранящееся в текущем узле
 /// </summary>
 public TValue Value { get; set; }

 /// <summary>
 /// Конструктор. Каждый узел должен содержать как минимум ключ и значение
 /// </summary>
 /// <param name="key">Ключ узла</param>
 /// <param name="value">Значение, которое будет хранить узел</param>
 public TreeNode(TKey key, TValue value)
 {
  Key = key;
  Value = value;
 }
}

* This source code was highlighted with Source Code Highlighter.

   Очевидно, узлы будут содержать ключи, которые необходимо сравнивать. Поэтому тип ключа должен реализовывать IComparable<TKey>. В будущем мы реализуем поиск по дереву значения по ключу. Если поиск не удастся (нет такого ключа в дереве), то возвращать вместо значения будем null. Поэтому условимся, что значением может быть только класс. Ключ узла можно задать только через конструктор.
   Укажем связи узла - добавим в тело класса узлы младшего и старшего сыновей и родительский узел:

/// <summary>
/// Младший сын для текущего узла
/// </summary>
public TreeNode<TKey, TValue> Less
{
  get
  {
    return _less;
  }
  // При установке младшего сына указываем, что являемся родителем для него
  set
  {
    if (_less != null)
      _less._parent = null;

    _less = value;

    if (_less != null)
      _less._parent = this;
  }
}

/// <summary>
/// Старший сын для текущего узла
/// </summary>
public TreeNode<TKey, TValue> Greater
{
  get
  {
    return _greater;
  }
  // При установке старшего сына указываем, что являемся родителем для него
  set
  {
    if (_greater != null)
      _greater._parent = null;

    _greater = value;

    if (_greater != null)
      _greater._parent = this;
  }
}

/// <summary>
/// Родительский узел.
/// </summary>
public TreeNode<TKey, TValue> Parent
{
  // Родительский узел через свойство можно только устанавливать
  get
  {
    return _parent;
  }
}

private TreeNode<TKey, TValue> _less;
private TreeNode<TKey, TValue> _greater;
private TreeNode<TKey, TValue> _parent;

* This source code was highlighted with Source Code Highlighter.

   Как видно из листинга, родительский узел явно задать нельзя. Но зато он задается автоматически у сыновей, если какой-либо другой узел становится сыном для текущего. Это позволяет сократить некоторую рассогласованность в дереве. Но от всех пробем все же не спасает. По умолчанию узел считается корневым, то есть не имеет родителей. А также не имеет ни младшего, ни старшего сына. Если придется устанавливать узел в качестве корневого, то пригодится метод удаления связи с родителем:

/// <summary>
/// Позволяет задать текущий узел как родительский
/// </summary>
public void MakeRoot()
{
  _parent = null;
}

* This source code was highlighted with Source Code Highlighter.

   Резберем, как должно выглядеть дерево

/// <summary>
/// Само дерево бинарногго поиска
/// </summary>
/// <typeparam name="TKey">Тип используемого ключа</typeparam>
/// <typeparam name="TValue">Тип значения для хранения</typeparam>
public class Tree<TKey, TValue> where TKey : IComparable<TKey> // Чтобы ключи можно было сравнивать
                where TValue : class // Чтобы значения могли принимать нулевые значения
{
  /// <summary>
  /// Корневой узел
  /// </summary>
  public TreeNode<TKey, TValue> Root { get; private set; }

  /// <summary>
  /// Объявление индексатора
  /// </summary>
  /// <param name="key">Ключ искомого значение</param>
  /// <returns>Найденное значение, иначе null</returns>
  public TValue this[TKey key]
    {
      get
      {
        // Получение значения через поиск по дереву
        return Find(key);
      }

      set
      {
        // Добавление или смена существующего значения, соответствующего ключу
        Add(key, value);
      }
    }
}

* This source code was highlighted with Source Code Highlighter.

   Класс дерева пользуется теми же типами в шаблоне, что и класс узла. Дерево имеет корневой узел, а также индексатор для быстрого доступа к хранимым значениям. Индексатор содержит еще неописанные методы, которые позволяют дереву принимать новые значения для хранения, а также выдавать имеющиеся по предоставленному ключу.
  Так как нам все равно придется искать в дереве узлы, содержащие ближайшие ключи к заранее заданному, нужно описать соответствующий метод:

/// <summary>
/// Поиск узла с ближайшим значением ключа
/// </summary>
/// <param name="node">Начальный узел поиска</param>
/// <param name="key">Значение ключа поиска</param>
/// <returns>Найденный узел либо null</returns>
public static TreeNode<TKey, TValue> FindNearestFrom(TreeNode<TKey, TValue> node, TKey key)
{
  // Если начального узла нет, то поиска не будет
  if (node == null)
    return null;

  // Если ключ начального узла совпадает с ключом поиска,
  // то возвращаем начальный ключ
  if (node.Key.CompareTo(key) == 0)
    return node;

  var temp = node;

  // Цикл движения по дереву
  while (true)
  {
    var cmpr = temp.Key.CompareTo(key);

    // Искомый узел найден, если его ключ соответствет ключу поиска
    if (cmpr == 0)
      return temp;

    // Если ключ текущего узла больше ключа поиска,
    // то движемся к младшему сыну
    if (cmpr > 0)
    {
      // Если младшего сына нет, то искомый узел найден
      if (temp.Less == null)
        return temp;
      temp = temp.Less;
    }

    // Если ключ текущего узла меньше ключа поиска,
    // то движемся к старшему сыну
    if (cmpr < 0)
    {
      // Если старшего сына нет, то искомый узел найден
      if (temp.Greater == null)
        return temp;
      temp = temp.Greater;
    }
  }
}

* This source code was highlighted with Source Code Highlighter.

   Метод FindNearestFrom объявлен статическим, так как не зависит от конкретного дерева. Он выполняет поиск в дереве узла с ближайшим ключем к указанному от конкретного узла в дереве. Этот метод значительно упрощает реализацию метода поиска значения в дереве по заданному ключу.
   Методы добавления нового значения в дерево и получения уже имеющегося из него выглядят следующим образом:

/// <summary>
/// Позволяет добавить значение в дерево
/// </summary>
/// <param name="key">Ключ значения</param>
/// <param name="value">Добавляемое значение</param>
/// <returns>Значение, которое было добавлено</returns>
public TValue Add(TKey key, TValue value)
{ 
  // Поиск узла дерева с наиболее близким ключом
  var node = FindNearestFrom(Root, key);

  // Если таких узлов не найдено (пустое дерево, например)
  // то возвращаем null
  if (node == null)
  {
    Root = new TreeNode<TKey, TValue>(key, value);
    return Root.Value;
  }

  // Если у текущего узла установлен указанный ключ,
  // то есть значение с указанным ключом уже есть в дереве,
  // то заменяем значение на вновь устанавливаемое
  if (node.Key.CompareTo(key) == 0)
  {
    node.Value = value;
    return node.Value;
  }

  // Указанный ключ оказался менее ключа найденного узла
  if (node.Key.CompareTo(key) > 0)
  {
    // Добавляем младшего брата найденному узлу
    node.Less = new TreeNode<TKey, TValue>(key, value);
    return node.Less.Value;
  }

  // Указанный ключ оказался более ключа найденного узла
  if (node.Key.CompareTo(key) < 0)
  {
    // Добавляем старшего брата найденному узлу
    node.Greater = new TreeNode<TKey, TValue>(key, value);
    return node.Greater.Value;
  }

  // Случилось что-то сверхъестественное
  return null;
}

/// <summary>
/// Позволяет получить значение по ключу
/// Если указанного ключа нет в дереве, то возвращается null
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public TValue Find(TKey key)
{
  // Поиск узла дерева с наиболее близким ключом
  var node = FindNearestFrom(Root, key);

  // Если таких узлов не найдено (пустое дерево, например)
  // то возвращаем null
  if (node == null) return null;

  // Если ключ найденного узла равен заданному, то возвращаем значение узла
  // Иначе возвращается null
  return node.Key.CompareTo(key) == 0 ? node.Value : null;
}

* This source code was highlighted with Source Code Highlighter.

   Метод поиска значения по ключу тривиален, а вот у метода добавления новых значений есть ряд особенностей. Во-первых новые значения добавляются только в листы. Таким образом, никакой оптимизации при добавлении значения нет. Еще одна особенность конкретно моей реализации, если значение для указанного ключа уже есть в дереве, то оно перезаписывается.
   Ну и на последок самое сложное в бинарном дереве поиска - удаление значения по ключу. Основная идея состоит в том, что найденный узел в дереве замещается узлом с ближайшим значением ключа. При условии, что поиск осуществляется ниже по дереву от удаляемого узла.

/// <summary>
/// Удаляет значение, соответствующее данному ключу
/// </summary>
/// <param name="key">Ключ для удаления</param>
public void Delete(TKey key)
{
  // Ищем узел с заданным ключом
  var node = FindNearestFrom(Root, key);

  // Если узел с таким ключом не найден, то удаления не будет
  if (node == null)
    return;

  // Ищем ближайший узел к наденному, ключ которого меньше
  var leafLess = FindNearestFrom(node.Less, key);
  // Ищем ближайший узел к наденному, ключ которого больше
  var leafGreater = FindNearestFrom(node.Greater, key);

  TreeNode<TKey, TValue> leaf;

  // Если найден хотя бы один из ближайших узлов
  if (leafLess != null || leafGreater != null)
  {
    // Устанавливаем замещающий узел
    if (leafLess != null && leafLess.Less != null)
      leaf = leafLess;
    else if (leafGreater != null && leafGreater.Greater != null)
      leaf = leafGreater;
    else
      leaf = leafLess ?? leafGreater;

    // Вынимаем замещающий узел из дерева
    if (leaf.Parent.Less != null && leaf.Parent.Less.Key.CompareTo(leaf.Key) == 0)
      leaf.Parent.Less = leaf.Greater;
    else
      leaf.Parent.Greater = leaf.Less;
  
  }
  // Ближайших узлов нет
  // Мы имеем дело с листом
  else
  {
    // Найденный узел может оказаться корневым
    if (node.Parent != null)
    {
      // Если найденный узел просто лист,
      // то избавиться от него будет просто
      if (node.Parent.Less != null && node.Parent.Less.Key.CompareTo(node.Key) == 0)
        node.Parent.Less = null;
      else
        node.Parent.Greater = null;
    }
    else
      // Найденный узел - корневой
      // Удаляем последний узел в дереве
      Root = null;

    return;
  }

  // Замещающий узел становится на место найденного
  leaf.Greater = node.Greater;
  leaf.Less = node.Less;

  // Если найденный узел не является корневым
  if (node.Parent != null)
  {
    // Передаем родительский узел от найденного к замещающему
    if (node.Parent.Less != null && node.Parent.Less.Key.CompareTo(node.Key) == 0)
      node.Parent.Less = leaf;
    else
      node.Parent.Greater = leaf;
  }
  else
  {
    // Удаляемый узел - корневой
    // Замещающий узел становится корневым
    leaf.MakeRoot();
    Root = leaf;
  }
}

* This source code was highlighted with Source Code Highlighter.

   В текущей реализации безусловно есть изъяны. Например, как поддержки согласованности структуры дерева. Узел может быть сыном к какому-либо другому узлу и быть корневым, то есть не иметь родителя. Очевидно, это какая-то архитектурная ошибка. Интересно, как бы вы преодолели ее?