Упорядоченное дерево

Cтраница 1

Упорядоченное дерево - это дерево, у которого ребра ( ветви), исходящие из каждой вершины, упорядочены. Поэтому два упорядоченных дерева на рис. 4.18 - это разные, отличные друг от друга объекты. [1]

Упорядоченное дерево, каждый узел которого содержит 2 или 3 связи, а все листья расположены на одном уровне, называется ( 2 - 3) - деревом. Из определения следует, что узел ( 2 - 3) - дерева может содержать один или два ключа. [2]

Упорядоченное дерево может также интерпретироваться в виде так называемого уступчатого списка, который используется в оглавлениях. [3]

Упорядоченным деревом будем называть двоичное дерево, каждый элемент А которого может содержать на своей правой ветви элементы, у которых разность между значением их признака и значением признака элемента А неотрицательна, а на левой ветви - элементы, у которых разность между значением их признака и значением признака элемента А отрицательна. [4]

Упорядоченным деревом называется дерево, в котором множество сыновей каждого узла упорядочено. При изображении упорядоченного дерева мы будем считать, что множество сыновей каждого узла упорядочено слева направо. [5]

Представление упорядоченного дерева за счет поддержания связного списка дочерних узлов каждого узла эквивалентно представлению его в виде двоичного дерева. На схеме справа вверху показано представление в виде связного списка дочерних узлов для дерева, показанного слева вверху; при этом список реализован в правых связях узлов, а левая связь каждого узла указывает на первый узел в связном списке его дочерних узлов. На схеме справа внизу приведена несколько измененная версия верхней схемы; она представляет бинарное дерево, изображенное слева внизу. [6]

Частным случаем упорядоченного дерева является бинарное дерево. [7]

Нарисуйте три упорядоченных дерева, которые изоморфны по отношению к упорядоченному дереву, показанному на рис. 5.20. Другими словами, должна существовать возможность преобразования всех четырех деревьев одного в другое путем обмена дочерними узлами. [8]

ТП) образует упорядоченное дерево. [9]

Реализация процедуры построения упорядоченного дерева ТЬ ( Х U х) требует выполнения не более 0 ( log X) операций. [10]

Любая классификационная премируется некоторым упорядоченным деревом. [11]

Поскольку каждый узел в упорядоченном дереве может иметь любое количество связей, представляется естественным рассматривать его с использованием связного списка, а не массива, для хранения связей с дочерними узлами. Пример такого представления приведен на рис. 5.22. Из этого примера видно, что тогда каждый узел содержит две связи: одну для связного списка, соединяющего его с родственными узлами, и вторую для связного списка его дочерних узлов. [12]

На рис. 4 приведен пример упорядоченного дерева Хаффмена. [13]

На рис. 1.3 изображены два различных упорядоченных дерева. [14]

Деревья, построенные в различном порядке. [15]

Страницы: 1 2 3 4