Звучит знакомо? но мы собираемся присмотреться.
двоичное дерево поиска (BST) - это двоичное дерево в симметричном порядке, где каждый узел имеет ключ (и соответствующее значение).
Бинарное дерево означает, что оно состоит из узлов, и каждый узел имеет не более двух дочерних элементов (левый и правый дочерние элементы).
В то время как симметричный порядок заключается в том, что каждый узел больше, чем все узлы в левом поддереве, и меньше, чем ключи в правом поддереве.
Он используется для реализации таблиц символов (ассоциативных массивов), и это ключ, который будет использоваться для соответствующей сортировки узлов.
Деревья двоичного поиска
Мы собираемся реализовать таблицы символов, используя двоичное дерево поиска. Итак, основные операции двоичного дерева поиска будут такими же; получить, поместить, удалить, contains & isEmpty.
Реализация
Начнем с класса двоичного дерева поиска (BST). Он имеет ссылочную переменную под названием «root», указывающую на корневой узел.
Тип «Ключ и значение» - это любой универсальный тип. А для ключей они сопоставимы . Итак, мы можем использовать метод compareTo (), чтобы сравнить, является ли один ключ меньше другого, больше или равен.
public class BST<Key extends Comparable<Key>, Value> {
private Node root = null; // root of BST
}
Затем у нас есть внутренний класс под названием «Узел» для представления каждого узла в дереве. Каждый узел имеет ключ, значение, ссылку на левый и правый дочерний узел и целое число, «подсчитывающее» количество узлов в поддереве с корнем в этом узле.
private class Node {
private Key key; // sorted by key
private Value val; // associated data
private Node left, right; // left and right subtrees
private int count; // number of nodes in subtree
public Node(Key key, Value val, int count) {
this.key = key;
this.val = val;
this.count = count;
}
}
- получать
Он рекурсивно ищет узел, используя его ключ, и возвращает его значение.
Он начинается с корневого узла, если он меньше чем, то идем влево, если больше чем, идем вправо, и если он равен, все готово; поисковый результат. С другой стороны, если дерево пусто или мы достигли нулевой ссылки, поиск пропущен.
// searches for a node with a given key, and returns associated val.
public Value get(Key key) {
return get(root, key);
}
// A helper method to search for a node given a starting Node
private Value get(Node current, Key key) {
if (current == null) return null; // search miss
int cmp = key.compareTo(current.key);
if (cmp < 0) return get(current.left, key); // go left
else if (cmp > 0) return get(current.right, key); // go right
else return current.val; // search hit
}
С этого момента, во время нашей реализации для таблицы символов с использованием двоичного дерева поиска, может случиться так, что когда ключ равен нулю, на этом этапе вы можете вызвать исключение.
- положил
Вставьте узел ключа и значение в дерево. Он рекурсивно просматривает дерево, пока не найдет нулевую ссылку, и все, что нам нужно сделать, это заменить эту ссылку новым узлом.
Если ключ уже существует, он обновляет значение (избегайте дублирования). Он удаляет узел из дерева, если значение равно нулю.
public void put(Key key, Value val) {
if (val == null) { // remove key from table if value is null
delete(key);
return;
}
root = put(root, key, val);
}
// A helper method to insert a node given a starting Node
private Node put(Node current, Key key, Value val) {
if (current == null) return new Node(key, val, 1);
// if key exists, overrides the old value (avoid duplicates)
int cmp = key.compareTo(current.key);
if (cmp < 0) current.left = put(current.left, key, val);
else if (cmp > 0) current.right = put(current.right, key, val);
else current.val = val;
// update number of nodes rooted at Node current
current.count = 1 + size(current.left) + size(current.right);
return current;
}
- удалять
Мы пока пропустим его, но вернемся к нему позже (см. Ниже).
- содержит
// Is the given key exists?
public boolean contains(Key key) { return get(key) != null; }
- Дерево пусто?
Когда дерево пусто, корневой узел будет нулевым, и, следовательно, количество узлов с корнем в корневом узле равно 0; в дереве нет узлов.
// Is the table empty?
public boolean isEmpty() { return size(root) == 0; }
// A helper method to get number of nodes rooted at Node current
private int size(Node current) {
if (current == null) return 0;
else return current.count;
}
Анализ
Стоимость - это количество сравнений, равное глубине узла в дереве +1. Наилучший случай для поиска - O (1); корень может быть ответом.
Время выполнения операций get и put равно количеству сравнений, которое равно глубине узла в дереве + 1.
Глубина дерева зависит от формы деревьев, которая, в свою очередь, зависит от порядка, в котором вставляются ключи.
- худший случай, когда ключи вставляются в порядке убывания; максимальная глубина дерева - O (N).
- лучший случай, когда дерево идеально сбалансировано; максимальная глубина дерева - O (LogN).
Если ключи вставляются в случайном порядке, количество сравнений в операции search или insert составляет ~ (2 LogN) в среднем , а в худшем случае - ~ (4.311 LogN) (предложено Reed, 2003). Существует небольшая вероятность того, что высота будет ~ (N) в худшем случае, если ключи вставлены в случайном порядке.
В отличие от Binary Heaps, где все уровни заполнены (почти кроме последнего).
Сбалансированное двоичное дерево означает, что для каждого (не листового) узла высота левого и правого поддеревьев различается не более чем на единицу, в то время как идеально сбалансированное означает, что все конечные узлы имеют одинаковую глубину. или того же уровня; каждый путь от корня до нулевой ссылки имеет одинаковую длину.
Заказанные операции
Важной причиной широкого использования бинарных деревьев поиска является то, что они позволяют нам хранить ключи в порядке.
Таким образом, используя реализацию двоичного дерева поиска для таблиц символов, где ключи сопоставимы, мы можем поддерживать дополнительные операции, такие как: min, max, пол, потолок, рейтинг, select и т. д.
- Мин. И Макс.
Продолжаем двигаться влево от корня, чтобы найти минимум, и вправо, чтобы найти максимум.
// get the smallest key
public Key min() {
if (isEmpty()) throw new NoSuchElementException("...");
return min(root).key;
}
// A helper method to get the smallest node starting from Node curre
private Node min(Node current) {
if (current.left == null) return current;
else return min(current.left);
}
// get the largest key
public Key max() {
if (isEmpty()) throw new NoSuchElementException("...");
return max(root).key;
}
// A helper method to get the largest node starting from Node curren
private Node max(Node current) {
if (current.right == null) return current;
else return max(current.right);
}
- Пол и потолок
Для поиска этажа, если текущий узел больше ключа k, продолжайте движение влево. Если текущий узел меньше k, идите вправо. Каждый раз, когда мы идем направо, текущий узел является полом, пока мы снова не пойдем направо.
public Key floor(Key key) {
if (isEmpty()) throw new NoSuchElementException("...");
Node x = floor(root, key);
if (x == null) return null; // if empty, return null
else return x.key;
}
// A helper method to get the floor of a key starting from Node curr
private Node floor(Node current, Key key) {
if (current == null) return null;
int cmp = key.compareTo(current.key);
if (cmp == 0) return current;
if (cmp < 0) return floor(current.left, key);
Node t = floor(current.right, key);
if (t != null) return t;
else return current;
}
Поиск потолка аналогичен, просто поменяйте местами вправо и влево.
public Key ceiling(Key key) {
if (isEmpty()) throw new NoSuchElementException("...");
Node x = ceiling(root, key);
if (x == null) return null; // if empty, return null
else return x.key;
}
// A helper method to get the ceiling of a key starting from Node cu
private Node ceiling(Node current, Key key) {
if (current == null) return null;
int cmp = key.compareTo(current.key);
if (cmp == 0) return current;
if (cmp > 0) return ceiling(current.right, key);
Node t = ceiling(current.left, key);
if (t != null) return t;
else return current;
}
- Ранг и выбор
Для ранга предположим, что нам нужен ранг ключа k…
Если текущий узел больше k, продолжайте движение влево; Это означает, что ключ, который мы ищем, находится перед (меньше) текущего ключа.
Если текущий узел меньше k, идите вправо; Это означает, что ключ, который мы ищем, находится после (больше) текущего ключа, и поэтому нам нужно подсчитать текущий узел и все узлы в его левом поддереве.
Помните, что ранг ключа k - это количество ключей меньше k. Другими словами, он возвращает индекс k в отсортированном массиве или упорядоченном дереве.
// get the number of keys in the subtree less than given key.
public int rank(Key key) {
return rank(root, key);
}
// A helper method to get the rank of a key starting from Node curre
private int rank(Node current, Key key) {
if (current == null) return 0;
int cmp = key.compareTo(current.key);
if (cmp < 0) return rank(current.left, key);
else if (cmp > 0)
return 1 + size(current.left) + rank(current.right, key);
else return size(current.left);
}
Для select предположим, что нам нужен ключ с рангом k (с индексом k в BST) …
Если количество ключей t в левом поддереве больше k, мы идем влево, а если t меньше k , мы идем вправо и обновляем k = kt-1 (вычитаем текущий узел и все узлы в его левом поддереве).
// return the key at a given rank k; return kth smallest key
public Key select(int k) {
if (k < 0 || k >= size(root)) { // same as when the key is null
throw new IllegalArgumentException("...");
}
Node x = select(root, k);
return x.key;
}
// A helper method to return key of rank k starting from Node curren
private Node select(Node current, int k) {
if (current == null) return null;
int t = size(current.left);
if (t > k) return select(current.left, k);
else if (t < k) return select(current.right, k-t-1);
else return current;
}
- Запросы диапазона
Определить, сколько ключей попадает в заданный диапазон [lo, hi], можно сделать, вычтя ранг более низкого ключа lo из ранга более высокого hi (добавление 1, если в дереве существует более высокий ключ).
public int size(Key lo, Key hi) {
if (lo.compareTo(hi) > 0) return 0;
if (contains(hi)) return rank(hi) - rank(lo) + 1;
else return rank(hi) - rank(lo);
}
При поиске ключей, попадающих в заданный диапазон, можно пройти по дереву по порядку; левое поддерево, текущий узел, затем рекурсивно правое поддерево.
public Iterable<Key> keys(Key lo, Key hi) {
// create an Iterable object
Queue<Key> queue = new Queue<Key>();
// fill the Iterable object(queue) with keys in range[lo, hi]
keys(root, queue, lo, hi);
// return the Iterable object so we can iterate over the keys
return queue;
}
// A helper method to fill the Iterable object(queue) with the keys
private void keys(Node current, Queue<Key> queue, Key lo, Key hi) {
if(current == null) return;
int cmplo = lo.compareTo(current.key);
int cmphi = hi.compareTo(current.key);
// if lo is less than current node, go left
if (cmplo < 0) keys(current.left, queue, lo, hi);
// if current node within the range[lo, hi], add to the queue
if (cmplo <= 0 && cmphi >= 0) queue.enqueue(current.key);
// if hi is greater than current node, go right
if (cmphi > 0) keys(current.right, queue, lo, hi);
}
// if no given range is specified, then iterate over all the keys
public Iterable<Key> keys() { return keys(min(), max()); }
Анализ
Для всех операций с деревом двоичного поиска требуется h (кроме метода keys ()), где h - высота (глубина) дерева. Высота дерева пропорциональна (LogN), если ключи вставлены в случайном порядке.
Метод keys () всегда принимает значение O (N), несмотря на высоту.
Удаление в BST
Мы пропустили метод delete в нашей реализации (см. Выше). Это связано с тем, что операция удаления требует внимательного изучения.
Ленивый подход
Чтобы удалить узел с заданным ключом, установите для него значение null и оставьте ключ. Этот узел становится бесполезным, он нужен только для того, чтобы вести поиск по дереву с помощью своего ключа.
Этот подход будет стоить ~ (2 * LogN) за операцию insert, search и delete, если ключи вставляются в случайном порядке (где N - количество узлов, включая удаленные узлы в BST), но это неудобно, потому что у вас будет большое количество бесполезных узлов (перегрузка памяти).
Удалить ключ мин. / Макс.
Чтобы удалить минимум, мы идем влево, пока не найдем узел с нулевой левой ссылкой, а затем заменим ссылку на этот узел его правой ссылкой.
Чтобы удалить максимум, он работает аналогично, просто поменяйте местами вправо и влево.
После этого удаленный узел становится доступным для сборщика мусора.
// delete the smallest node
public void deleteMin() {
if (isEmpty()) return;
root = deleteMin(root);
}
// A helper method to delete the min node starting from Node current
private Node deleteMin(Node current) {
// go to left until finding a node where left is null
// once, we found it, return it's right node
if (current.left == null) return current.right;
// assign the left link of current node
current.left = deleteMin(current.left);
// update the size of each node as you go up
current.count = size(current.left) + size(current.right) + 1;
return current;
}
Удаление произвольного узла (метод Хиббарда)
Мы можем действовать аналогичным образом, чтобы удалить любой узел, у которого есть один дочерний элемент (или без дочерних), но что мы можем сделать, чтобы удалить узел, у которого есть два дочерних элемента? Решение состоит в замене узла его преемником.
Эта замена сохраняет порядок в дереве, потому что нет ключей между ключом узла, который мы хотим удалить, и ключом его преемника.
Узел-преемник узла x - это крайний левый узел (узел с наименьшим ключом) в правом поддереве x.
// delete a node given it's key
public void delete(Key key) {
root = delete(root, key);
}
// A helper method to delete a node starting from Node current
private Node delete(Node current, Key key) {
if (current == null) return null;
// search for the node you want to delete
int cmp = key.compareTo(current.key);
if (cmp < 0) current.left = delete(current.left, key);
else if (cmp > 0) current.right = delete(current.right, key);
else { // once you found it
// If no right child, return the left child
if (current.right == null) return current.left;
// If no left(but right child), return the right child.
if (current.left == null) return current.right;
// Otherwise; current node has two children
// 1. Save a link to the node to be deleted in t
Node t = current;
// 2. Set current to point to its successor min(t.right).
current = min(t.right);
// 3. Set the right link of current to deleteMin(t.right);
// the link to the tree containing all the keys that are
// larger than current.key after the deletion.
current.right = deleteMin(t.right);
// 4. Set the left link of current(which was null) to t.left
// (all the keys that are less than both the deleted key and
// its successor).
current.left = t.left;
}
// update the size of each node as you go up
current.count = size(current.left) + size(current.right) + 1;
return current;
}
Ожидаемая высота, полученная в результате последовательности случайных вставок и удалений по Хиббарду, приводит к несбалансированному дереву. Высота дерева становится sqrt (N) вместо (LogN).
Сводка: реализации таблиц символов
В BST, если ключи расположены в случайном порядке, это обеспечивает вероятностную гарантию для операций поиска и вставки (2 LogN) в среднем случае и (4,311 LogN) в худшем случае.
В BST операции удаления занимают O (N) в худшем случае и O (sqrt (N)) в среднем. Если операции удаления разрешены, то средний случай поиска и вставки также равен O (sqrt (N)).
- Теперь вопрос в том, Можем ли мы гарантировать производительность (LogN) для всех операций в худшем случае? Да, красно-черные BST могут это сделать.
