4-дерево

Cтраница 3

Поэтому представление 4-дерева с использованием древовидной структуры имеет недостаток, заключающийся в требовании большого объема памяти. Линейное 4-дерево кодирует совокупность вершин черных листьев, используя только код положения. [31]

Хотя списки пропусков легко обобщить в качестве систематического способа быстрого перемещения по связному списку, важно понимать, что лежащая в основе структура данных - всего лишь альтернативное представление сбалансированного дерева. Например, на рис. 13.27 приведено представление сбалансированного 2 - 3 - 4-дерева из рис. 13.10 в виде списка пропусков. [32]

Результирующее 4-дерево называют / ( - деревом квадрантов, поскольку всего 16 примитивных визуальных образов использованы вместо двух примитивных визуальных образов в исходном представлении в виде 4-дерева. Очевидно, что / ( - дерево квадрантов имеет меньше вершин, чем исходное 4-дерево, и операции соответственно ускоряются. [33]

Добавление биномиальной очереди из 3 узлов к биномиальной очереди из 7узлов имеет своим результатом очередь из 10 узлов как результат выполнения процесса, который моделирует операцию сложения 0112 111210102 двоичной арифметики. Последующее сложение трех 2-деревьев оставляет одно из них в итоговой очереди, а в перенос попадает 4-дерево, содержащее узлы TNEI. Это 4-дерево складывается с другим 4-деревом, образуя биномиальную очередь, показанную в нижней части диаграммы. Процесс охватывает небольшое количество узлов. [34]

Использование двух типов связей обеспечивает эффективный способ представления 3-узлов и 4-узлов в 2 - 3 - 4-деревьях. R-связи ( жирные линии на схемах) используются для представления внутренних соединений в узлах, а В-связи ( тонкие линии на схемах) - для представления связей 2 - 3 - 4-дерева. Оба представления имеют три ключа и четыре В-связи. Оба представления имеют два ключа и три В-связи. [35]

Бинарные изображения для упр. 3. [36]

Я - число черных вершин, которые представляют однородные черные области, И - число белых вершин, которые представляют однородные белые области, а С - число серых вершин, являющихся внутренними вершинами 4-дерева. [37]

Основная идея заключается в представлении 2 - 3 - 4-деревьев в виде стандартных BST-деревьев ( содержащих только 2-узлы), но с добавлением к каждому узлу дополнительного информационного разряда для кодирования 3-узлов и 4-узлов. Мы будем представлять связи двумя различными типам связей: красными ( red) связями ( R-связями), которые объединяют воедино небольшие бинарные деревья, образующие 3-узлы и 4-узлы, и черными ( black) связями ( В-связями), которые объединяют воедино 2 - 3 - 4-дерево. [38]

Операция пересечения двух областей объектов по существу не отличается от операции объединения, за исключением того, что в область результата помещаются меньшие, а не большие блоки. Стоит отметить, что пространственные отношения между блоками двух областей, представленных линейными 4-деревьями, могут быть только отношениями включает, совпадают и рядом, если двоичные изображения имеют одинаковые размеры. Это свойство 4-дерева делает простыми операции на множествах. [40]

В частности, для вставки нового элемента в биномиальную очередь мы превращаем новый элемент в 1-узловое сортирующее дерево. Далее, если N есть четное число ( значение самого правого разряда равно 0), мы просто помещаем это сортирующее дерево в самую правую пустую позицию биномиальной очереди. Если N - нечетное число ( значение самого правого разряда составляет 1), мы объединяем сортирующее 1-дерево, соответствующее новому элементу, с сортирующим 1-деревом в самой крайней правой позиции биномиальной очереди, в результате чего получаем сортирующее 2-дерево переноса. Если позиция, соответствующая 2 в биномиальной очереди, пуста, то сортирующее дерево переноса помещается в эту позицию, в противном случае производится слияние сортирующего 2-дерева переноса с сортирующим 2 деревом из биномиальной очереди, образуя при этом 4-дерево переноса, и так продолжая процесс до тех пор, пока не будет достигнута пустая позиция в биномиальной очереди. Этот процесс демонстрируется на рис. 9.17, а в программе 9.14 приведена его реализация. [42]

Предположим, что мы интересуемся только цифровыми картинами на двумерной сетке. Каждое разбиение порождает четыре квадранта одинаковых размеров. Мы помечаем квадрант белым, если он состоит только из белых пикселов, черным, если он состоит только из черных пикселов, и серым, если он состоит из белых и черных пикселов. Дальнейшее разбиение переносится на серые блоки. Белые и черные блоки остаются без изменений. Процесс разбиения лучше всего описать с помощью 4-дерева, в котором корень представляет исходное изображение, и листья-черные или белые квадранты. Поэтому 4-дерево может представить визуальные данные в более компактном виде, по сравнению с растровой структурой данных. [43]

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