История изменений
Исправление aist1, (текущая версия) :
И не только оно, а и большинство других деревьев. Без parent link сложно организовать итерацию по дереву. Там итератор должен хранить весь путь от корня до текущего элемента. В случае сбалансированных деревьев это вполне нормально, так как длина такого пути логарифмическая. А вот в общем случае – длина может быть и N. Так себе итератор получится.
Т.е. еще одна практически важная структура данных, оказывается, не DAG.
И если двусвязный список еще можно запихнуть в массив, и, тем самым, сделать вид, что «списки просто не нужны». То вот дерево в монолитный массив запихнуть будет сильно труднее. Кто хочет, может потренироваться. Такие схемы есть, но они все статические: добавление элемента – O(N).
Исходная версия aist1, :
И не только оно, а и большинство других деревьев. Без parent link сложно организовать итерацию по дереву. Там итератор должен хранить весь путь от корня до текущего элемента. В случае сбалансированных деревьев это вполне нормально, так как длина такого пути логарифмическая. А вот в общем случае – длина может быть и N. Так себе итератор получится.
Т.е. еще одна практически важная структура данных, оказывается, не DAG.