(Untitled)

[faceted_jacinth]

Quote of the day:

A single Nehalem chip today could easily generate four gigabytes per second of new garbage when running a classic enterprise workload.The text pointed by the link is very informative, though. It's about the Azul JVM and how they exploit virtual memory to create a "Pause less" concurrent garbage collector (truly pauseless in the

Comments

[fat_crocodile]

что значит "мутабельное"?

[faceted_jacinth]

Можно менять значения указателей в вершинах на что-нибудь другое. Но после обхода дерево должно остаться в первоначальном состоянии.

[fat_crocodile]

Тогда спускаясь вниз по ветке можно переставлять указатель на того ребёнка, который выбран так, что он указывает на родителя. А поднимаясь возвращать всё обратно. Помнить надо ровно один указатель -- на текущего родителя.

[faceted_jacinth]

> Тогда спускаясь вниз по ветке можно переставлять указатель на того ребёнка, который выбран так, что он указывает на родителя.

А вот в этом-то, батенька, и засада: совершенно непонятно, как определить, который из указателей на ребёнков на самом деле указывает на родителя, когда мы в очередной раз возвращаемся наверх.

[anonymous]

Можно же переподвесить дерево за root->left, отцепив от него root->left->right и прицепив его в качестве левого поддерева к старому корню. От этого inorder traversal не поменяется, а дерево таким образом рано или поздно кончится (в смысле что левых детей не останется, корень напечатаем и разберёмся с правым поддеревом по индукции).

[faceted_jacinth]

Нифига не понял что от чего переотцепляется, но идея в общем плодотворная: можно дерево линеаризовать: запоминаем рут и текущую вершину, на каждом шаге пересоединяем левого ребёнка текущей вершины как самого правого ребёнка вообще, и переходим к следующей правой вершине. Потом проходим из рута и печатаем.

Забыл сказать: после всего этого дерево должно остаться в первозданном виде.

[naoe_riki]

Генерить по очереди числа и пытаться дойти до той или иной вершины, идя из корня по очереди налево/направо в зависимости от того, очередной бит в числе ноль или единица? XD А допиливание заключается в обхождении случая, когда, например, дерево - не дерево, а типа список какой-нибудь, вытянутое всё?

[faceted_jacinth]

Не покатит -- числа в общем случае будут занимать O(ln(N)) памяти же. А нужно O(1).

[naoe_riki]

Может вот такое прокатывает решение?
Заходим в вершину current, там указатели L, R. У нас есть указатель на то, откуда пришли, P.
temp:=L; L:=R; R:=P; P:=current; current:=temp;
То есть как бы вначале в вершине родитель будет запомнен в правом указателе, а в левом - правый указатель. При этом мы пойдём налево, чего и хотим. Придя в следующий раз в эту вершину, мы снова пойдём по левому указателю, то есть в этот раз направо, и "циклически" передвинем указатели: указатель на родителя будет теперь храниться в левом, указатель на левую вершину в правом. Потом придём в третий раз в эту вершину и опять "циклически" передвинув указатели, они вернуться на свои места, а мы пойдём по тому, что у нас хранилось в левом указателе, то есть к родителю.

[fat_crocodile]

Супер! Очень красиво.
Не понятно только, как избежать тройной обработки узлов. Но может и не надо, повторение -- мать учения.

[yakness]

вот я и перестал понимать этот блог.

[mkal]

А можно сначала топологически отсортировать дерево по указателям, чтобы у корень был в узле с минимальным указателем, а по каждому пути указатели строго возрастали, а дальше уже обходить, сохраняя указатель на родителя в указателе на того сына, в который мы спустились. При подъёме легко понять, откуда мы пришли и куда идти дальше. Ну в конце можно корень на место вернуть, если это кому-то нужно. Остальные вершины, правда, в памяти перемешаются, т.е. указатели на внутренние вершины снаружи хранить нельзя будет.