Структуры данных. Деревья - 30 стр.

UptoLike

Составители:

Рубрика:

Результат применения алгоритма Delete1 к дереву, изображенному на ри-

сунке 6 а), выглядит так, как показано на рисунке 6 в). Можно заметить, что при

использовании этого алгоритма дерево подвергается большей деформации, чем

при применении алгоритма Delete (см. рисунок 6 б) ).

Процедура Insert, используемая в Delete1, является универсальной и для

данного случая включения может быть упрощена, так как

известно, что правое

поддерево должно быть подсоединено к самой правой пустой ссылке. В этом

случае можно выполнить нерекурсивную реализацию процедуры включения в

дерево поиска:

procedure Insert1(T : Tree; p: Tree);

var s: Tree;

begin

s:=T; {по условию использования T<>nil}

while s^.R <> nil do

s:=s^.R;

s^.R:=p;

end; { Insert1 }

Упражнение 4.6. Описать процедуру исключения слова из частотного сло-

варя ( см. раздел 4.2 и пример 4.3 ).

5. СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ

Дерево называется

идеально сбалансированным, если число вершин

( узлов ) в его левых и правых поддеревьях отличается не более чем на единицу

( рисунок 7 ).