^$h@\'\'rK# :) написал(а):

у вершины два целых значения

Это как?

озадачь любой поисковик по ключу 2-3 дерево
например (кратко)

2-3 деревья являются подвидом Б-деревьев и необходимы для эффективного хранения информации. Свойства 2-3 дерева: 1) любая ячейка имеет 2 или 3 листа; 2) любой элемент отстоит от вершины на одинаковом рассроянии. Высота 2-3 дерева лежит между log3n и log2n.

Для поиска необходимо последовательно просматривать ключи, хранящиеся в ячейках. Вначале ключ искомого элемента сравнивается с правым ключем ячейки и если наш ключ не меньше его, то идем в правое поддерево. Иначе сравниваем наш ключ с ключем в левой ячейке и если наш ключ не меньше его, то идем в среднее поддерево, иначе в правое поддерево. Таким образом доходим до нужного нам элемента.

Для ввода вначале реализуется алгоритм поиска для определения ячейки, сыном которой будет являться вставляемый элемент. Далее элемент вставляется в качестве сына найденной ячейки. Если у ячейки стало 3 сына, то сортируем их. Если же в результате вставки у ячейки стало 4 сына, что является нарушением свойства 1) 2-3 дерева, то делим эту ячейку на две, и смотрим не нарушились ли свойства дерева для отца образовавшихся ячеек. В случае, когда свойство 1) не выполняется в корне дерева, то делим корень на две ячейки и их отцом ставим новый сформированный корень.

Для удаления реализуем алгоритм поиска удаляемого элемента в дереве. После этого удаляем наш элемент, и смотрим выполнения свойств 2-3 дерева для его отца. Если свойства выполняются, то алгоритм удаления завершен. Если нет, то смотрим на братьев этой ячейки. Если у левого или правого брата три сына, то забираем один, и определяем его как сына нашей ячейки. Если же у братьев также по два сына, то передаем единственного сына ячейки одному из братьев, а ячейку удаляем. В последнем случае необходимо опять же проверить выполнение свойств 2-3 дерева для отца нашей ячейки. Если у корня дерева в ходе этих перемещений остался только один сын, то удаляем корень и обозначаем новым корнем его единственного сына.

хотя особенностью 2-3 дерева является сбалансированность, и если она тебе вовсе не нужна, тогда делай как utug написал

Исправлено Fatboy (04.10.07 10:46)