Значение узла в дереве называется ключом. Бинарное дерево — это дерево, в котором каждый узел имеет не более двух дочерних элементов. Двоичное дерево поиска (BST) — это дерево, в котором для каждого узла правый дочерний элемент больше или равен левому дочернему элементу. Это приводит к тому, что правая половина дерева имеет значения, обычно превышающие значения левой половины на каждом уровне. Это означает, что бинарное дерево поиска частично отсортировано (тип неполной сортировки). BST можно хранить в структуре, подобной массиву, где корневой узел является первым значением.
Бинарное дерево может быть преобразовано в различные самобалансирующиеся деревья с различными наборами дополнительных условий, такие как дерево AVL и красно-черное дерево.
TreeMap в Java — это красно-черное дерево. Однако каждый узел состоит из ключа и соответствующего значения (пары ключ/значение), а не только из ключа. Каждая пара ключ/значение будет одним элементом в структуре, подобной массиву. В этой статье объясняется, как использовать TreeMap в Java, начиная с двоичного дерева поиска, за которым следует красно-черное дерево, а затем Java TreeMap.
Бинарное дерево поиска
Ниже приведен пример бинарного дерева поиска:
У каждого узла есть ключ. Ключ (значение) для корневого узла равен 8. Левый дочерний узел равен 3, а правый дочерний узел равен 10 (10 >= 3). Можно видеть, что для любого узла, имеющего двух дочерних элементов, правый дочерний элемент больше или равен левому дочернему элементу. Кроме того, правая половина дерева имеет значения, превышающие значения левой половины дерева для каждого уровня.
Все значения приведенного выше дерева можно поместить в массив следующим образом:
8, 3, 10, 1, 6, , , , 14, 4, 7, , , , , , , 13, ,
Обратите внимание, что массив (дерево) начинается с 8; опускается до 3, затем поднимается выше 8 в 10; снижается до 1, повышается до 6, затем имеет NIL до 14; снижается до 4; повышается до 7; снова NIL; затем 13 и последний NIL.
8 — это первое значение с индексом 0. Это корневой узел (корневой родитель). Это не обязательно самое большое значение среди всех значений. Его первый потомок (3) имеет индекс 1, индекс которого равен 2(0) + 1, где 0 — индекс родителя. Его второй потомок (10) имеет индекс 2, что равно 2(0) + 2, где 0 — индекс родителя.
3 находится в индексе 1. Это родитель. Его первый потомок (1) имеет индекс 3, что равно 2(1) + 1, где 1 — индекс родителя. Его второй потомок (6) имеет индекс 4, что равно 2(1) + 2, где 1 — индекс родителя.
6 находится в индексе 4. Это родитель. Его первый потомок (4) имеет индекс 9, что равно 2(4) + 1, где 4 — индекс родителя. Его второй потомок (7) имеет индекс 10, что равно 2(4) + 2, где 4 — индекс родителя.
10 находится в индексе 3. Это родитель. У него нет первого (левого) потомка, который должен был быть с индексом 7, что равно 2(3) + 1, где 3 — индекс родителя. Его второй потомок (14) имеет индекс 8, что равно 2(3) + 2, где 3 — индекс родителя.
14 находится в индексе 8. Это родитель. Его первый потомок (13) имеет индекс 17, что равно 2(8) + 1, где 8 — индекс родителя. У него нет правого (второго) потомка, который должен был быть с индексом 18, что равно 2(8) + 2, где 8 — индекс родителя.
В общем, поскольку подсчет индексов начинается с 0. Пусть я представляю индекс родителя массива; и поэтому левый (первый) потомок родителя с индексом i имеет индекс 2i + 1; а его правый (второй) дочерний элемент имеет индекс 2i + 2. Некоторые ячейки в массиве могут быть пустыми; они не должны иметь значений.
Красно-черное дерево
Красно-черное дерево — это сбалансированное бинарное дерево поиска. Ниже приведено уже сбалансированное красно-черное дерево:
Сбалансированное дерево – это дерево небольшой высоты. Позиции узлов изменены и отмечены красным и синим цветами, чтобы иметь наименьшую возможную высоту дерева в его развитии.
Используя формулы 2i + 1 и 2i + 2, значения можно поместить в структуру, подобную массиву, следующим образом:
13, 8, 17, 1, 11, 15, 25, , 6, , , , , 22, 27
Обратите внимание, что массив начинается с 13, опускается до 8 и затем повышается до 17. Затем он опускается за пределы 8 до 1, а затем повышается до 11, затем до 15, затем до 25; от которого идет NIL, а затем опускается до 6. Перед 22 и 27 следуют NIL.
Массив сбалансированного дерева, такой как красно-черное дерево выше, имеет меньше NIL, чем его соответствующее несбалансированное двоичное дерево поиска. Длина массива сбалансированного дерева короче, чем у соответствующего несбалансированного дерева.
Красно-черное дерево — это частично упорядоченное дерево.
Пары ключ/значение для Java TreeMap
Предыдущее красно-черное дерево имеет только ключи в качестве значений узлов. Каждому целочисленному ключу может быть присвоено соответствующее строковое значение. В следующем списке есть те же ключи с соответствующими значениями:
13/thirteen, 8/eight, 17/seventeen, 1/one, 11/eleven, 15/fifteen, 25/twenty-five, 6/six, 22/twenty-two, 27/twenty-seven
Это пары ключ/значение, подходящие для Java TreeMap. Каждому ключу будет сопоставлено соответствующее значение. Пара ключ/значение называется записью карты в Java. Для Java TreeMap расположение узлов осуществляется по ключам (а не по значениям пар ключ/значение). Каждый ключ сопоставляется со своим значением.
Создание карты Java TreeMap
В Java TreeMap — это класс в пакете java.util.*, который следует импортировать. Этот класс имеет четыре конструктора, и в этой статье проиллюстрированы два конструктора.
Публичная древовидная карта ()
Это создает пустой TreeMap. Следующий сегмент кода иллюстрирует это:
TreeMap<Integer,String> tm = new TreeMap<Integer,String>(); tm.put(13, "thirteen"); tm.put(8, "eight"); tm.put(17, "seventeen"); tm.put(1, "one"); tm.put(11, "eleven"); tm.put(15, "fifteen"); tm.put(25, "twenty-five"); tm.put(6, "six"); tm.put(22, "twenty-two"); tm.put(27, "twenty-seven");
Метод put() включает пары ключ/значение в TreeMap. После всего этого TreeMap становится сбалансированным внутри.
Public TreeMap (Map<? extends K,? extends V> m)
Этот метод конструктора создает карту из другой уже созданной карты, как в следующем фрагменте кода:
TreeMap<Integer,String> tm = new TreeMap<Integer,String>(); tm.put(13, "thirteen"); tm.put(8, "eight"); tm.put(17, "seventeen"); tm.put(1, "one"); tm.put(11, "eleven"); tm.put(15, "fifteen"); tm.put(25, "twenty-five"); tm.put(6, "six"); tm.put(22, "twenty-two"); tm.put(27, "twenty-seven"); TreeMap<Integer,String> tm1 = new TreeMap<Integer,String>(tm);
tm1 создается из tm. После всего этого оба TreeMaps внутренне сбалансированы; с первым сбалансированным первым. Балансировка происходит, поскольку ключи включают пары.
Методы карты дерева Java
Публичный V put (ключ K, значение V)
Строго говоря, метод put() не добавляет пару ключ/значение. Он связывает определенное значение с определенным ключом. Если ключ уже существовал в TreeMap с другим значением, значение заменяется новым. Этот метод возвращает старое значение или ноль, если старого значения не было. Применение этого метода было продемонстрировано выше.
Публичный размер()
Этот метод возвращает количество сопоставлений ключ/значение (пар) в TreeMap. Следующий фрагмент кода показывает, как его использовать:
int it = tm.size(); System.out.println(it);
Результат равен 10, что указывает на то, что в этом объекте TreeMap имеется 10 пар ключ/значение.
Public V get (ключ объекта)
Этот метод возвращает значение, соответствующее аргументу, который является ключом. Возвращает null, если ключ не существует. Следующий код иллюстрирует это для пары ключ/значение: 11/”eleven” и для ключа 40, которого не существует:
String val = tm.get(11); String str = tm.get(40); System.out.print(val + ", "); System.out.print(str + " "); System.out.println();
Результат:
eleven, null
Открытый набор<K>keySet()
Этот метод возвращает набор ключей, которые находятся в TreeMap. Для отображения ключей необходимо использовать итератор. Следующий сегмент кода для предыдущего TreeMap иллюстрирует это:
Set<Integer> st = tm.keySet();
Iterator<Integer> iter = st.iterator();
while (iter.hasNext()) {
System.out.print(iter.next() + ", ");
}
System.out.println();
Результат:
1, 6, 8, 11, 13, 15, 17, 22, 25, 27,
Возвращаемый список полностью отсортирован (по возрастанию), хотя TreeMap имеет частичную внутреннюю сортировку.
Значения Public Collection<V>()
Это возвращает представление коллекции (список) всех значений в TreeMap без ключей. Для отображения значений необходимо использовать итератор. Следующий сегмент кода для предыдущего TreeMap иллюстрирует это:
Collection<String> col = tm.values();
Iterator<String> iter = col.iterator();
while (iter.hasNext()) {
System.out.print(iter.next() + ", ");
}
System.out.println();
Результат:
one, six, eight, eleven, thirteen, fifteen, seventeen, twenty-two, twenty-five, twenty-seven,
Значения отображаются на основе их полных отсортированных ключей (по возрастанию), хотя TreeMap имеет внутреннюю частичную сортировку.
Открытый набор<Map.Entry<K,V>> entrySet()
Это возвращает набор пар ключ/значение. Чтобы отобразить ключи и соответствующие им значения, необходимо использовать итератор. Следующий сегмент кода для вышеприведенной TreeMap иллюстрирует это:
Set<Map.Entry<Integer,String>> pairs = tm.entrySet();
Iterator<Map.Entry<Integer,String>> iter = pairs.iterator();
while (iter.hasNext()) {
Map.Entry<Integer,String> etry = iter.next();
int in = etry.getKey(); String str = etry.getValue();
System.out.println(in + " => " + str);
}
Результат:
1 => one 6 => six 8 => eight 11 => eleven 13 => thirteen 15 => fifteen 17 => seventeen 22 => twenty-two 25 => twenty-five 27 => twenty-seven
Пары были отображены на основе их полных отсортированных ключей (по возрастанию), хотя TreeMap имеет внутреннюю частичную сортировку.
Вывод
В Java TreeMap — это красно-черное дерево, которое является самобалансирующимся двоичным деревом поиска. В этой статье обсуждались часто используемые методы и конструкция Java TreeMap. Мы надеемся, что вы нашли эту информацию полезной.руководств.