Просто с помощью связного списка из key-value пар. Нужная пара находится линейным поиском. Минусы такого подхода, естественно, скорость работы, и невозможность проитерировать по структуре данных по порядку.
Поддерживать упорядоченный массив из key-value пар + бинарный поиск. Плюс в том, что теперь поиск работает за лоарифм, однако вставка и удаление элементов всё ещё работает за линейное время, потому что надо сдвинуть все элементы массива.
Я на секунду подумал, что можно ведь вместо упорядоченного массива использовать связный список, но тогда бы не получилось реализовать эффективный бинарный поиск из-за отсутствия random access.
BST is a binary tree in a symmetric order. Symmetric order — это, когда все ключи всех вершин в левом поддереве меньше, чем ключ в корневой вершине, а в правом поддереве — большие ключи.
При кольная рекурсивная реализация метода, который вставляет ключ в бинарное дерево:
public void put(Key key, Value value) {
root = put(root, key, value);
}
// Возвращает либо старую ссылку на x, либо ссылку на новую,
// только что созданную вершину
private Node put(Node x, Key key, Value value) {
// случай с пустым поддеревом
if (x == null)
return new Node(key, value);
int cmp = key.compareTo(x.key);
// пробуем запихнуть в левое или правое поддерево
if (cmp < 0)
x.left = put(x.left, key, value);
else if (cmp > 0)
x.right = put(x.right, key, value);
else // if (cmp == 0)
// если нашли нужную вершину, то апдейтим значение
x.value = value;
return x;
}
Проблема с несбалансированным бинарным деревом в том, что оно легко может выродиться в линейный список с небольшим дополнительным оверхедом в виде второй сслыки в каждой вершине, если добавлять элементы в возрастающем/убывающем порядке.
Но, тем не менее, всё не так плохо: при добавлении $N$ рандомных элементов мат ожидание количества сравнений при каждой вставке (различных элементов) будет логарифмиечким, а точнее $\sim 2 \ln N$, потому что вставка $N$ элементов в бинарное дерево в точности соответствует по сути быстрой сортировке, только в немного другом порядке, а уже было доказано, что мат ожидание для быстрой сортировки — это $\sim 2 N \ln N$, то можно разделить на $N$ это всё и получить логарифм.
И ещё есть теорема о том, что мат ожидание высоты дерева $\sim 4.311 \ln N$. То есть опять же, не так уж и далеко от идеального значения, но всё портит худший случай.
Чтобы найти минимальный элемент в дереве, очевидно, надо просто пройти до конца налево, а максимальный — это самый правый элемент. Если надо найти ключ меньший или равный данному (floor), то тут надо рассмотреть несколько случаев, при этом функцию будем реализовывать так же, рекурсивно. Пусть мы ищем floor(k) и в данный момент находимся в вершине со значением R:
Реализация floor:
public Key floor(Key key) {
Node x = floor(root, key);
if (x == null)
return null;
return x.key;
}
// Находит вершину с floor значением, иначе возвращает null
private Node floor(Node x, Key key) {
// в пустом поддереве ничего нет
if (x == null)
return null;
int cmp = key.compareTo(x.key);
if (cmp == 0)
return x;
if (cmp < 0)
return floor(x.left, key);
// третий случай с тем, что ответ
// может быть в правом поддереве
Node t = floor(x.right, key);
if (t != null)
return t.value;
else
return x;
}
Если мы будем хранить в вершинах ещё и количество элементов в поддеревьях, то можно будет довольно быстро вычислять размер дерева и ещё порядок элемента в дереве. Но тогда придётся ещё апдейтить размеры размеров деревьев.
И тут опять получится рекурсивный алгоритм для вычисления ранга ключа (какой он по счёту).
// апдейтим значение
private Node put(Node x, Key key, Value value) {
// ...
int cmp = key.compareTo(x.key);
// ...
// То есть в count засовывается размеры левого и правого поддеревьев
// плюс ещё сам x (+1)
x.count = 1 + size(x.left) + size(x.right);
// ...
}
public int rank(Key key) {
return rank(key, root);
}
private int rank(Key key, Node x) {
if (x == null)
return 0;
int cmp = key.compareTo(x.key);
if (cmp < 0)
// root > key
// тогда корневой элемент и элементы справа не делают вклада
// в значение ранга элемента key
return rank(key, x.left);
else if (cmp > 0)
// root < key
// тогда в ранг делают вклад корневой элемент и все
// элементы левого поддерева + ранг key в терминах
// правого поддерева
return 1 + size(x.left) + rank(key, x.right);
else // if (cmp == 0)
return size(x.left);
}
Inorder traversal — рекурсивно обойти левое поддерево, пройтись по корню, потом рекурсивно обойти правое поддерево.
При этом, если у вершин дерева есть ссылки на родителей, то можно обходить дерево нерекурсивно. Начинаем с самого маленького элемента дерева, после чего либо достаём последователя из правого поддерева, либо идём вверх до тех пор, пока не попадём в родительскую вершину из левого поддерева (ну, или что эквивалентно тому, что мы перейдём от вершины с меньшим ключом к её родителю с большим в случае, если дерево — это BST, конечно).
public Node next() {
Node next = current;
if (current.right != null)
current = min(current.right);
else
while (current != null) {
if (current.parent != null
&& current == current.parent.left) {
current = current.parent;
break;
}
current = current.parent;
}
return next;
}
А если нет любой другой причины хранить и поддерживать родителей для каждой вершины дерева, то можно реализовать этот обход нерекурсивно и без необходимости в родителях (Morris inorder tree traversal). При этом он по ходу немного модифицирует структуру дерева, но потом всё возвращает обратно, но всё равно нужно помнить об этом, например, при реализации синхронизированного дерева.
Суть примерно вот в этом:
curr = root, а дальше залезаем в цикл до тех пор, пока не дойдём до curr == null.curr нет левого потомка, то обходим curr и переходим к его правому потомку.curr правым потомком максимальной вершины в левом поддереве curr (делаем такой цикл) и переходим к левому потомку curr.Node current = root;
while (current != null) {
if (current.left == null) {
print(current);
current = current.right;
} else {
// пробуем найти максимальную вершину в левом поддереве
Node pre = current.left;
while (pre.right != null && pre.right != current)
pre = pre.right;
if (pre.right == null) {
// если получается, то делаем вот так, чтобы потом
// можно было вернуться наверх
pre.right = current;
current = current.left;
} else {
// но, если попадаем цикл, то это означает, что мы уже
// проходили тут, так что надо восстановить прежнюю структуру,
// и сделать то, что в current.left == null
pre.right = null;
print(current);
current = current.right;
}
}
}
В худшем случае, если дерево — это линейный список, наклонённый строго в левую сторону, этот алгоритм пройдётся дважды по каждой вершине, так что время будет линейным. Но, наверное, вариант с поддерживанием родительских узлов ничем не хуже, потому что это совсем маленький оверхед, плюс он не требует измнения структуры дерева.
Но вообще можно реализовать примерно то же самое, если вместо изменения ссылок каждый раз, когда поворачиваешь налево, добавлять текущую вершину в стек, а потом, когда доходишь до дна, возвращаться к последней добавленной в стек вершине, обходить её и дальше идти направо и там всё то же самое:
Deque<Node> stack = new ArrayDeque<>();
Node x = root;
while (x != null || !stack.isEmpty()) {
if (x != null) {
stack.push(x);
x = x.left;
} else {
x = stack.pop();
print(x);
x = x.right;
}
}
Один из вариантов — не удалять элементы элементы в действительности, а помечать их как умершие. До определённого момента всё будет в порядке, но, в какой-то момент могилок либо станет слишком много, и тогда будет страдать производительность, либо просто память переполнится даже, если вроде по факту элементов в дереве не очень много.
Но, на самом деле, в таком подходе тут даже нет необходимости, потому что можно реализовать Hibbard deletion, который строится на нескольких случаях:
Проблема в hibbard deletion в том, что удаление несимметрично (если использовать только predecessor’ов или только successor’ов), из-за этого, если сделать достаточно много удалений и добавлений, то дерево перекашивает в одну из сторон. Конкретно со временем все операции деградируют до сложности $\sqrt N$ (ну, то есть высота дерева становится $\sqrt N$), но я не знаю, как это доказывается.
Если попытаться рандомно выбирать между successor’ом и predecessor’ом, то на практике вроде как всё улучшается, но вроде никто не доказал, что этот метод вообще что-то улучшает.
Из-за несбалансированности дерева оно может выродиться в что-то около линейного списка и тогда все рекурсивные операции будут глубины $O(N)$, и их нельзя оптимизировать хвостовой рекурсией, из-за чего потребуется не только линейное время, но и линейная память для их выполнения. Так что в этом случае лучше было бы их реализовать нерекурсивно, например, вот так.
Tree-list recursion problem. A binary search tree and a circular doubly linked list are conceptually built from the same type of nodes - a data field and two references to other nodes. Given a binary search tree, rearrange the references so that it becomes a circular doubly-linked list (in sorted order).
Можно довольно легко реализовать рекурсивно, реализовав метод append(node, node), который бы добавлял к первому циклическому списку второй. А само преобразование реализовать рекурсивно: рекурсивно превратить левое и правое поддеревья в списки, сделать из корня циклический список из одного элемента и всё вместе слить с помощью append. (Решение)
BST and Binary Tree reconstruction. (Решения)
Если есть preorder и postorder обходы произвольного бинарного дерева, то в общем случае нельзя единственным образом восстановить структуру дерева. Структуру дерева точно можно будет восстановить только, если бинарное дерево будет full (это, когда у каждой вершины либо нет ни одного потомка, либо два потомка, не путать с complete — когда полностью заполнены все уровни бинарного дерева).
Например, для pre: ABC, post: CBA есть несколько разных бинарных деревьев.
Короче, сам алгоритм выглядит примерно вот так:
Если есть preorder обход BST, то можно восстановить его структуру, если использовать немного странный алгоритм, который я так толком и не понял:
public static Node BSTFromPostorder(int[] pre) {
Node root = new Node(pre[0]);
// path from the root to the current node excluding right turns
ArrayDeque<Node> stack = new ArrayDeque<>();
stack.push(root);
for (int i = 1; i < pre.length; i++) {
Node current = null;
while (!stack.isEmpty() && pre[i] > stack.peek().value)
current = stack.pop();
if (current != null) {
current.right = new Node(pre[i]);
stack.push(current.right);
} else {
current = stack.peek();
current.left = new Node(pre[i]);
stack.push(current.left);
}
}
return root;
}
Reverse a BST. Given a standard BST (where each key is greater than the keys in its left subtree and smaller than the keys in its right subtree), design a linear-time algorithm to transform it into a reverese BST (where each key is smaller than the keys in its left subtree and greater than the keys in its right subtree). The resulting tree shape should be symmetric to the original one.
Level-order traversal reconstruction of a BST. Given a sequence of keys, design a linear-time algorithm to determine whether it is the level-order traversal of some BST (and construct the BST itself).
Level-order traversal reconstruction of a BST. Given a sequence of keys, design a linear-time algorithm to determine whether it is the level-order traversal of some BST (and construct the BST itself).