Главная » Java, Структуры данных и алгоритмы » Векторная структура для бинарных деревьев

0

В основу простейшей структуры представления бинарного дерева Т положен принцип нумерации узлов дерева. Каждый узел v дерева Гполу- чает порядковый номер p{v) в виде целого числа, который определяется следующим образом:

•    если v является корнем Г, то p(v) = 1;

•    если v — левый дочерний элемент узла w, то p(v) = 2р(и)\

Рис. 6.18. Уровневая нумерация бинарного дерева: (а) принципиальная схема; (Ь) пример

(Ь)

Функция р уровневой нумерации предполагает представление бинарного дерева Тс помощью вектора Этаким образом, что узел v дерева Тсоответствует p(v)-My элементу вектора S (см. рис. 6.19). Традиционно вектор Sреализуется расширяемым массивом (см. п. 5.1.3). Подобная реализация достаточно проста и удобна, так как позволяет легко выполнять

•    если v — правый дочерний элемент узла и, то p(v) = 2р(и)+1.

Нумерационная функция р известна как уровневая нумерация (level numbering) узлов бинарного дерева Г, поскольку нумерует узлы на каждом уровне Тв возрастающем порядке слева направо, хотя иногда может пропускать некоторые номера (см. рис. 6.18).

(а)

методы root, parent, leftChild, rightChild, sibling, islnternal, isExternal и isRoot, пользуясь простыми арифметическими операциями над числами p(v), ассоциируемыми с узлом v, участвующим в операции. Это означает, что каждый позиционный объект v служит контейнером (wrapper) индекса p{v) в векторе S. Детали реализации оставлены для самостоятельной проработки в упражнении М-6.24.

Рис. 6.19. Представление бинарного дерева Т с помощью вектора S

Допустим, что п — количество узлов дерева Т, а рт — максимальное значение p(v) всех узлов дерева Т. Вектор S имеет размерность N = рт + 1, поскольку элемент с индексом 0 из S не ассоциируется ни с одним из узлов дерева Т. Кроме того, вектор S будет иметь некоторое количество пустых элементов, не соотносящихся с существующими узлами дерева Т. Такие пустые сегменты могут соответствовать пустым простым узлам и даже являться сегментами, в которые можно поместить потомков этих узлов. В действительности, в самом худшем случае, N = 2(/н1)/2, обоснование чему можно получить, выполнив упражнение М-6.20. В разделе 7.3 рассмотрен класс бинарных деревьев, называемый «пирамидой» (heap), для которого N = п + 1. Более того, если все простые узлы пусты, как в случае с реализацией упомянутой пирамиды, то имеется возможность сэкономить место и при этом избежать увеличения размера вектора ?при включении простых узлов, индекс которых следует после индекса последнего в ряду составного узла дерева. Однако имеются приложения,

для которых векторное представление бинарного дерева удобнее, несмотря на увеличение объема памяти, в худшем случае требуемое таким представлением,

В табл. 6.1 показано время выполнения методов бинарного дерева, реализованного с помощью вектора. В эту таблицу не включены методы обновления бинарного дерева; такие операции оставлены для рассмотрения в примере 3-6.18.

Операция

Время

positions, elements

i 0(1)

swapElements, replaceElement

0(1)

root, parent, children

0(1)

leftChild, rightChild, sibling

0(1)

islnternal, isExternal, isRoot

0(1)

