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

0

Теперь опишем класс бинарного поискового дерева BinarySearchTree, хранящий пары «ключ-элемент» класса Item (показанного повторно во фрагменте кода 9.2) в качестве элементов, расположенных в позициях (узлах) его бинарного дерева. Код BinarySearchTree приведен во фрагментах кода 9.3—9.5. Заметим, что показанное бинарное дерево Г использует только интерфейс BinaryTree, а также содержит методы expandExternal и removeAboveExternal (см. п. 6.4.2).

Таким образом, класс BinarySearchTree не зависит от специфики реализации бинарного дерева и в полной мере определяет возможность многоразового использования кода.

Вспомогательный метод findPosition, созданный на основе алгоритма TreeSearch, инициируется методами findElement, insertltem и removeElement. Переменная экземпляра actionPos сохраняет позицию, в которой завершилась последняя операция поиска, ввода или удаления. Эта переменная в принципе не нужна при реализации бинарного поискового дерева, но полезна для классов, расширяющих BinarySearchTree (см. фрагменты кода 9.8-9.9 и 9.12-9.13) при определении позиции, над которой была выполнена предыдущая операция. Позиция actionPos имеет соответствующее значение, обеспечивающее ее инициализацию сразу после выполнения методов findElement, insertltem и removeElement.

public class Item {

private Object key, elem; protected Item (Object k, Object e) { key = k; elem = e;

}

public Object key() { return key; } public Object element() { returp elem; } public void setKey(Object k) { key = k; } public void setElement(Object e) { elem = e; }

}

Фрагмент кода 9.2. Класс для пар «ключ-элемент», хранящихся в словаре (анало-* гичен классу фрагмента кода 7.2)

/** реализация словаря с помощью бинарного поискового дерева */ public class BinarySearchTree implements Dictionary { Comparator С; // компаратор BinaryTree T; // бинарное дерево

protected Position actionPos; // позиция ввода или родительский

// элемент удаленной позиции

14 Зак 2456

public BinarySearchTree(Comparator c)*{ С = с;

T (BinaryTree) new NodeBinaryTree();

}

// вспомогательные методы

/** извлечь ключ объекта в данном узле дерева protected Object key(Position position) { return ((Item) position.element()).key();

}

/** извлечь элемент объекта в данном узле дерева protected Object element(Position position) { return ((Item) position.element()).element();

}

/** проверить, подходит ли данный ключ

protected void checkKey(Object key) throws InvalidKeyException { if (IC.isComparable(key)) -

throw new InvalidKeyExceptionfKey "+key+" is not comparable11);

}

Фрагмент кода 9.3. Класс BinarySearchTree (продолжение — фрагмент кода 9.4)

Г* Вспомогательный метод, используемый removeElement protected void swap(Position swapPos, Position remPos){ T.replaceElement(swapPos, remPos.element());

}

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

protected Position findPosition(Object key, Position pos) { if (T.isExternal(pos))

return pos; // ключ не найден, возвращается последний простой узел else {

Object curKey = key(pos); if (C.isLessThan(key, curKey))

return findPosition(key, T.leftChild(pos)); else if (C.isGreaterThan(key, curKey)) // поиск в левом дереве

return findPosition(key, T.rightChild(pos)); // поиск в правом дереве else

return pos; // возвращает составной узел, где обнаружен ключ

}

}

// метод из АТД «словарь» public int size() {

return (T.size() – 1) / 2; . ,}      

public boolean isEmpty() {

return T.size() == 1;

public Object findElement(Object key) throws InvalidKeyException { checkKey(key); // может выдать InvalidKeyException Position curPos = findPosition(key, T.root()); actionPos = curPos; // узел, на котором заканчивается поиск if (T.islnternal(curPos))

return element(curPos); else

return NO_SUCH_KEY;

}

Фрагмент кода 9.4. Класс BinarySearchTree (продолжение фрагмента кода 9.3)

public void insertltem(Object key, Object element) throws InvalidKeyException {

checkKey(key); // может выдать InvalidKeyExceptilpn Position insPos = T.root(); do {

insPos = findPosition(key, insPos); if (T.isExternal(insPos)) break;

else // ключ уже существует

insPos = T.rightChild(insPos);                                                                                             \

} while (true); T.expandExternal(insPos); Item newltem = new ltem(key, element); T.replaceElement(insPos, newltem);

actionPos = insPos; // узел, в который введен новый объект

}

public Object rempveElement(Object key) throws InvalidKeyException { Object toReturn;

checkKey(key); // может выдать InvalidKeyException Position remPos = findPosition(key, T.root()); if(T.isExternal(remPos)) {

actionPos = remPos; // узел, на котором успешно закончился поиск return NO-SUCH-KEY;

}

else{

toReturn = element(remPos); // возвращаемый элемент if (T.isExternal(T.leftChild(remPos)))

remPos = T.leftChild(remPos); else if (T.isExternal(T.rightChild(remPos)))

remPos = T.rightChild(remPos); else { // ключ находится в узле с составными дочерними элементами

Position swapPos = remPos; // найти узел для замены объектов remPos = T.rightChild(swapPos); do

remPos = T.leftChild(remPos); while (T.islnternal(remPos)); swap(swapPos, T.parent(remPos));

}

actionPos = T.sibling(remPos); // лист, соседний удаляемому листу T.removeAboveExternal(remPos);

return toReturn; }

}

}

Фрагмент кода 9.5. Класс BinarySearchTree (продолжение фрагмента кода 9.4)

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

По теме:

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