Итерация по двоичному дереву с O (1) Вспомогательным пространством

Ответ 1

Гез, мне придется набирать его из Кнута. Это решение принадлежит Джозефу М. Моррису [Inf. 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 ;
}

Ответ 2

Возможно, если у вас есть ссылка на родителя в каждом дочернем элементе. Когда вы сталкиваетесь с ребенком, перейдите в левое поддерево. Когда вы возвращаетесь, проверьте, являетесь ли вы левым ребенком вашего родителя. Если это так, посетите правое поддерево. В противном случае продолжайте движение вверх, пока вы не будете левым ребенком, или пока не нажмете корень дерева.

В этом примере размер стека остается постоянным, поэтому нет дополнительной памяти. Конечно, как отметил Мехрдад, ссылки на родителей можно рассматривать как O (n) пространство, но это скорее свойство дерева, чем свойство алгоритма.

Если вам не нужен порядок, в котором вы пересекаете дерево, вы можете назначить интегральное сопоставление для узлов, где корень равен 1, а у детей корня 2 и 3, дети из них равны 4, 5, 6, 7 и т.д. Затем вы прокручиваете каждую строку дерева, увеличивая счетчик и получая доступ к этому node по его числовому значению. Вы можете отслеживать наивысший возможный дочерний элемент и останавливать цикл, когда ваш счетчик передает его. По времени это крайне неэффективный алгоритм, но я думаю, что это занимает O (1) пространство.

(я заимствовал идею нумерации из куч. Если у вас есть node 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) для доступа в любом порядке элементов дерева, не требуя от родительских ссылок или изменения структуры дерева.

Ответ 3

Вы можете сделать это разрушительно, отрывая каждый лист, когда идете. Это может быть применимо в определенных ситуациях, т.е. Когда вам больше не понадобится дерево.

В дополнение, вы можете создать другое двоичное дерево, когда вы уничтожаете первый. Вам потребуется некоторое управление памятью, чтобы убедиться, что пиковая память никогда не превышает размер исходного дерева плюс, возможно, небольшая константа. Тем не менее, это может привести к некоторым вычислительным накладным расходам.

ИЗМЕНИТЬ: Есть способ! Вы можете сами использовать узлы, чтобы осветить путь назад к дереву, временно изменив их. По мере того, как вы посещаете node, вы указываете его указатель left-child на родителя, указатель right-child на последний раз, когда вы правильно включили свой путь (который должен быть найден в родительском указателе right-child в этот момент) и сохраните его реальных детей либо в текущем избыточном родительском указателе right-child, либо в вашем обходном состоянии соответственно. следующий указатель для детей left-child. Вам нужно сохранить некоторые указатели на текущий node и его окрестности, но ничего "нелокального". Когда вы возвращаетесь к дереву, вы меняете процесс.

Надеюсь, я смогу сделать это как-то ясным; это всего лишь приблизительный эскиз. Вам придется искать его где-нибудь (я уверен, что это упоминается где-то в "Искусстве программирования" ).

Ответ 4

Чтобы сохранить дерево и использовать только пространство O (1), это возможно, если...

• Каждый node является фиксированным размером.
• Все дерево находится в смежной части памяти (т.е. массиве)
• Вы не перебираете дерево, вы просто перебираете массив

Или, если вы уничтожаете дерево при его обработке...:

