Алгоритмы и структуры данных. Извлечение информации на языке Java

154

Глава 12. TreeMap

Упражнение 10

Для этого упражнения вы напишете реализацию интерфейса

Map, используя бинарное дерево поиска.

Начало реализации под названием MyTreeMap выглядит следу-

ющим образом:

public class MyTreeMap<K, V> implements Map<K, V> {

private int size = 0;

private Node root = null;

Переменная экземпляра — size, отслеживающая количество

ключей, и root, являющаяся ссылкой на корень дерева. Если

дерево пустое, то root имеет значение null и size равно 0.

Реализация класса Node, который определен внутри MyTreeMap,

будет такой:

protected class Node {

public K key;

public V value;

public Node left = null;

public Node right = null;

public Node(K key, V value) {

this.key = key;

this.value = value;

}

}

Каждая вершина содержит пару «ключ ...