Сортировка частично упорядоченным деревом.



Сортировка частично упорядоченным деревом.

В двоичном дереве, которое строится в этом методе сортировки для каждого узла справедливо следующее утверждение: значения ключа, записанное в узле, меньше, чем ключи его потомков. Для полностью упорядоченного дерева имеются требования к соотношению между ключами потомков. Для данного дерева таких требований нет, поэтому такое дерево и называется частично упорядоченным. Кроме того, наше дерево должно быть абсолютно сбалансированным. Это означает не только то, что длины путей к любым двум листьям различаются не более, чем на 1, но и то, что при добавлении нового элемента в дерево предпочтение всегда отдается левой ветви/подветви, пока это не нарушает сбалансированность. Более подробно деревья рассматриваются в гл.6.

Например, последовательность чисел:

3 20 12 58 35 30 32 28

будет представлена в виде дерева, показанного на рис.3.15 .



Содержание раздела