Структуры и алгоритмы обработки данных


Краткая теория


 

При обработке данных в ЭВМ важно знать и информационное поле элемента, и его размещение в памяти машины. Для этих целей используется сортировка. Итак, сортировка - это расположение данных в памяти в регулярном виде по их ключам. Регулярность рассматривают как возрастание значения ключа от начала к концу в массиве.

Различают следующие типы сортировок:

  • внутренняя сортировка - это сортировка, происходящая в оперативной памяти машины
  • внешняя сортировка - сортировка во внешней памяти.

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

 

 

Существует множество способов упорядочивания дерева. Рассмотрим один из них :

       " Левый " сын имеет ключ меньше, чем ключ " Отца "

       " Правый " сын имеет ключ больше, чем ключ " Отца "

Получили бинарное упорядоченное дерево с минимальным числом уровней.

Строго сбалансированное дерево : дерево, в котором левое и правое поддерево имеют  уровни , отличающиеся  не более, чем на единицу.

Рассмотрим принцип построения дерева при занесении элементов в массив :

Пусть в первоначально пустой массив заносятся последовательно поступающие элементы :  70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86 ; Т.к. это еще пустое дерево, то ссылки left и right равны  nil( left - указатель на левого сына (элемент), right - указатель на правого сына (элемент)).

Четвертый из поступающих элементов 87. Т.к. этот ключ больше ключа 70 ( корень ), то новая вершина должна размещаться на правой ветви дерева. Чтобы определить ее место, спускаемся по правой стрелке к очередной вершине ( с ключом 85 ), и если поступивший ключ больше 85, то новую вершину делаем правым сыном вершины с ключом 85 .

 

 

В рассмотренном примере ПРИНЦИП ПОСТРОЕНИЯ ДЕРЕВА имеет следующий вид : если поступает очередной элемент массива, то начиная с корня дерева (в зависимости от сравнения текущего элемента с очередной вершиной) идем влево или вправо от нее до тех пор, пока не найдем подходящую вершину, к которой можно подключить новую вершину с текущим ключом. В зависимости от результата сравнения ключей, новую вершину делаем левой или правой для найденной вершины.

 

 




- Начало -  - Назад -  - Вперед -



Книжный магазин