Сегодня я хочу представить вашему вниманию свою реализацию бинарного дерева поиска. Пример написан только для себя, чтобы освежить в памяти особенности разных структур данных, ну и конечно изучить что-то новое. То есть эксперимент носит скорее учебный характер.
Про бинарное дерево поиска очень много информации в интернете, так что выдумывать ничего не придется. Нужно только сделать свою реализацию.
Для начала определимся с узлами дерева
Укажем связи узла - добавим в тело класса узлы младшего и старшего сыновей и родительский узел:
Так как нам все равно придется искать в дереве узлы, содержащие ближайшие ключи к заранее заданному, нужно описать соответствующий метод:
Методы добавления нового значения в дерево и получения уже имеющегося из него выглядят следующим образом:
Ну и на последок самое сложное в бинарном дереве поиска - удаление значения по ключу. Основная идея состоит в том, что найденный узел в дереве замещается узлом с ближайшим значением ключа. При условии, что поиск осуществляется ниже по дереву от удаляемого узла.
Про бинарное дерево поиска очень много информации в интернете, так что выдумывать ничего не придется. Нужно только сделать свою реализацию.
Для начала определимся с узлами дерева
/// <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.
В текущей реализации безусловно есть изъяны. Например, как поддержки согласованности структуры дерева. Узел может быть сыном к какому-либо другому узлу и быть корневым, то есть не иметь родителя. Очевидно, это какая-то архитектурная ошибка. Интересно, как бы вы преодолели ее?
// Поиск узла дерева с наиболее близким ключом
ОтветитьУдалитьvar node = FindNearestFrom(Root, key);
// Если таких узлов не найдено (пустое дерево, например)
// то возвращаем null
if (node == null)
{
Root = new TreeNode(key, value);
return Root.Value;
}
почему тут создаёшь новый рут?
вот тут
ОтветитьУдалить// Случилось что-то сверхъестественное
return null;
наверное лучше эксепшон породить
@Артем, по поводу добавления нового значения. Поиск узла дерева с наиболее близким ключем может дать Null только в одном случае - если дерево пустое. Если есть хотя бы Root, то ближайший узел найдется 100% (сам Root, например)
ОтветитьУдалить@Артем, по поводу сверхъестественного.
ОтветитьУдалитьДумаю, тут все же генерация исключения не нужна. Вряд ли до сюда вообще дойдет выполнение программы.
ну да, после
ОтветитьУдалитьif (node.Key.CompareTo(key) == 0)...
if (node.Key.CompareTo(key) > 0)...
if (node.Key.CompareTo(key) < 0)...
Останется только породить исключение
OMGException("how it happens??")
:)
чтобы не было ненужного ретурна, используй вместо последнего if (node.Key.CompareTo(key) < 0) просто else
ОтветитьУдалить@Артем, так более читаемо
ОтветитьУдалитьА почему в методе, где добавляешь узел, ты 3 раза сравниваешь?
ОтветитьУдалитьif (node.Key.CompareTo(key) == 0)...
if (node.Key.CompareTo(key) > 0)...
if (node.Key.CompareTo(key) < 0)...
а что бы не сделать так же, как в методе, где ищешь ближайший?
var cmpr = temp.Key.CompareTo(key);
@Артем, да, это ты верно подметил. Тут можно соптимизировать
ОтветитьУдалить