Таблица 6.1. Время выполнения методов бинарного дерева Г, представленного вектором 5, где S реализован с помощью массива. Количество узлов в дереве равно л, размерность S равна N. Методы hasNext(), nextObject() и nextPosition() итераторов elements(), positions() и children(v) требуют 0(1) времени. Используемое пространство есть 0(ЛО, в худшем случае составляющее 0(2(/Ы)/2)

Л

Векторное представление бинарного дерева является быстрым и простым способом реализации АТД «дерево», но может быть недостаточно эффективным с точки зрения занимаемого места, если высота дерева слишком велика. Следующая структура представления бинарных деревьев не имеет такого недостатка.

.2. Связная структура бинарных деревьев

Естественным способом реализации бинарного дерева является использование связной структуры (linked structure). При таком подходе каждый узел v дерева Т представляется объектом со ссылками на элемент, хранящийся в v, и на позиционные объекты, ассоциируемые с дочерними и родительскими элементами узла v (см. рис. 6.20).

Изображение связной структуры данных для представления бинарного дерева дано и на рис. 6.21.

Если узел v является корнем дерева Г, то ссылкой на родительский узел будет null, а если v — простой (пустой) узел, то ссылками на дочерние элементы v также будет null. При необходимости изменить занимаемое пространство при пустых простых узлах все ссылки можно осуществить на простые узлы null. Более того, согласно принципам объектно-ориентированного программирования, можно воспользоваться специально

созданным вместо пустого простого узла объектом NULL_NODE, на который и должна указывать ссылка. Такой объект может реализовывать интерфейс Position. Конечно, при использовании указанных заглушек для простых узлов следует ожидать, что метод parent будет генерировать сообщение об ошибке при обращении к «заменителю» простого узла.

Рис. 6.20. Узел связной структуры данных для представления бинарного дерева

 

Рис. 6.21. Пример связной структуры данных д ля представления бинарного дерева

Класс BTNode (фрагмент кода 6.26) представляет узел v объектом, реализующим позицию АТД ги имеющим экземпляры переменных element, left, right и parent, которые ссылаются на элементы, хранимые в v, — соответственно левый дочерний элемент, правый дочерний элемент, родительский элемент узла v. Класс BTNode также имеет методы для возвращения и задания этих переменных.

Г* Узел бинарного дерева 7 public class BTIMode implements Position { private Object element; private BTNode left, right, parent; /** конструктор по умолчанию 7 public BTNode() { } /** конструктор с параметрами 7

public BTNode(Object о, BTNode u, BTNode v, BTNode w) { setElement(o); setParent(u); setLeft(v); setRight(w);

}

public Object element() { return element; } public void setElement(Object o) { element=o; } public BTNode getLeftQ { return left; } public void setLeft(BTNode v) { left=v; } public BTNode getRight() { return right; } public void setRight(BTNode v) { right=v; } public BTNode getParent() { return parent; } public void setParent(BTN;ode v); { parent=v; }

}

Фрагмент кода 6.26. Вспомогательный класс BTNode для реализации узлов бинарного дерева

Во фрагментах кода 6.27 и 6.28 показан класс LinkedBinaryTree, реализующий интерфейс BinaryTree (фрагмент кода 6.15) и использующий связную структуру данных. Этот класс хранит размер дерева и ссылку на объект BTNode, ассоциируемый внутренними переменными с корнем дерева. Кроме интерфейса BinaryTree, метод LinkedBinaryTree включает

еще и следующие методы обновления:

expandExternal(v): трансформирует v из простого узла в составной путем создания двух новых простых узлов в качестве левого и правого дочерних элементов v; ошибка возникает в случае, если v уже является составным. Input: позиция; Output: нет.

removeAboveExternal(w): удаляет простой узел w вместе с его родителем

v, замещая v потомком w (см. рис. 6.13); ошибка возникает, если w является составным узлом или корнем.

Input: позиция; Output: нет.

У класса LinkedBinaryTree имеется конструктор без аргументов, который возвращает бинарное дерево, состоящее из единственного узла. Взяв за основу такое дерево, можно построить любое бинарное дерево путем многократного применения метода expandExternal. И наоборот, любое бинарное дерево можно разобрать с помощью метода remove Above External, сведя размер дерева до единственного простого узла.

public class LinkedBinaryTree implements Binary Tree { private Position root; // ссылка на корень private int size; // количество узлов public LinkedBinaryTree() {

root == new BTNode(null,null,null,null); size = 1;

}

public int size() { return size; }

public boolean isEmptyO { return (size==0); }

public boolean islnternal(Position v) {

return (((BTNode) v).getLeft()!=null &.&. ((BTNode) v).getRight()!=null);

}

public boolean isExternal(Position v) {

return (((BTNode) v),getLeft()==null && ((BTNode) v).getRight()==null);

}

public boolean isRoot(Position v) { return (v==root()); }

public Position root() { return root; } public Positionlterator positions() {

Position[ ] positions = new Position [size()]; inorderPositions(root(), positions, 0); return new ArrayPositionlterator(positions);

}

public Position leftChild(Position v) { return ((BTNode) v).getLeft(); } public Position rightChild(Position v) { return ((BTNode) v).getRight(), } public Position sibling(Position v) { Position p = parent(v); Position Ic = leftChild(p); if (v == Ic)

return rightChild(p);

else

return Ic;

public Position parent(Position v) { return ((BTNode) v).getParent(); }

Фрагмент кода 6.27. Класс LinkedBinaryTree, реализующий интерфейс BinaryTree (продолжение — фрагмент кода 6.28)

public Object replaceElement(Position v, Object о) { Object temp = ((BTf^de) v).element(); ((BTNode) v).setElement(o); return temp;

}

public void swapElements(Position v, Position w) { Object temp = w.element(); ((BTNode) w).setElement(v.element()); ((BTNode) v).setElement(temp);

}

public void expandExternal(Position v) { if (isExternal(v)) {

. ((BTNode) v).setLeft(new BTNode(null,(BTNode) v, null, null)); ((BTNode) v).setRight(new BTNode(null,(BTNode) v, null, null)); size += 2;

}

}

public void removeAboveExternal(Position v) { if (isExternal(v)) {.

1 BTNode p = (BTNode) parent(v); BTNode s = (BTNode) sibling(v); if (isRoot(p)) { s.setParent(null); root = s;

}

else {

BTNode g = (BTNode) parent(p); if (p == leftChild(g))

g.setLeft(s); else

g.setRight(s); s.setParent(g);

}

size -=2; }

}

Фрагмент кода 6.28. Класс LinkedBinaryTree, реализующий интерфейс BinaryTree

Обратите внимание, что методы обновления expandExternal и remove- AboveExternal работают нормально только в случае, если простой узел представляет собой стандартный узел, то есть не является null или специально созданным объектом NULL_NODE. Альтернативные методы обновления бинарного дерева предложены читателю для решения в упражнении 3-6.7.

Другим примером использования метода expandExternal является «клонирование» бинарного дерева Тс целью получения его точной копии Т\ Эта операция выполняется рекурсивно, а за основу берется Т\ состоящее из одного простого узла v’. Для корня v дерева Г вызывается рекурсивный алгоритм, показанный во фрагменте кода 6.29, который клонирует ^посредством обратного прохода. В Java каждый объект, реализующий интерфейс java.lang.Cloneable, должен уметь дублировать себя с помощью метода clone(). Используемая по умолчанию реализация clone() просто копирует переменные экземпляра объекта (атрибуты). Таким образом, реализация алгоритма, подобная показанной во фрагменте кода 6.29, может использоваться для клонирования бинарного дерева.

Алгоритм clone(7n,r’,v,v’):

Input. бинарное дерево Г, содержащее узел v, и бинарное дерево Г’, содержащее простой узел v’.

Output: приращение дерева Г’таким образом, что ветвь, корнем которой является v’/становится точной копией ветви, корнем которой является v дерева Т.

TreplaceElement(\/’, i/.element()) if 7~.islnternal([16]/) then r.exspandExternal(i/) clone(T,T,r.leftChild(v), T.leftChild(i/)) clone(r,rfr.rightChild(i/), r.rightChild(v’)) -

Фрагмент кода 6.29. Алгоритм clone

Проанализируем время выполнения каждого метода класса LinkedBinaryTree, представленного с помощью связной структуры.

мой, обратный, симметричный), служит одной цели. Узлы, к которым выполняется обращение при проходе, сохраняются в массиве, а класс-адаптер ArrayPositionlterator генерирует итератор узлов. То же делает метод elements(). Следовательно, методы positions() и elements() выполняются за О(п) времени каждый.

• Класс-адаптер ArrayPositionlterator генерирует итераторы elements(), positions() и children(v), имеющие методы hasNext(), nextObject() и nextPosition(), выполняющиеся за 0(1) времени.

С учетом требуемого для такой структуры данных места отметим, что для каждого узла дерева Т существует объект класса BTNode (фрагмент кода 6.26). Таким образом, вся структура займет 0(п) места.

. В табл. 6.2 сведены данные о производительности такой реализации бинарного дерева.

Операции

Время

positions, elements

0(1)

swapElements, replaceElement

0(1)

root, parent, children

0(1)

leftChild, rightChild, sibling

0(1)

islnternal, isExternal, isRoot

0(1)

expandExternal, removeAboveExternal

0(1)

Таблица 6.2. Время выполнения методов бинарного дерева с количеством узлов л, реализованного с помощью связной структуры. Затраты памяти составляют 0(п)

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии