4.3.7 Сортировка и поиск с помощью двоичного дерева
Двоичные деревья чаще всего применяются для сортировки и поиска. Пусть для определенности сортируется массив, состоящий из целых чисел. Для этого сначала строится двоичное дерево по следующему алгоритму: в качестве корня двоичного дерева берется первый элемент массива. Следующие элемен- ты массива становятся либо левыми, либо правыми потомками в зависимости от значения элемента. Если следующий элемент меньше корня, то он вставля- ется в левое поддерево, если больше корня, то в правое поддерево, причем вставляется в нужное место в зависимости от значения текущего элемента. По- сле построения двоичного дерева осуществляется его обход слева. Легко ви- деть, что если двоичное дерево построено так, как описано выше, то при его обходе слева мы получим упорядоченный по возрастанию массив. Такие двоичные деревья называются двоичными деревьями поиска или де- ревья бинарного поиска ( binary search tree ), поскольку при поиске ис- пользуется упорядоченность двоичного дерева. Поиск происходит следующим
Глава 4 Типовые алгоритмы обработки информации ____________________________________________________________________ образом. В качестве текущего узла принимаем корень. Затем сравниваем значе- ние искомого элемента со значением текущего узла. Если они равны, то тре- буемый элемент найден и алгоритм заканчивает свою работу. В противном слу- чае, если искомый элемент меньше значения текущего узла, то текущим делаем левое поддерево, если больше, то текущим становится правое поддерево. Снова сравниваем наш элемент с текущим узлом и так далее до тех пор, пока искомый элемент не будет найден, либо не будет достигнут пустой узел, что будет озна- чать, что искомого элемента в массиве нет. Выше мы уже отмечали, что деревья обычно не вводятся, а формируются программно. Напишем процедуру формирования двоичного дерева по заданно- му массиву целых чисел: procedure insert_node(Elem: integer; var root: PTree); var p: ^Tree; // текущий узел newTree: ^Tree; // новый узел begin p:= root; // начинаем с корня и проходим до нужного узла while (Elem > p^.node) and (p^.right <> nil) or (Elem < p^.node) and (p^.left <>nil) do if Elem < p^.node then p:= p^.left else p:= p^.right; New(newTree); < Создание нового узла >newTree^.left:= nil; newTree^.right:= nil; newTree^.node:= Elem; < В зависимости от значения Elem новый
4.3 Динамические структуры данных ____________________________________________________________________ узел добавляется либо справа, либо слева > if Elem > p^.node then p^.right:= newTree else p^.left:= newTree; end; Процедуру поиска мы уже разрабатывали в последнем примере предыду- щего раздела. На этот раз оформим поиск в виде функции: function Search_Elem(Elem: integer; var root: PTree): boolean; var p: PTree; begin Search_Elem:= false; if root = nil then exit; p:= root; if p^.node = Elem then Search_Elem:= true // элемент найден else if Elem < p^.node then Search_Elem:= Search_Elem(Elem, p^.left) else Search_Elem:= Search_Elem(Elem, p^.right); end; Теперь давайте напишем программу сортировки массива целых чисел по возрастанию и поиска в дереве бинарного поиска нужного элемента. Все нуж-
Глава 4 Типовые алгоритмы обработки информации ____________________________________________________________________ ные процедуры у нас уже имеются. program in_order; uses CRT, FileUtil; type
| vector = array | of integer; |
| PTree= ^Tree; | // Указатель на дерево |
| Tree= record | // Само дерево, имеет тип — запись |
| node: integer; | // значение вершины (узла) дерева |
left: PTree; // Ссылка на левое поддерево right: PTree; // Ссылка на правое поддерево end; var i, n, choose: integer; Elem: integer; sorted_array: vector; // сортируемый массив root: PTree; < Процедура обхода двоичного дерева слева >procedure obhod(p: PTree); begin if p <> nil then begin obhod(p^.left); write(p^.node, ‘ ‘); obhod(p^.right); end; end;
4.3 Динамические структуры данных ____________________________________________________________________ < Процедура поиска узла для вставки нового узла >procedure insert_node(Elem: integer; var root: PTree); var p: ^Tree; // текущий узел newTree: ^Tree; // новый узел begin p:= root; // начинаем с корня и проходим до нужного узла while (Elem > p^.node) and (p^.right <> nil) or (Elem < p^.node) and (p^.left <>nil) do if Elem < p^.node then p:= p^.left else p:= p^.right; < Создание нового узла >New(newTree); newTree^.left:= nil; newTree^.right:= nil; newTree^.node:= Elem; < В зависимости от значения Elem новый узел добавляется либо справа, либо слева >if Elem > p^.node then p^.right:= newTree else p^.left:= newTree; end; < ========= Сортировка двоичным деревом поиска ======== >procedure Tree_Sort(var sorted_array: vector); var Elem: integer;
Глава 4 Типовые алгоритмы обработки информации ____________________________________________________________________ begin Elem:= sorted_array[0]; New(root); root^.left:= nil; root^.right:= nil; root^.node:= Elem; for i:= 1 to High(sorted_array) do begin Elem:= sorted_array[i]; insert_node(Elem, root); end; obhod(root); // Обход полученного дерева слева end; < Функция поиска в бинарном дереве >function Search_Elem(Elem: integer; var root: PTree): boolean; var p: PTree; begin Search_Elem:= false; if root = nil then exit; p:= root; if p^.node = Elem then Search_Elem:= true // элемент найден else if Elem < p^.node then Search_Elem:= Search_Elem(Elem, p^.left) else
4.3 Динамические структуры данных ____________________________________________________________________ Search_Elem:= Search_Elem(Elem, p^.right); end; begin writeln(UTF8ToConsole(‘ Введите количество элементов массива ‘)); readln(n); SetLength(sorted_array, n); writeln(UTF8ToConsole(‘ Введите элементы массива ‘)); for i:= 0 to n — 1 do read(sorted_array[i]); repeat writeln(UTF8ToConsole(‘ Выберите нужное действие: ‘)); writeln(UTF8ToConsole(‘ 1-сортировка массива ‘)); writeln(UTF8ToConsole(‘ 2-поиск элемента массива ‘)); writeln(UTF8ToConsole(‘ 3-выход из программы ‘)); readln(choose); case choose of 1: begin < Сортировка > < Вызов процедуры сортировки массива бинарным деревом поиска >Tree_Sort(sorted_array); writeln; end; 2: begin < поиск >writeln(UTF8ToConsole(‘ введите искомый элемент ‘)); readln(Elem); if Search_Elem(Elem, root) then writeln(UTF8ToConsole(‘ Элемент найден ‘)) else writeln(UTF8ToConsole(‘ Элемент не найден ‘)); end;
Глава 4 Типовые алгоритмы обработки информации ____________________________________________________________________ end; < end of case >until choose = 3; end. При работе с программой обратите внимание на то, что, прежде чем вызы- вать функцию поиска, необходимо отсортировать массив, т.е. построить соот- ветствующее двоичное дерево.
Источник
Сортировка с помощью дерева
Сортировка с помощью дерева осуществляется на основе бинарного дерева поиска.
Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
- оба поддерева – левое и правое, являются двоичными деревьями поиска;
- у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X;
- у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X.
Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
Для сортировки с помощью дерева исходная сортируемая последовательность представляется в виде структуры данных «дерево».
Например, исходная последовательность имеет вид:
4, 3, 5, 1, 7, 8, 6, 2
Корнем дерева будет начальный элемент последовательности. Далее все элементы, меньшие корневого, располагаются в левом поддереве, все элементы, большие корневого, располагаются в правом поддереве. Причем это правило должно соблюдаться на каждом уровне.
После того, как все элементы размещены в структуре «дерево», необходимо вывести их, используя инфиксную форму обхода.
Реализация сортировки с помощью дерева на C++
#include
using namespace std;
// Структура — узел дерева
struct tnode
int field; // поле данных
struct tnode *left; // левый потомок
struct tnode *right; // правый потомок
>;
// Вывод узлов дерева (обход в инфиксной форме)
void treeprint(tnode *tree)
if (tree != NULL ) < //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция вывода левого поддерева
cout field treeprint(tree->right); //Рекурсивная функция вывода правого поддерева
>
>
// Добавление узлов в дерево
struct tnode * addnode( int x, tnode *tree) if (tree == NULL ) // Если дерева нет, то формируем корень
tree = new tnode; //память под узел
tree->field = x; //поле данных
tree->left = NULL ;
tree->right = NULL ; //ветви инициализируем пустотой
>
else // иначе
if (x < tree->field) //Если элемент x меньше корневого, уходим влево
tree->left = addnode(x, tree->left); //Рекурсивно добавляем элемент
else //иначе уходим вправо
tree->right = addnode(x, tree->right); //Рекурсивно добавляем элемент
return (tree);
>
//Освобождение памяти дерева
void freemem(tnode *tree)
if (tree != NULL ) // если дерево не пустое
freemem(tree->left); // рекурсивно удаляем левую ветку
freemem(tree->right); // рекурсивно удаляем правую ветку
delete tree; // удаляем корень
>
>
// Тестирование работы
int main()
struct tnode *root = 0; // Объявляем структуру дерева
system( «chcp 1251» ); // переходим на русский язык в консоли
system( «cls» );
int a; // текущее значение узла
// В цикле вводим 8 узлов дерева
for ( int i = 0; i < 8; i++)
cout cin >> a;
root = addnode(a, root); // размещаем введенный узел на дереве
>
treeprint(root); // выводим элементы дерева, получаем отсортированный массив
freemem(root); // удаляем выделенную память
cin.get(); cin.get();
return 0;
>
Результат выполнения
Комментариев к записи: 3
Источник
Сортировка бинарным деревом
Сортировка бинарным деревом (Tree sort) – алгоритм сортировки, который заключается в построении двоичного дерева поиска по ключам массива, с последующим построением результирующего массива упорядоченных элементов путем обхода дерева.
Принцип работы алгоритма сортировки бинарным деревом
- Элементы неотсортированного массива данных добавляются в двоичное дерево поиска;
- Для получения отсортированного массива, производится обход бинарного дерева с переносом данных из дерева в результирующий массив.
Реализация алгоритма сортировки бинарным деревом
using System; using System.Collections.Generic; namespace TreeSortApp < //простая реализация бинарного дерева public class TreeNode < public TreeNode(int data) < Data = data; >//данные public int Data < get; set; > //левая ветка дерева public TreeNode Left < get; set; > //правая ветка дерева public TreeNode Right < get; set; > //рекурсивное добавление узла в дерево public void Insert(TreeNode node) < if (node.Data < Data) < if (Left == null) < Left = node; >else < Left.Insert(node); >> else < if (Right == null) < Right = node; >else < Right.Insert(node); >> > //преобразование дерева в отсортированный массив public int[] Transform(Listint> elements = null) < if (elements == null) < elements = new Listint>(); > if (Left != null) < Left.Transform(elements); >elements.Add(Data); if (Right != null) < Right.Transform(elements); >return elements.ToArray(); > > class Program < //метод для сортировки с помощью двоичного дерева private static int[] TreeSort(int[] array) < var treeNode = new TreeNode(array[0]); for (int i = 1; i < array.Length; i++) < treeNode.Insert(new TreeNode(array[i])); > return treeNode.Transform(); > static void Main(string[] args) < Console.Write("n hljs-keyword">var n = int.Parse(Console.ReadLine()); var a = new int[n]; var random = new Random(); for (int i = 0; i < a.Length; i++) < a[i] = random.Next(0, 100); > Console.WriteLine("Random Array: ", string.Join(" ", a)); Console.WriteLine("Sorted Array: ", string.Join(" ", TreeSort(a))); > > > Источник
2 Алгоритм бинарного дерева
Сортировка с помощью бинарного дерева — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения с потока (например, с файла, сокета или консоли) [6].
Реализация алгоритма бинарного дерева на языке С#:
public TreeItem LeftChild;
public TreeItem RightChild;
TreeItem top; int n = 0;
private void Add(int a)
TreeItem temp = new TreeItem();
private void Build(TreeItem t)
public void Sort(int[] mas)
>
Рисунок 3 – Реализация программы, которая сортирует по возрастанию массив из 3000 элементов методом бинарного дерева за 4 миллисекунды.
Рисунок 4 – Реализация программы, которая сортирует по убыванию массив из 3000 элементов методом бинарного дерева за 4 миллисекунды.
3 Быстрая сортировка
Основная стратегия ускорения алгоритмов сортировка — обмены между как можно более дальними элементами исходного файла — в методе быстрой сортировки реализована за счет того, что один из ключей в исходном файле используется для разделения его на два подфайла так, чтобы слева от выбранного элемента находились только элементы с меньшими ключами, а справа — только с большими. Элемент, разделяющий файл, помещается между его двумя подфайлами и процедура выполняется рекурсивно для каждой половины до тех пор, пока в очередном новом подфайле не окажется меньше, чем М элементов, где М — заранее выбранное число.
Сортировка подфайлов, содержащих меньше чем М элементов, выполняется каким-либо простым методом, например, простыми вставками. Таким образом, реализация метода зависит от двух параметров: значения М и способа выбора элемента, который предназначен для разделения файла на две части.
Блок выбора Х в простейшем случае формулируется как X=K[l], однако это может привести к крайне неэффективному алгоритму. Наиболее простое лучшее решение — выбирать Х как случайный ключ из диапазона K[l] . K[r] и обменять его с K[l] [4].
Реализация алгоритма быстрой сортировки на языке С#:
public void sorting(int[] mas, long first, long last)
int p = mas[(last — first) / 2 + first];
long i = first, j = last;
Источник