История изменений
Исправление dimgel, (текущая версия) :
Мысли читаешь. :) За исключением того, что куча походу таки-лучше потому что:
- ближайший к извлечению узел - уже в корне, не надо его дополнительно искать;
- меньше ограничений на упорядоченность дочерних узлов, значит больше возможностей химичить (что я и попытался было выше).
Насчёт увеличить число потомков узла – тоже прикидываю, но главным образом с целью не перетасовывать всё дерево при каждом извлечении элемента, а опять же – допускать узлы-пустышки на каждом уровне чтобы потом редуцировать смежные пустышки, не перелопачивая всё дерево; типа такого (но ещё недодумал):
1 take min X X X 3 free, compress 4
2 3 -------> 2 3 ---> X 3 ---> X X ===============> 5 6
4 5 6 4 5 6 4 5 6 4 5 6
В случае увеличения числа потомков (я начал было рисовать на бумажке 3 а не 4), логика сжатия может оказаться проще (а может и не оказаться).
UPD. На этой схеме фигня нарисована: дети 4-ки теряются. Поэтому и начал думать в сторону широких узлов. Хотя зреет ощущение, что и они не помогут, т.к. принципиально не устраняют этой проблемы.
Исправление dimgel, :
Мысли читаешь. :) За исключением того, что куча походу таки-лучше потому что:
- ближайший к извлечению узел - уже в корне, не надо его дополнительно искать;
- меньше ограничений на упорядоченность дочерних узлов, значит больше возможностей химичить (что я и попытался было выше).
Насчёт увеличить число потомков узла – тоже прикидываю, но главным образом с целью не перетасовывать всё дерево при каждом извлечении элемента, а опять же – допускать узлы-пустышки на каждом уровне чтобы потом редуцировать смежные пустышки, не перелопачивая всё дерево; типа такого (но ещё недодумал):
1 take root X X X 3 free, compress 4
2 3 --------> 2 3 ---> X 3 ---> X X ===============> 5 6
4 5 6 4 5 6 4 5 6 4 5 6
В случае увеличения числа потомков (я начал было рисовать на бумажке 3 а не 4), логика сжатия может оказаться проще (а может и не оказаться).
UPD. На этой схеме фигня нарисована: дети 4-ки теряются. Поэтому и начал думать в сторону широких узлов. Хотя зреет ощущение, что и они не помогут, т.к. принципиально не устраняют этой проблемы.
Исправление dimgel, :
Мысли читаешь. :) За исключением того, что куча походу таки-лучше потому что:
- ближайший к извлечению узел - уже в корне, не надо его дополнительно искать;
- меньше ограничений на упорядоченность дочерних узлов, значит больше возможностей химичить (что я и попытался было выше).
Насчёт увеличить число потомков узла – тоже прикидываю, но главным образом с целью не перетасовывать всё дерево при каждом извлечении элемента, а опять же – допускать узлы-пустышки на каждом уровне чтобы потом редуцировать смежные пустышки, не перелопачивая всё дерево; типа такого (но ещё недодумал):
1 take root X X X 3 free, compress 4
2 3 --------> 2 3 ---> X 3 ---> X X ===============> 5 6
4 5 6 4 5 6 4 5 6 4 5 6
В случае увеличения числа потомков (я начал было рисовать на бумажке 3 а не 4), логика сжатия может оказаться проще (а может и не оказаться).
UPD. На этой схеме фигня нарисована: дети 4-ки теряются. Поэтому и начал думать в сторону широких узлов.
Исправление dimgel, :
Мысли читаешь. :) За исключением того, что куча походу таки-лучше потому что:
- ближайший к извлечению узел - уже в корне, не надо его дополнительно искать;
- меньше ограничений на упорядоченность дочерних узлов, значит больше возможностей химичить (что я и попытался было выше).
Насчёт увеличить число потомков узла – тоже прикидываю, но главным образом с целью не перетасовывать всё дерево при каждом извлечении элемента, а опять же – допускать узлы-пустышки на каждом уровне чтобы потом редуцировать смежные пустышки, не перелопачивая всё дерево; типа такого (но ещё недодумал):
1 take root X X X 3 free, compress 4
2 3 --------> 2 3 ---> X 3 ---> X X ===============> 5 6
4 5 6 4 5 6 4 5 6 4 5 6
В случае увеличения числа потомков (я начал было рисовать на бумажке 3 а не 4), логика сжатия может оказаться проще (а может и не оказаться).
Исправление dimgel, :
Мысли читаешь. :) За исключением того, что куча походу таки-лучше потому что:
- ближайший к извлечению узел - уже в корне, не надо его дополнительно искать;
- меньше ограничений на упорядоченность дочерних узлов, значит больше возможностей химичить (что я и попытался было выше).
Насчёт увеличить число потомков узла – тоже прикидываю, но главным образом с целью не перетасовывать всё дерево при каждом извлечении элемента, а опять же – допускать узлы-пустышки на каждом уровне чтобы потом редуцировать смежные пустышки, не перелопачивая всё дерево; типа такого (но ещё недодумал):
1 take root X X X 3 free, compress 4
2 3 --------> 2 3 ---> X 3 ---> X X ===============> 5 6
4 5 6 4 5 6 4 5 6 4 5 6
Исправление dimgel, :
Мысли читаешь. :) За исключением того, что куча походу таки-лучше потому что:
- ближайший к извлечению узел - уже в корне, не надо его дополнительно искать;
- меньше ограничений на упорядоченность дочерних узлов, значит больше возможностей химичить (что я и попытался было выше).
Насчёт увеличить число потомков узла – тоже прикидываю, но главным образом с целью не перетасовывать всё дерево при каждом извлечении элемента, а опять же – допускать узлы-пустышки на каждом уровне чтобы потом редуцировать смежные пустышки, типа такого (но ещё недодумал):
1 take root X X X 3 free, compress 4
2 3 --------> 2 3 ---> X 3 ---> X X ===============> 5 6
4 5 6 4 5 6 4 5 6 4 5 6
Исправление dimgel, :
Мысли читаешь. :) За исключением того, что куча походу таки-лучше потому что:
- ближайший к извлечению узел - уже в корне, не надо его дополнительно искать;
- меньше ограничений на упорядоченность дочерних узлов, значит больше возможностей химичить (что я и попытался было выше).
Насчёт увеличить число потомков узла – тоже прикидываю, но главным образом с целью не перетасовывать всё дерево при каждом извлечении элемента, а опять же – допускать узлы-пустышки на каждом уровне чтобы потом редуцировать смежные пустышки, типа такого (но ещё недодумал):
1 take root X X X 3 free compress, 4
2 3 --------> 2 3 ---> X 3 ---> X X ===============> 5 6
4 5 6 4 5 6 4 5 6 4 5 6
Исправление dimgel, :
Мысли читаешь. :) За исключением того, что куча походу таки-лучше потому что:
- ближайший к извлечению узел - уже в корне, не надо его дополнительно искать;
- меньше ограничений на упорядоченность дочерних узлов, значит больше возможностей химичить (что я и попытался было выше).
Насчёт увеличить число потомков узла – тоже прикидываю, но главным образом с целью не перетасовывать всё дерево при каждом извлечении элемента, а опять же – допускать узлы-пустышки на каждом уровне чтобы потом редуцировать смежные пустышки, типа такого (но ещё недодумал):
1 take root X X X 3 free compress 4
2 3 --------> 2 3 ---> X 3 ---> X X ===============> 5 6
4 5 6 4 5 6 4 5 6 4 5 6
Исходная версия dimgel, :
Мысли читаешь. :) За исключением того, что куча походу таки-лучше потому что:
- ближайший к извлечению узел - уже в корне, не надо его дополнительно искать;
- меньше ограничений на упорядоченность дочерних узлов, значит больше возможностей химичить (что я и попытался было выше).
Насчёт увеличить число потомков узла – тоже прикидываю, но главным образом с целью не перетасовывать всё дерево при каждом извлечении элемента, а опять же – допускать узлы-пустышки на каждом уровне чтобы потом редуцировать смежные пустышки, типа такого (но ещё недодумал):
1 take root X X X 4
2 3 --------> 2 3 ---> X 3 ---> X X ==> 5 6
4 5 6 4 5 6 4 5 6 4 5 6