Главная » Java, Структуры данных и алгоритмы » Реализация AVL-дерева на Java

0

Теперь перейдем к деталям реализации и проанализируем использование AVL-дерева Теп составными узлами для реализации упорядоченного словаря из п объектов. Алгоритмы ввода и удаления для Т требуют

 

Рис. 9.11. Удаление элемента с ключом 32 из AVL-дерева (рис. 9.8): (а) после удаления узла с ключом 32 корень не сбалансирован; (Ь) разовая ротация восстанавливает свойство сбалансированности

выполнения трехузловых реструктуризации и определения разности высот двух соседних узлов. Что касается реструктуризации, то необходимо расширить набор операций АТД «бинарное дерево», добавив метод restructure. Несложно заметить, что операция restructure может выполняться за 0(1) времени, если Г реализовано связной структурой (п. 6.4.2), чего нельзя достичь при векторной реализации (п. 6.4.1). Таким образом, для представления AVL-дерева предпочтительнее связная структура.

Если же говорить о высоте, то можно явным образом сохранить высоту каждого составного узла v в самом узле. Или же возможно сохранить коэффициент сбалансированности (balance factor) узла v непосредственно в нем, при этом коэффициент определяется как разность высот левого и правого дочерних элементов. Таким образом, коэффициент сбалансированности узла v всегда равен -1,0 или 1, за исключением случая ввода или удалений, когда он временно может стать равным -2 или +2. При вводе или удалении высоты и коэффициенты сбалансированности 0(log п) узлов могут изменяться и восстанавливаться за время 0(log п).

Во фрагментах кода 9.7—9.9 приводится Java-реализация словаря, выполненного с помощью AVL-дерева. Класс AVLItem, приведенный фрагментом кода 9.7, расширяет класс Item, используемый для представления объекта «ключ-элемент» бинарного поискового дерева. Он определяет дополнительную переменную экземпляра height, представляющую высоту узла. Класс AVLTree, полностью показанный во фрагментах кода 9.8 и 9.9, расширяет BinarySearchTree (фрагменты кода 9.3—9.5). Конструктор из AVLTree вначале вызывает конструктор суперкласса, а затем объявляет Т экземпляром класса ResrtructurableNodeBinaryTree, реализующим АТД «бинарное дерево», и дополнительно поддерживает метод restructure для выполнения трехузловых реструктуризаций (детали оставлены для упражнения С-9.3). Класс AVLTree наследует методы size, isEmpty, findElement, findAIIEIements и removeAIIEIements от своего суперкласса BinarySearchTree, но переопределяет методы insertltem и removeElement.

Метод insertltem (фрагмент кода 9.9) начинается вызовом метода insertltem своего суперкласса, с помощью которого вводит новый объект и прописывает позицию ввода (узел, содержащий ключ 54, на рис. 9.9) в переменной экземпляра actionPos. Вспомогательный метод rebalance используется для прохода пути с места ввода до корня, во время которого обновляются высоты всех пройденных узлов и проводятся, где следует, трехузловые реструктуризации. Точно так же метод removeElement (фрагмент кода 9.9) начинается вызовом метода суперкласса removeElement, который удаляет объект и помещает позицию, замещающую удаленную, в переменную экземпляра actionPos. После чего вспомогательный метод rebalance проходит путь от места удаления до корня.

public class AVLItem extends Item { int height;

AVLItem(Object k, Object e, int h) { super(k, e); height = h;

}

public int heightQ { return height; } public int setHeight(int h) { int oldHeight = height; height = h; return oldHeight;

}

}

Фрагмент кода 9.7. Класс, реализующий узел AVL-дерева. Высота узла дерева хранится в виде переменной экземпляра

/** Реализация словаря с помощью AVL-дерева. */ public class AVLTree extends BinarySearchTree implements Dictionary { public AVLTree(Comparator c) { super(c);

T = new RestructurableNodeBinaryTree();

}

private int height(Position p) { if (T.isExternal(p))

return 0; else

return ((AVLItem) p.element()).height();

}

private void setHeight(Position p) { // вызывается, если p составной ((AVLItem) p.element()).setHeight(1+Math.max(height(T.leftChild(p)),

height(T.rightChild(p))));

}

private boolean isBalanced(Position p) {

// проверяет, находится ли коэффициент сбалансированности р // в пределах -1 и 1

int bf = height(T.leftChild(p)) – height(T.rightChild(p)); return ((-1 <= bf) && (bf <= 1));

}

private Position tallerChild(Position p) {

// возвращает дочерний элемент p с высотой, большей или равной // высоте остальных дочерних элементов if (height(T.leftChild(p)) >= height(T.rightChild(p))) return T.leftChild(p); else

return T.rightChild(p);

}

Фрагмент кода 9.8. Конструктор и вспомогательные методы класса AVLTree

r

*                     Вспомогательный метод, вызываемый методами insertltem

*                     и removeElement.

*                     проходит путь Т от данного узла до корня. Для каждого

*                     обнаруженного узла

*                     zFos пересчитывает высоту zPos и выполняет трехузловое

*                     реструктурирование,

*                     если zPos оказывается несбалансированным.

private void rebalance(Position zPos) { while (IT.isRoot(zPos)) { zPos = T.parent(zPos); setHeight(zPos); if (!isBalanced(zPos)) {

// выполняет трехузловую реструктуризацию

Position xPos = tallerChild(tallerChild(zPos));

zPos = ((RestructurableNodeBinaryTree) T).restructure(xPos);

setHeight(T.leftChild(zPos));

setHeight(T.rightChild(zPos));

setHeight(zPos);

}

}

}

// методы словарного АТД

/** переопределяет соответствующие методы родительского класса */ public void insertltem(Object key. Object element) throws InvalidKeyException { super.insertltem(key, element); // может выдать InvalidKeyException Position zPos = actionPos; // начинает с позиции ввода T.replaceElement(zPos, new AVLItem(key, element, 1)); rebalance(zPos);

}

/** переопределяет соответствующие методы родительского класса. */ public Object removeElement(Object key) throws InvalidKeyException { Object toReturn = super.removeElement(key);

// может выдать InvalidKeyException if (toReturn != NO_SUCH_KEY) {

Position zPos = actionPos; // начинает с позиции удаления rebalance(zPos);

}

return toReturn;

}

Фрагмент кода 9.9. Вспомогательный метод rebalance и словарные методы insertltem и removeElement класса AVLTree

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

По теме:

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