288
правок
Изменения
→Реализация персистентных массивом в виде сбалансированных деревьев
Решающим моментом является то, что мы допускаем множественные ссылки на одно и то же поддерево: хотя концептуальное представление постоянных массивов - ориентированные деревья, их представление в памяти различно. Мы допускаем, что узел может быть преемником многих разных узлов.
{{Определение|definition= Пусть X - некоторое множество. Бинарное дерево с несколькими ссылками по на X является кортежем B = (N, L, R) с L∩R = 0 /, L, R ⊆ N × N, таким, что
* (N, L∪R) является '''корневым ациклическим ориентированным графом ''' с узлами N, ребрами L∪R.
* В каждом из двух подграфов (N, L) и (N, R) каждый узел имеет '''не более одного прямого преемника '''.
*Узлы без каких-либо преемников (листья B) должны быть все элементами X.
}}
Дано двоичное дерево с несколькими ссылками B = (N,L,R) и узел ''p'' ∈ N. Пишут LEFT(''p'') = ''q'', если ''q'' является единственным приемником ''p'' в(N,L) и, если такого ''q'' не существует, пишем LEFT(''p'')= ⊥, предполагая, что ⊥ не содержит N. Аналогично, пишут RIGHT(p) = ''q'', если q является единственным приемником p в(N,R) и, если такого q не существует, пишем RIGHT(''p'')= ⊥. Мы будем называть LEFT (''p'') левым дочерним элементом p и RIGHT (''p'') правым дочерним элементом.
В B = (N, L∪R) узел ''p'' ∈ N может иметь много прямых предшественников ''q''. Тогда ребра (''q'', ''p'') ∈ E называют ссылками от q до p.
