C++ : Алгоритмы - Бинарное дерево поиска. Часть IV

Четвертая часть статьи про реализацию Бинарных деревьев на С++.

Реализовывать будем Обходы дерева. 

Обход бинарного дерева предполагает посещение всех элементов дерева, при этом каждая вершина посещается только один раз. Существует три вида таких обходов, каждый из которых мы будем реализовывать рекурсивно.

1) Прямой порядок (англ. preorder)

        Посетить корень, посетить левое поддерево, посетить правое поддерево.

C++ : Алгоритмы - Бинарное дерево поиска. Часть III

Продолжение статьи про бинарные деревья...Уже третья часть...

На повестке дня - 2 вида поиска в бинарном дереве. Точнее, вид один, но видов возращаемых значений 2 - это true/false и pointer, то есть указатель на элемент в дереве.

Использовать будем конечно шаблоны и рекурсию. Ниже листинги этих четырёх (2 основных и две, которые вызываются рекурсивно) функций.

Возращает  булевское значение :
bool FindReturnBool(const TypeOfTree& dataToInsert);
//Вспомагательная функция для поиска елемента(true/false)
bool _FindReturnBool(BinaryTree<TypeOfTree>* element,const TypeOfTree& dataToInsert);     

C++ : Алгоритмы - Бинарное дерево поиска. Часть II

Итак, продолжим..

Вторая статья про Бинарные деревья поиска. Будем реализовывать метод для вставки элементов в дерево, то есть, создание самого дерева.

Чуть-чуть за саму вставку. Деревья - это не списки, хотя чуть похожи. Поэтому и вставка будет кардинально отличатся от добавления элемента в простой список.

Добавление первого элемента в дерево простое. При добавлении же второго элемента мы должны посмотреть на значение корня: если же добавляемое значение меньше, чем значение корня, то добавляем вставляемый элемент в левое поддерево(то есть присваиваем левому указателю корня новый обьект структуры). Если же второй вставляемый элемент больше, чем значение корня, то добавляем узел в правое поддерево.

C++ : Алгоритмы - Бинарное дерево поиска. Часть I

Наконец-то у меня появилось время, чтобы продолжить заниматься своим блогом. На сей раз я представлю вам цикл статей, в котором буде повествоваться про одну из самых известных, ну и, я так думаю, самую простую структуру "из самых сложных" - Бинарное дерево поиска.

Деревья - это вообще интересная вещь. Если рассмотреть уже построеное дерево, то оно реально оправдывает свое название - оно реально похоже на дерево...только перевёрнутое=). Но это не мешает ему иметь корень - самую верхнюю вершину, с которой и начинается все дерево, листья - это самые  нижние вершины. Так же можно увидеть сходство и генеалогическим деревом - в нем есть родители, дети, братья etc..

С++: Внешняя сортировка на 3х лентах

Приступим. Закончив с рассмотрением основных внутренних алгоритмов сортировки, приступим к рассмотрению внешних алгоритмов. Одним из таких есть внешняя сортировка на 3 лентах или простое слияние

Прямое слияние

Слияние означает объединение двух (или более) последовательностей в одну-единственную упорядоченную последовательность с помощью повторяющегося выбора из доступных в данный момент элементов. Слияние намного проще сортировки, и его используют как вспомогательную операцию в более сложных процессах сортировки последовательностей. Одна из сортировок на основе слияния называется простым слиянием. Она выполняется следующим образом:

C++ : Алгоритмы сортировок[2]

Продолжение предыдущей статьи...

Рекурсивные алгоритмы и улучшение известных нам из предыдущей статьи.

 Быстрая сортировка

Теперь коснемся третьего улучшения метода, основанного на обмене. Если учесть, что пузырьковая сортировка в среднем была самой неэффективной из всех трех алгоритмов прямой сортировки, то следует ожидать относительно существенного улучшения. Оно, оказывается, приводит к самому лучшему из известных в данный момент методу сортировки для массивов. Его изобретатель Ч. Хоар назвал метод быстрой сортировкой (QuickSort).

Алгоритм. Выберем наугад какой-либо элемент (назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент  , затем будем просматривать массив справа, пока не встретим  . Теперь Поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена , пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) x, и правую – с ключами больше (или равными) x.

C++ : Алгоритмы сортировок

Для начала немного теории:

Сортировка – это упорядочение данных по некоторому признаку.

Все методы сортировки разбиты на два класса – сортировку массивов и сортировку файлов (последовательностей). Их называют соответственно внутренней и внешней сортировкой, поскольку массивы хранятся в быстрой оперативной внутренней памяти машины со случайным доступом, а файлы обычно размещаются в более медленной, но более емкой внешней памяти (на носителях). При рассмотрении элементов значение каждого будем называть ключом (key) элемента.

Сейчас мы будем говорить про сортировку массивов, то есть про Внутреннюю сортировку данных.

Сортировка массивов

Пусть задан массив с элементами a1, a2, .......an, которые нужно расположить в возрастающем порядке.