143
правки
Изменения
→Вставка элемента
[[Файл:23treesearch.png|border]]
=== Вставка элемента === *<tex>x</tex> - искомое значение.*<tex>t</tex> - текущая вершина в дереве. Изначально <tex>t = \mathtt{root}</tex>Если корня не существует {{---}} дерево пустое, то новый элемент и будет корнем (одновременно и листом). Иначе поступим следующим образом: Найдем сперва, где бы находился элемент, применив search(x). Далее проверим есть ли у этого узла родитель, если его нет, то в дереве всего один элемент - лист. Возьмем этот лист и новый узел, и создадим для них родителя, лист и новый узел расположим в порядке возрастания. Если родитель существует, то подвесим к нему ещё одного сына. Если сыновей стало 4, то разделим родителя на два узла, и повторим разделение теперь для его родителя. splitParent('''Node''' t): '''if''' (t.length > 3) Node a; a.sons[0] = t.sons[2] a.sons[1] = t.sons[3] t.sons[2].parent = a t.sons[3].parent = a a.keys[0] = t.keys[2] a.length = 2 t.length = 2 t.sons[2] = '''null''' t.sons[3] = '''null''' '''if''' (t.parent != '''null''') t.parent[t.length] = a t.length++ сортируем сыновей у t.parent splitParent(t.parent) '''else''' //мы расщепили корень, надо подвесить его к общему родителю, который будет новым корнем Node t = root root.sons[0] = t root.sons[1] = a t.parent = root a.parent = root root.length = 2 сортируем сыновей у rootЕсли сыновей стало 3, то ничего не делаем. Далее необходимо восстановить ключи на пути от новой вершины до корня: updateKeys('''Node''' t): Node a = t.parent '''while''' (a != '''null''') '''for''' i = 0 .. a.length - 1 a.keys[i] = max(a.sons[i]) //max - возвращает максимальное значение в поддереве. a = a.parent //Примечание: max легко находить, если хранить максимум //правого поддерева в каждом узле {{---}} это значение и будет max(a.sons[i]) <tex>\mathtt{updateKeys}</tex> необходимо запускать от нового узла. Код для добавления: insert('''int''' x): Node n = Node(x) '''if''' (root == null) root = n return Node a = search(x) '''if''' (a.parent == '''null''') Node t = root root.sons[0] = t root.sons[1] = n t.parent = root n.parent = root root.length = 2 сортируем сыновей у root '''else''' Node p = a.parent p.sons[p.length] = n p.length++ n.parent = p сортируем сыновей у p split(n) updateKeys(n)
=== Удаление элемента ===
