Я пытаюсь решить упражнение, которое может быть немного сложным, так как я должен реализовать приоритетную очередь, начиная с класса шаблона дерева (типа RedBlack или BinarySearch Tree).Деревья и очереди приоритетов
Используя шаблон, который выглядит как
class Node
int key
Node left
Node right
Node parent
int leftNodes
int rightNodes
Первоначально, когда я должен был вставить новый элемент Я попытался полностью заполнять уровень дерева, а затем, используя алгоритм InOrderTreeTRaversal/сортировки заполнения массива и генераторную дерево BinarySearch из этого массива и замену новым корневым элементом оригинальным. Предположим, что в результате получилось сбалансированное дерево.
К сожалению, этот подход представляется нецелесообразным, поскольку дерево должно эмулировать свойство maxheap сохраняя сбалансированные вал для каждой вставки/удаления (и мой код не работает хорошо, при заполнении полностью уровня дерева). Возможно ли реализовать возможности «Дерево с кучей»? Я имею в виду дерево, для которого каждый элемент больше или равен его дочерним элементам, остается сбалансированным после вставки и имеет возможности автобаланса при удалении корневого узла (большего элемента ключа)?
[Red Black Tree] (http://en.wikipedia.org/wiki/Red%E2%80%93black_tree) - это то, что вы ищете. –
Использование дерева RedBlack можно иметь на дереве элемент, упорядоченный по значению? Ротация структуры при добавлении или удалении свинца в неупорядоченное дерево. Мне нужно иметь самый большой элемент на корневом уровне и уровне на уровне узла меньше или равно его родительскому. – Daved