Итерация по двоичному дереву с O(1) вспомогательным пространством
Можно ли перебирать двоичное дерево в O(1) вспомогательном пространстве (без использования стека, очереди и т. Д.), Или это оказалось невозможным? Если это возможно, как это можно сделать?
Изменить: Ответы, которые я получил о том, что это возможно, если есть указатели на родительские узлы, интересны, и я не знал, что это можно сделать, но в зависимости от того, как вы на это смотрите, это может быть O(n) вспомогательным пространство. Кроме того, в моем случае практического использования нет указателей на родительские узлы. Пожалуйста, примите это во внимание при ответе.
11 ответов
Черт возьми, мне придется на самом деле напечатать это от Кнута. Это решение принадлежит Джозефу М. Моррису [ Инф. Proc. Письма 9 (1979), 197-200]. Насколько я могу судить, он запускается за время O(NlogN).
static void VisitInO1Memory (Node root, Action<Node> preorderVisitor) {
Node parent = root ;
Node right = null ;
Node curr ;
while (parent != null) {
curr = parent.left ;
if (curr != null) {
// search for thread
while (curr != right && curr.right != null)
curr = curr.right ;
if (curr != right) {
// insert thread
assert curr.right == null ;
curr.right = parent ;
preorderVisitor (parent) ;
parent = parent.left ;
continue ;
} else
// remove thread, left subtree of P already traversed
// this restores the node to original state
curr.right = null ;
} else
preorderVisitor (parent) ;
right = parent ;
parent = parent.right ;
}
}
class Node
{
public Node left ;
public Node right ;
}
Это возможно, если у вас есть ссылка на родителя у каждого ребенка. Когда вы встретите ребенка, посетите левое поддерево. При возвращении проверьте, не являетесь ли вы левым потомком своего родителя. Если так, посетите правильное поддерево. В противном случае продолжайте идти вверх, пока вы не оставите ребенка или пока не достигнете корня дерева.
В этом примере размер стека остается постоянным, поэтому дополнительная память не используется. Конечно, как отметил Мерад, ссылки на родителей можно рассматривать как пространство O(n), но это скорее свойство дерева, чем свойство алгоритма.
Если вас не волнует порядок, в котором вы проходите дерево, вы можете назначить интегральное отображение для узлов, где корень равен 1, потомки корня равны 2 и 3, потомки тех 4, 5, 6, 7 и т. Д. Затем вы перебираете каждую строку дерева, увеличивая счетчик и получая доступ к этому узлу по его числовому значению. Вы можете отслеживать максимально возможный дочерний элемент и останавливать цикл, когда ваш счетчик пропустит его. С точки зрения времени, это крайне неэффективный алгоритм, но я думаю, что он занимает O(1) место.
(Я позаимствовал идею нумерации из кучи. Если у вас есть узел N, вы можете найти детей в 2N и 2N+1. Вы можете работать в обратном направлении от этого номера, чтобы найти родителя ребенка.)
Вот пример этого алгоритма в действии на C. Обратите внимание, что нет malloc'ов, кроме как для создания дерева, и что нет рекурсивных функций, что означает, что стек занимает постоянное место:
#include <stdio.h>
#include <stdlib.h>
typedef struct tree
{
int value;
struct tree *left, *right;
} tree;
tree *maketree(int value, tree *left, tree *right)
{
tree *ret = malloc(sizeof(tree));
ret->value = value;
ret->left = left;
ret->right = right;
return ret;
}
int nextstep(int current, int desired)
{
while (desired > 2*current+1)
desired /= 2;
return desired % 2;
}
tree *seek(tree *root, int desired)
{
int currentid; currentid = 1;
while (currentid != desired)
{
if (nextstep(currentid, desired))
if (root->right)
{
currentid = 2*currentid+1;
root = root->right;
}
else
return NULL;
else
if (root->left)
{
currentid = 2*currentid;
root = root->left;
}
else
return NULL;
}
return root;
}
void traverse(tree *root)
{
int counter; counter = 1; /* main loop counter */
/* next = maximum id of next child; if we pass this, we're done */
int next; next = 1;
tree *current;
while (next >= counter)
{
current = seek(root, counter);
if (current)
{
if (current->left || current->right)
next = 2*counter+1;
/* printing to show we've been here */
printf("%i\n", current->value);
}
counter++;
}
}
int main()
{
tree *root1 =
maketree(1, maketree(2, maketree(3, NULL, NULL),
maketree(4, NULL, NULL)),
maketree(5, maketree(6, NULL, NULL),
maketree(7, NULL, NULL)));
tree *root2 =
maketree(1, maketree(2, maketree(3,
maketree(4, NULL, NULL), NULL), NULL), NULL);
tree *root3 =
maketree(1, NULL, maketree(2, NULL, maketree(3, NULL,
maketree(4, NULL, NULL))));
printf("doing root1:\n");
traverse(root1);
printf("\ndoing root2:\n");
traverse(root2);
printf("\ndoing root3:\n");
traverse(root3);
}
Я прошу прощения за качество кода - это в значительной степени доказательство концепции. Кроме того, время выполнения этого алгоритма не является идеальным, поскольку он выполняет большую работу, чтобы компенсировать неспособность поддерживать какую-либо информацию о состоянии. С положительной стороны, это соответствует требованиям алгоритма пространства O(1) для доступа в любом порядке к элементам дерева, не требуя дочерних родительских ссылок или изменения структуры дерева.
Вы можете сделать это разрушительно, разъединяя каждый лист по ходу дела. Это может быть применимо в определенных ситуациях, например, когда вам больше не нужно дерево.
Расширяя, вы можете построить другое двоичное дерево, уничтожив первое. Вам понадобится некоторое микроуправление памятью, чтобы убедиться, что пиковая память никогда не превышает размер исходного дерева плюс небольшая константа. Это, вероятно, будет иметь некоторые вычислительные затраты.
РЕДАКТИРОВАТЬ: Есть способ! Вы можете использовать сами узлы, чтобы осветить путь назад по дереву, временно перевернув их. Когда вы посещаете узел, вы указываете его left-child указатель на его родителя, его right-child указатель на последний раз, когда вы сделали правый поворот на вашем пути (который можно найти в родительском right-child указатель на данный момент), и сохраните его реальных потомков либо в теперь избыточных родительских right-child указатель или в вашем состоянии обхода соотв. следующий посетил детский left-child указатель. Вам нужно сохранить некоторые указатели на текущий узел и его окрестности, но ничего "нелокального". Когда вы вернетесь к дереву, вы полностью измените процесс.
Я надеюсь, что смогу прояснить это как-нибудь; это всего лишь грубый набросок. Вам придется где-то искать это (я уверен, что это упоминается где-то в "Искусстве компьютерного программирования").
Сохранить дерево и использовать только пробел O(1) возможно, если...
- Каждый узел имеет фиксированный размер.
- Все дерево находится в непрерывной части памяти (т.е. массив)
- Вы не перебираете дерево, вы просто перебираете массив
Или если вы уничтожите дерево в процессе его обработки...:
- @Svante выступил с этой идеей, но я хотел немного рассказать о нем, используя деструктивный подход.
- Как? Вы можете продолжать брать самый левый листовой узел в дереве (for(;;) node = node->left и т. Д...., затем обрабатывать его, а затем удалять. Если самый левый узел в дереве не является листовым узлом, then you process and delete the right node's left most leaf node. If a right node has no children, then you process and delete it.
Ways that it wouldn't work...
If you use recursion you will use a stack implicitly. For some algorithms (not for this problem) tail recursion would allow you to use recursion and have O(1) space, but since any particular node may have several children, and hence there is work to do after the recursive call, O(1) space tail recursion is not possible.
You could try to tackle the problem 1 level at a time, but there is no way to access an arbitrary level's nodes without auxiliary (implicit or explicit) space. For example you could recurse to find the node you want, but then that takes implicit stack space. Or you could store all your nodes in another data structure per level, but that takes extra space too.
"Источники данных и их алгоритмы" Гарри Льюиса и Ларри Дененберга описывают обход инверсии связей для постоянного обхода пространства двоичного дерева. Для этого вам не нужен родительский указатель на каждом узле. Обход использует существующие указатели в дереве для хранения пути для отслеживания назад. Требуется 2-3 дополнительных ссылки на узлы. Плюс немного на каждом узле, чтобы отслеживать направление прохождения (вверх или вниз) при движении вниз. В моей реализации этих алгоритмов из книги профилирование показывает, что этот обход имеет гораздо меньше памяти / процессорного времени. Реализация в Java здесь.
Указатели от узлов к их предкам могут иметь дополнительное хранилище (ну, два бита на узел), используя структуру, называемую многопоточным деревом. В многопоточном дереве нулевые ссылки представлены битом состояния, а не нулевым указателем. Затем вы можете заменить нулевые ссылки указателями на другие узлы: левые ссылки указывают на узел-преемник в обходе inorder, а правые ссылки на предшественник. Вот диаграмма в Юникоде (X представляет узел заголовка, используемый для управления деревом):
╭─┬────────────────────────────────────────╮
╭───────────────────────── ▶ ┏━━━┯━━━┯━━ ▼ ┓│ │
│ ╭─╂─ │ X │ ─╂╯ │
│ ▼ ┗━━━┷━━━┷━━━┛ │
│ ┏━━━┯━━━┯━━━┓ │
│ ╭────╂─ │ A │ ─╂──╮ │
│ ▼ ┗━━━┷━━━┷━━━┛ │ │
▲ ┏━━━┯━━━┯━━━┓ ▲ │ ┏━━━┯━━━┯━━━┓ │
│ ╭─╂─ │ B │ ─╂────┤ ├────────╂─ │ C │ ─╂───────╮ │
│ ▼ ┗━━━┷━━━┷━━━┛ │ ▼ ┗━━━┷━━━┷━━━┛ ▼ │
▲ ▲ │ ┏━━━┯━━━┯━━━┓ ▲ ┏━━━┯━━━┯━━━┓ │
╰╂─ │ D │ ─╂─╯ ╰───╂ │ E │ ─╂╮ │ ╭╂─ │ F │ ─╂╮ │
┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛▼ │ ▼┗━━━┷━━━┷━━━┛▼ │
▲ ┏━━━┯━━━┯━━━┓ │ ┏━━━┯━━━┯━━━┓ ▲ ┏━━━┯━━━┯━━━┓│
╰─╂─ │ G │ ╂──┴─╂─ │ H │ ─╂─┴─╂─ │ J │ ─╂╯
┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛ ┗━━━┷━━━┷━━━┛
Если у вас есть структура, выполнить обход по порядку очень и очень просто:
Inorder-наследник (p)
р указывает на узел. Эта процедура находит преемника р в
обход по порядку и возвращает указатель на этот узел
q ← p. право
Если p.rtag = 0, то
Пока q.ltag = 0 Do
q ← q.left
Конец пока
Конец, если
Возврат q
Много дополнительной информации о резьбовых деревьях можно найти в Art of Programming Program Ch.2 §3.1 или разбросано по всему Интернету.
Вы можете достичь этого, если узлы имеют указатели на своих родителей. Когда вы идете обратно вверх по дереву (используя родительские указатели), вы также проходите узел, с которого пришли. Если узел, с которого вы исходите, является левым дочерним узлом того узла, на котором вы сейчас находитесь, то вы пересекаете правый дочерний узел. В противном случае вы вернетесь к его родителю.
РЕДАКТИРОВАТЬ в ответ на редактирование в вопросе: Если вы хотите выполнить итерацию по всему дереву, то нет, это невозможно. Чтобы залезть обратно на дерево, нужно знать, куда идти. Однако, если вы просто хотите пройтись по одному пути вниз по дереву, это может быть достигнуто в O(1) дополнительном пространстве. Просто итерируйте дерево, используя цикл while, сохраняя один указатель на текущий узел. Продолжайте вниз по дереву, пока не найдете нужный узел или не достигнете конечного узла.
РЕДАКТИРОВАТЬ: Вот код для первого алгоритма (проверьте функцию iterate_constant_space() и сравните с результатами стандартной функции iterate()):
#include <cstdio>
#include <string>
using namespace std;
/* Implementation of a binary search tree. Nodes are ordered by key, but also
* store some data.
*/
struct BinarySearchTree {
int key; // they key by which nodes are ordered
string data; // the data stored in nodes
BinarySearchTree *parent, *left, *right; // parent, left and right subtrees
/* Initialise the root
*/
BinarySearchTree(int k, string d, BinarySearchTree *p = NULL)
: key(k), data(d), parent(p), left(NULL), right(NULL) {};
/* Insert some data
*/
void insert(int k, string d);
/* Searches for a node with the given key. Returns the corresponding data
* if found, otherwise returns None."""
*/
string search(int k);
void iterate();
void iterate_constant_space();
void visit();
};
void BinarySearchTree::insert(int k, string d) {
if (k <= key) { // Insert into left subtree
if (left == NULL)
// Left subtree doesn't exist yet, create it
left = new BinarySearchTree(k, d, this);
else
// Left subtree exists, insert into it
left->insert(k, d);
} else { // Insert into right subtree, similar to above
if (right == NULL)
right = new BinarySearchTree(k, d, this);
else
right->insert(k, d);
}
}
string BinarySearchTree::search(int k) {
if (k == key) // Key is in this node
return data;
else if (k < key && left) // Key would be in left subtree, which exists
return left->search(k); // Recursive search
else if (k > key && right)
return right->search(k);
return "NULL";
}
void BinarySearchTree::visit() {
printf("Visiting node %d storing data %s\n", key, data.c_str());
}
void BinarySearchTree::iterate() {
visit();
if (left) left->iterate();
if (right) right->iterate();
}
void BinarySearchTree::iterate_constant_space() {
BinarySearchTree *current = this, *from = NULL;
current->visit();
while (current != this || from == NULL) {
while (current->left) {
current = current->left;
current->visit();
}
if (current->right) {
current = current->right;
current->visit();
continue;
}
from = current;
current = current->parent;
if (from == current->left) {
current = current->right;
current->visit();
} else {
while (from != current->left && current != this) {
from = current;
current = current->parent;
}
if (current == this && from == current->left && current->right) {
current = current->right;
current->visit();
}
}
}
}
int main() {
BinarySearchTree tree(5, "five");
tree.insert(7, "seven");
tree.insert(9, "nine");
tree.insert(1, "one");
tree.insert(2, "two");
printf("%s\n", tree.search(3).c_str());
printf("%s\n", tree.search(1).c_str());
printf("%s\n", tree.search(9).c_str());
// Duplicate keys produce unexpected results
tree.insert(7, "second seven");
printf("%s\n", tree.search(7).c_str());
printf("Normal iteration:\n");
tree.iterate();
printf("Constant space iteration:\n");
tree.iterate_constant_space();
}
http://en.wikipedia.org/wiki/XOR_linked_list
закодировать ваш родительский узел в указатели листа
Да, это возможно. Вот мой пример итерации, которая имеет временную сложность O(n) и пространственную сложность O (1).
using System;
public class Program
{
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public static void Main()
{
TreeNode left = new TreeNode(1);
TreeNode right = new TreeNode(3);
TreeNode root = new TreeNode(2, left, right);
TreeNode previous = null;
TreeNode current = root;
TreeNode newCurrent = null;
while(current != null) {
if(current.left == null) {
if(current.right == null) {
if(previous == null) {
Console.WriteLine(current.val);
break;
}
Console.WriteLine(current.val);
current = previous;
previous = previous.left;
current.left = null;
} else {
newCurrent = current.right;
current.right = null;
current.left = previous;
previous = current;
current = newCurrent;
}
} else {
newCurrent = current.left;
current.left = previous;
previous = current;
current = newCurrent;
}
}
}
}
Каждый раз, когда вы видите
Я думаю, что вы никак не могли бы это сделать, так как вы должны каким-то образом найти узлы, на которых вы остановились на пути, и определить, что вам всегда нужно пространство O(высота).
Можно ли перебирать двоичное дерево в O(1) вспомогательном пространстве.
struct node { node * father, * right, * left; int value; };
Эта структура позволит вам двигаться на 1 шаг в любом направлении через двоичное дерево.
Но все же в итерации вам нужно идти по пути!