• @Svante придумал эту идею, но я хотел немного расширить как, используя деструктивный подход.
• Как? Вы можете продолжать использовать левый лист node в дереве (for (;;) node= node → left и т.д., Затем обработать его, а затем удалить его Если левый node в дереве не является листом node, тогда вы обрабатываете и удаляете правый node самый левый лист node. Если в правом node нет дочерних элементов, вы обрабатываете и удаляете это.

Пути, что это не сработает...

Если вы используете рекурсию, вы будете использовать стек неявно. Для некоторых алгоритмов (не для этой проблемы) хвостовая рекурсия позволит вам использовать рекурсию и иметь O (1) пространство, но так как любой конкретный node может иметь несколько дочерних элементов, и, следовательно, после рекурсивного вызова есть работа, O (1) рекурсия космического хвоста невозможна.

Вы можете попытаться решить проблему 1 уровня за раз, но нет способа получить доступ к узлам произвольного уровня без вспомогательного (неявного или явного) пространства. Например, вы можете реорганизовать, чтобы найти node, который вы хотите, но затем он занимает неявное пространство стека. Или вы можете хранить все свои узлы в другой структуре данных на уровне, но это занимает дополнительное пространство.

Ответ 5

Вы можете достичь этого, если узлы имеют указатели на своих родителей. Когда вы возвращаетесь назад к дереву (используя родительские указатели), вы также передаете node, из которого вы пришли. Если вы выбрали node - это левый дочерний элемент node, на котором вы сейчас находитесь, вы переходите к правильному ребенку. В противном случае вы возвращаетесь к нему родительским.

ИЗМЕНИТЬ в ответ на редактирование в вопросе: если вы хотите итерации по всему дереву, то это невозможно. Чтобы подняться по дереву, вам нужно знать, куда идти. Однако, если вы просто хотите итерации по одному пути вниз по дереву, то это может быть достигнуто в O (1) дополнительном пространстве. Просто повторяйте дерево, используя цикл while, сохраняя единственный указатель на текущий node. Продолжайте движение вниз по дереву, пока не найдете нужный node или нажмите лист node.

EDIT: Здесь код для первого алгоритма (проверьте функцию 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();
}

Ответ 6

Указатели от узлов к их предкам могут быть получены без дополнительного (хорошо, двух бит на node) дополнительного хранилища с использованием структуры, называемой резьбовым деревом. В потоковом дереве нулевые ссылки представлены бит состояния, а не нулевой указатель. Затем вы можете заменить нулевые ссылки указателями на другие узлы: левые ссылки указывают на преемника node в обходном пути и правильные ссылки на предшественника. Ниже приведена диаграмма с интенсивностью Unicode (X представляет заголовок node, используемый для управления деревом):

                                         ╭─┬────────────────────────────────────────╮
   ╭─────────────────────────▶┏━━━┯━━━┯━━▼┓│                                        │
   │                        ╭─╂─  │ X │  ─╂╯                                        │ 
   │                        ▼ ┗━━━┷━━━┷━━━┛                                         │
   │                    ┏━━━┯━━━┯━━━┓                                               │
   │               ╭────╂─  │ A │  ─╂──╮                                            │
   │               ▼    ┗━━━┷━━━┷━━━┛  │                                            │    
   │        ┏━━━┯━━━┯━━━┓    ▲         │        ┏━━━┯━━━┯━━━┓                       │
   │      ╭─╂─  │ B │  ─╂────┤         ├────────╂─  │ C │  ─╂───────╮               │
   │      ▼ ┗━━━┷━━━┷━━━┛    │         ▼        ┗━━━┷━━━┷━━━┛       ▼               │  
   │┏━━━┯━━━┯━━━┓ ▲          │   ┏━━━┯━━━┯━━━┓       ▲         ┏━━━┯━━━┯━━━┓        │
   ╰╂─  │ D │  ─╂─╯          ╰───╂   │ E │  ─╂╮      │        ╭╂─  │ F │  ─╂╮       │ 
    ┗━━━┷━━━┷━━━┛                ┗━━━┷━━━┷━━━┛▼      │        ▼┗━━━┷━━━┷━━━┛▼       │
                                    ▲ ┏━━━┯━━━┯━━━┓  │ ┏━━━┯━━━┯━━━┓ ▲ ┏━━━┯━━━┯━━━┓│
                                    ╰─╂─  │ G │   ╂──┴─╂─  │ H │  ─╂─┴─╂─  │ J │  ─╂╯
                                      ┗━━━┷━━━┷━━━┛    ┗━━━┷━━━┷━━━┛   ┗━━━┷━━━┷━━━┛

Когда у вас есть структура, выполнение обходного пути очень просто:

Inorder-Successor(p)
    p points to a node.  This routine finds the successor of p in
    an inorder traversal and returns a pointer to that node

    q ← p.right
    If p.rtag = 0 Then
        While q.ltag = 0 Do
            q ← q.left
        End While
    End If

    Return q
    

Больше информации о резьбовых деревьях можно найти в Art of Computer Programming Ch.2 §3.1 или разбросано по Интернету.

Ответ 7

"Структуры данных и их алгоритмы" Гарри Льюиса и Ларри Дененберга описывают обход обращения ссылок для постоянного обхода двоичного дерева. Для этого вам не нужен родительский указатель на каждом node. Обход использует существующие указатели в дереве для хранения пути для отслеживания обратной связи. Требуется 2-3 дополнительных node ссылок. Плюс немного на каждом node, чтобы отслеживать направление обхода (вверх или вниз) при движении вниз. В моей реализации этих алгоритмов из книги профилирование показывает, что этот обход имеет гораздо меньше времени памяти/процессора. Реализация в java здесь.

Ответ 8

http://en.wikipedia.org/wiki/XOR_linked_list

закодировать родителя node в указатели листа

Ответ 9

Я думаю, что вы не могли бы этого сделать, так как вам нужно найти узлы, на которых вы остановились на пути, и определить, что вам всегда нужно пространство O (высота).

Ответ 10

Можно ли перебирать бинарное дерево в O (1) вспомогательном пространстве.

struct node { node * father, * right, * left; int value; };

Эта структура позволит вам перемещать 1-шаг в любом направлении через двоичное дерево.
Но все же на итерации вам нужно сохранить путь!