Только что узнал о новом клевом дереве поиска :-)
Хочу поделиться. Если баян, расскажите, где можно было об этом почитать..
Для понимания лучше, если вы знаете, что такое AVL-дерево :-),
[http://ru.wikipedia.org/wiki/АВЛ-дерево|http://ru.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE]
Мысль #1:
Большое вращение в AVL в точности = 2 малых вращения, поэтому реализовывать его не нужно.
Мысль #2:
Один из минусов AVL-я = мы храним какой-то там balance (высоту), хотя гораздо полезнее хранить size поддерева - он хотя бы реально нужен для выполнения запросов типа "k-й элемент".
Инвариант AVL:
abs(T.left.h - T.right.h) <= 1
Новый клевый инвариант:
T.left.size >= T.right.left.size и T.right.right.size,
T.right.size >= T.left.left.size и T.left.right.size
(h - высота, size - размер поддерева)
Как мы будем балансировать:
Если после добавления в какой-то вершине инвариант не выполнен, делаем вращение. Процедура рекурсивная.
Рассмотрим один пример: T.left.left.size > T.right.size, тогда делаем малое вращение, которое в корень ставит T.left
Рассмотрим 2-й пример: T.left.right.size > T.right.size, тогда делаем большое вращение (т.е. 2 малых), которое в корень ставит T.left.right
В обоих примерах процедуру корректировки рекурсивно вызываем ото всех вершин, в сбаллансированности которых мы не уверены.
Почему процесс быстро работает?
1) из инварианта про size следует, что max глубина = O(logN)
2) рассмотрим величину "сумма всех глубин", она при добавлении увеличивается на O(logN), т.е. в сумме не более NlogN, а каждое вращение, посмотрите внимательно, уменьшает ее хотя бы на 1. Т.е. суммарное число вращний после N добавлений не более NlogN.
Мысль #3:
По слухам, по скорости (добавление и удаление, размер дерева 10^6) это дерево рвет RB-tree, Treap, AVL, Splay, 2-3-Tree, RBST, в общем все, что я знаю :-)
Хочу поделиться. Если баян, расскажите, где можно было об этом почитать..
Для понимания лучше, если вы знаете, что такое AVL-дерево :-),
[http://ru.wikipedia.org/wiki/АВЛ-дерево|http://ru.wikipedia.org/wiki/%D0%90%D0%92%D0%9B-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE]
Мысль #1:
Большое вращение в AVL в точности = 2 малых вращения, поэтому реализовывать его не нужно.
Мысль #2:
Один из минусов AVL-я = мы храним какой-то там balance (высоту), хотя гораздо полезнее хранить size поддерева - он хотя бы реально нужен для выполнения запросов типа "k-й элемент".
Инвариант AVL:
abs(T.left.h - T.right.h) <= 1
Новый клевый инвариант:
T.left.size >= T.right.left.size и T.right.right.size,
T.right.size >= T.left.left.size и T.left.right.size
(h - высота, size - размер поддерева)
Как мы будем балансировать:
Если после добавления в какой-то вершине инвариант не выполнен, делаем вращение. Процедура рекурсивная.
Рассмотрим один пример: T.left.left.size > T.right.size, тогда делаем малое вращение, которое в корень ставит T.left
Рассмотрим 2-й пример: T.left.right.size > T.right.size, тогда делаем большое вращение (т.е. 2 малых), которое в корень ставит T.left.right
В обоих примерах процедуру корректировки рекурсивно вызываем ото всех вершин, в сбаллансированности которых мы не уверены.
Почему процесс быстро работает?
1) из инварианта про size следует, что max глубина = O(logN)
2) рассмотрим величину "сумма всех глубин", она при добавлении увеличивается на O(logN), т.е. в сумме не более NlogN, а каждое вращение, посмотрите внимательно, уменьшает ее хотя бы на 1. Т.е. суммарное число вращний после N добавлений не более NlogN.
Мысль #3:
По слухам, по скорости (добавление и удаление, размер дерева 10^6) это дерево рвет RB-tree, Treap, AVL, Splay, 2-3-Tree, RBST, в общем все, что я знаю :-)
Just found out about the new cool search tree :-)
I want to share. If the button accordion, tell me where it was possible to read about it ..
For understanding it is better if you know what an AVL tree is :-),
[http://www.wikipedia.org/wiki/AVL-treevo|http://ru.wikipedia.org/wiki/%D0%90% D0% 92% D0% 9B-% D0% B4% D0% B5 % D1% 80% D0% B5% D0% B2% D0% BE]
Thought # 1:
A large rotation in AVL is exactly = 2 small rotations, so you do not need to implement it.
Thought # 2:
One of the minuses of AVL-I = we store some kind of balance (height), although it is much more useful to keep the size of the subtree - it is at least really needed to fulfill requests of the type "k-th element".
Invariant AVL:
abs (T.left.h - T.right.h) <= 1
New cool invariant:
T.left.size> = T.right.left.size and T.right.right.size,
T.right.size> = T.left.left.size and T.left.right.size
(h - height, size - size of the subtree)
How we will balance:
If after adding to some vertex the invariant is not fulfilled, we make rotation. The procedure is recursive.
Consider one example: T.left.left.size> T.right.size, then do a small rotation, which puts T.left at the root
Consider the 2nd example: T.left.right.size> T.right.size, then we make a big rotation (i.e. 2 small), which puts T.left.right in the root
In both examples, the adjustment procedure is recursively called from all vertices, in the balance of which we are not sure.
Why does the process work fast?
1) from the invariant about size, it follows that max depth = O (logN)
2) consider the value of "the sum of all depths", it increases when added by O (logN), i.e. in the amount of not more than NlogN, and each rotation, look carefully, reduces it by at least 1. That is, the total number of rotations after N additions is no more than NlogN.
Thought # 3:
According to rumors, by speed (add and delete, tree size 10 ^ 6) this tree tears the RB-tree, Treap, AVL, Splay, 2-3-Tree, RBST, in general, everything I know :-)
I want to share. If the button accordion, tell me where it was possible to read about it ..
For understanding it is better if you know what an AVL tree is :-),
[http://www.wikipedia.org/wiki/AVL-treevo|http://ru.wikipedia.org/wiki/%D0%90% D0% 92% D0% 9B-% D0% B4% D0% B5 % D1% 80% D0% B5% D0% B2% D0% BE]
Thought # 1:
A large rotation in AVL is exactly = 2 small rotations, so you do not need to implement it.
Thought # 2:
One of the minuses of AVL-I = we store some kind of balance (height), although it is much more useful to keep the size of the subtree - it is at least really needed to fulfill requests of the type "k-th element".
Invariant AVL:
abs (T.left.h - T.right.h) <= 1
New cool invariant:
T.left.size> = T.right.left.size and T.right.right.size,
T.right.size> = T.left.left.size and T.left.right.size
(h - height, size - size of the subtree)
How we will balance:
If after adding to some vertex the invariant is not fulfilled, we make rotation. The procedure is recursive.
Consider one example: T.left.left.size> T.right.size, then do a small rotation, which puts T.left at the root
Consider the 2nd example: T.left.right.size> T.right.size, then we make a big rotation (i.e. 2 small), which puts T.left.right in the root
In both examples, the adjustment procedure is recursively called from all vertices, in the balance of which we are not sure.
Why does the process work fast?
1) from the invariant about size, it follows that max depth = O (logN)
2) consider the value of "the sum of all depths", it increases when added by O (logN), i.e. in the amount of not more than NlogN, and each rotation, look carefully, reduces it by at least 1. That is, the total number of rotations after N additions is no more than NlogN.
Thought # 3:
According to rumors, by speed (add and delete, tree size 10 ^ 6) this tree tears the RB-tree, Treap, AVL, Splay, 2-3-Tree, RBST, in general, everything I know :-)
У записи 39 лайков,
9 репостов.
9 репостов.
Эту запись оставил(а) на своей стене Sergey Kopeliovich
