В информатике такой подход получил название «двоичный поиск». Если сравнивать её с последовательным поиском, разница может оказаться существенной. Однако при представлении данных в виде массива эффективность двоичного поиска снижается за счет сложности переноса данных в нем для сохранения упорядоченности. Представление упорядоченных данных в виде двоичного дерева помогает решить эту проблему. Например, удаление отдельных элементов обеспечивает большую гибкость: затраты на вставку для выделения пространства и загрузки полей со значениями, А также на удаление для возврата пространства не зависят от количества n элементов.
Двоичное дерево поиска также применяется для построения более абстрактных структур, таких, как множества, мультимножества, ассоциативные массивы.
Список литературы
1. Симонова, Е. В. Структуры данных в C#: линейные и нелинейные динамические структуры : учебное пособие / Е. В. Симонова. -- Санкт-Петербург : Лань, 2018. -- 152 с.
2. Папшев, С. В. Дискретная математика. Курс лекций для студентов естественнонаучных направлений подготовки : учебное пособие / С. В. Папшев. -- Санкт-Петербург : Лань, 2019. -- 192 с.
3. Асанов, М. О. Дискретная математика: графы, матроиды, алгоритмы : учебное пособие / М. О. Асанов, В. А. Баранский, В. В. Расин. -- 3-е изд., стер. -- Санкт-Петербург : Лань, 2020. -- 364 с.
4. Тюкачев, Н. А. C#. Алгоритмы и структуры данных : учебное пособие / Н. А. Тюкачев, В. Г. Хлебостроев. -- 3-е изд., стер. -- Санкт-Петербург : Лань, 2018. -- 232 с.
5. Mehlhorn, K. Datenstrukturen und effiziente Algorithmen - Band 1: Sortieren und Suchen / K. Mehlhorn. - Stuttgart Teubner, 1988. - 317 s.
Приложение А
Листинг класса BinaryTree
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TreeModeler
{
public class BinaryTree
{
public BinaryTreeNode Root { get; set; }
public int Height { get; set; }
public BinaryTreeNode Add(int data)
{
BinaryTreeNode node;
if (Root == null)
{
Root = new BinaryTreeNode(data, null);
return Root;
}
else
{
BinaryTreeNode current = Root;
while (true)
{
if (data < current.Data)
{
if (current.LeftChild != null)
{
current = current.LeftChild;
continue;
}
else
{
node = new BinaryTreeNode(data, current);
current.LeftChild = node;
return node;
}
}
else
{
if (current.RightChild != null)
{
current = current.RightChild;
continue;
}
else
{
node = new BinaryTreeNode(data, current);
current.RightChild = node;
return node;
}
}
}
}
}
public BinaryTreeNode Find(int data)
{
BinaryTreeNode result = null;
if (Root == null)
{
return null;
}
BinaryTreeNode current = Root;
while (true)
{
if (data == current.Data)
{
result = current;
break;
}
if (data < current.Data)
{
if (current.LeftChild != null)
{
current = current.LeftChild;
continue;
}
break;
}
if (data > current.Data)
{
if (current.RightChild != null)
{
current = current.RightChild;
continue;
}
break;
}
}
return result;
}
public void Remove(int data)
{
BinaryTreeNode node = Find(data);
if (node == null)
return;
if (node.IsLeaf)
RemoveLeaf(node);
else if (node.RightChild != null && node.LeftChild == null)
RemoveNodeWithRightChild(node);
else if (node.RightChild == null && node.LeftChild != null)
RemoveNodeWithLeftChild(node);
else
RemoveNodeWithTwoChildren(node);
}
public void RemoveLeaf(BinaryTreeNode node)
{
if (node == Root)
Root = null;
else if (node.IsLeftChild)
node.Parent.LeftChild = null;
else
node.Parent.RightChild = null;
node.Parent = null;
}
public void RemoveNodeWithRightChild(BinaryTreeNode node)
{
if (node == Root)
Root = node.RightChild;
else if (node.IsLeftChild)
node.Parent.LeftChild = node.RightChild;
else
node.Parent.RightChild = node.RightChild;
node.RightChild.Parent = node?.Parent;
node.Parent = null;
node.RightChild = null;
}
public void RemoveNodeWithLeftChild(BinaryTreeNode node)
{
if (node == Root)
Root = node.LeftChild;
else if (node.IsLeftChild)
node.Parent.LeftChild = node.LeftChild;
else
node.Parent.RightChild = node.LeftChild;
node.LeftChild.Parent = node?.Parent;
node.Parent = null;
node.LeftChild = null;
}
public void RemoveNodeWithTwoChildren(BinaryTreeNode node)
{
BinaryTreeNode rightMin = node.RightChild;
while (rightMin.LeftChild != null)
rightMin = rightMin.LeftChild;
if (rightMin.RightChild == null)
{
RemoveLeaf(rightMin);
}
else
{
RemoveNodeWithRightChild(rightMin);
}
if (node == Root)
{
Root = rightMin;
Root.LeftChild = node.LeftChild;
Root.RightChild = node.RightChild;
}
else
{
if (node.IsLeftChild)
node.Parent.LeftChild = rightMin;
else
node.Parent.RightChild = rightMin;
rightMin.LeftChild = node.LeftChild;
rightMin.RightChild = node.RightChild;
rightMin.Parent = node.Parent;
}
if (rightMin.RightChild != null)
rightMin.RightChild.Parent = rightMin;
rightMin.LeftChild.Parent = rightMin;
node.Parent = null;
node.LeftChild = null;
node.RightChild = null;
}
public int GetHeight(BinaryTreeNode node)
{
if (node == null)
return 0;
else
{
return 1 +
Math.Max(GetHeight(node.LeftChild), GetHeight(node.RightChild));
}
}
}
}
Приложение Б
Листинг класса GeneralTree
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TreeModeler
{
public class GeneralTree
{
public GeneralTreeNode Root { get; set; }
public void Add(int data, GeneralTreeNode selected)
{
GeneralTreeNode node;
if (selected == null)
{
if (Root == null)
{
node = new GeneralTreeNode(data, null);
Root = node;
}
}
else
{
node = new GeneralTreeNode(data, selected);
selected.Children.Add(node);
}
}
public GeneralTreeNode Find(int data, GeneralTreeNode node)