Итерация по двоичному дереву с O (1) вспомогательное пространство
Вы можете просто сделать это:
// Delcare a boolean as an attribute to be accessible inside the listener
private boolean isPlaying = false;
// Inside onCreate(), set a listener on your Button myButton
Mediaplayer mp = MediaPlayer.create(this, R.raw.yourfile);
myButton.setOnClickListener(new View.OnClickListener() {
public void onClick(View v) {
if (!isPlaying) {
// Not playing music
// START RANDOM MUSIC with mp.start()
mp.start()
isPlaying = true;
}
else {
// Playing music
// STOP CURRENT PLAYED MUSIC with mp.stop()
mp.stop()
isPlaying = false;
}
}
});
РЕДАКТИРОВАТЬ : класс MediaPlayer имеет метод для этого!
// Inside onCreate(), set a listener on your Button myButton
Mediaplayer mp = MediaPlayer.create(this, R.raw.yourfile);
myButton.setOnClickListener(new View.OnClickListener() {
public void onClick(View v) {
if (!mp.isPlaying()) {
// Not playing music
// START RANDOM MUSIC with mp.start()
mp.start()
}
else {
// Playing music
// STOP CURRENT PLAYED MUSIC with mp.stop()
mp.stop()
}
}
});
Лучший
7 ответов
Вы можете сделать это деструктивно, разъединяя каждый лист по ходу дела. Это может быть применимо в определенных ситуациях, т. Е. Когда вам больше не нужно дерево.
Расширяя, вы можете построить другое двоичное дерево, уничтожив первое. Вам понадобится некоторое микроуправление памятью, чтобы убедиться, что пиковая память никогда не превышает размер исходного дерева плюс небольшая константа. Это, вероятно, будет иметь некоторые вычислительные издержки, однако.
РЕДАКТИРОВАТЬ: Есть способ! Вы можете использовать сами узлы, чтобы осветить путь назад по дереву, временно перевернув их. Когда вы посещаете узел, вы указываете его указатель left-child на его родителя, его указатель right-child указывает на последний раз, когда вы сделали правый поворот на вашем пути (то есть быть найденным в родительском s указатель right-child в данный момент) и сохраните его настоящие дочерние элементы либо в указателе right-child теперь избыточного родителя, либо в состоянии обхода, соответственно. указатель следующего посещенного ребенка левого ребенка . Вам нужно сохранить некоторые указатели на текущий узел и его окрестности, но ничего «нелокального». Возвращаясь к дереву, вы полностью изменяете процесс.
Я надеюсь, что смогу прояснить это; это всего лишь грубый набросок. Вам придется где-то искать это (я уверен, что это упоминается где-то в «Искусстве компьютерного программирования»).
s указатель левого потомка . Вам нужно сохранить некоторые указатели на текущий узел и его окрестности, но ничего «нелокального». Возвращаясь к дереву, вы полностью изменяете процесс.
Я надеюсь, что смогу прояснить это; это всего лишь грубый набросок. Вам придется где-то искать это (я уверен, что это упоминается где-то в «Искусстве компьютерного программирования»).
s указатель левого потомка . Вам нужно сохранить некоторые указатели на текущий узел и его окрестности, но ничего «нелокального». Возвращаясь к дереву, вы полностью изменяете процесс.
Я надеюсь, что смогу прояснить это; это всего лишь грубый набросок. Вам придется где-то искать это (я уверен, что это упоминается где-то в «Искусстве компьютерного программирования»).
Боже, мне действительно нужно будет напечатать его с Кнута. Это решение принадлежит Джозефу М. Моррису [ Inf. Proc. Letters 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) для доступа к элементам дерева в любом порядке, не требуя дочерних к родительским ссылкам или изменения структуры дерева.
Чтобы сохранить дерево и использовать только пробел O (1), это возможно, если ...
- Каждый узел имеет фиксированный размер.
- Все дерево находится в непрерывной части память (т. е. массив)
- Вы не перебираете дерево, вы просто перебираете массив
Или если вы уничтожаете дерево во время его обработки ...:
- @Svante придумал это идея, но я хотел бы расширить как немного, используя деструктивный подход.
- Как? Вы можете продолжать брать самый левый листовой узел в дереве (for (;;) node = node-> left и т. Д. ..., затем обрабатывать его, а затем удалять. Если самый левый узел в Дерево не является листовым узлом, тогда вы обрабатываете и удаляете самый левый крайний узел правого узла. Если правый узел не имеет дочерних узлов, то вы обрабатываете и удаляете его.
Способы, что он не будет работать ...
Если вы используете рекурсию, вы будете использовать стек неявно. Для некоторых алгоритмов (не для этой проблемы) хвостовая рекурсия позволила бы вам использовать рекурсию и иметь пространство O (1), но, поскольку у любого конкретного узла может быть несколько дочерних элементов, и, следовательно, после рекурсивного вызова есть работа, которую необходимо выполнить, O (1) ) рекурсия космического хвоста невозможна.
Вы можете попытаться решить задачу 1 уровня за раз, но нет способа получить доступ к узлам произвольного уровня без вспомогательного (неявного или явного) пространства. Например, вы можете выполнить поиск нужного узла, но тогда это займет неявное пространство стека. Или вы можете хранить все свои узлы в другой структуре данных для каждого уровня, но это также требует дополнительного места.
но, поскольку любой конкретный узел может иметь несколько дочерних элементов, и, следовательно, после рекурсивного вызова есть работа, которую необходимо выполнить, рекурсия O (1) в космическом хвосте невозможна.Вы можете попытаться решить задачу 1 уровня за раз, но нет способа получить доступ к узлам произвольного уровня без вспомогательного (неявного или явного) пространства. Например, вы можете выполнить поиск нужного узла, но тогда это займет неявное пространство стека. Или вы можете хранить все свои узлы в другой структуре данных для каждого уровня, но это также требует дополнительного места.
но, поскольку любой конкретный узел может иметь несколько дочерних элементов, и, следовательно, после рекурсивного вызова есть работа, которую необходимо выполнить, рекурсия O (1) в космическом хвосте невозможна.Вы можете попытаться решить задачу 1 уровня за раз, но нет способа получить доступ к узлам произвольного уровня без вспомогательного (неявного или явного) пространства. Например, вы можете выполнить поиск нужного узла, но тогда это займет неявное пространство стека. Или вы можете хранить все свои узлы в другой структуре данных для каждого уровня, но это также требует дополнительного места.
Например, вы можете выполнить поиск нужного узла, но тогда это займет неявное пространство стека. Или вы можете хранить все свои узлы в другой структуре данных для каждого уровня, но это также требует дополнительного места. Например, вы можете выполнить поиск нужного узла, но тогда это займет неявное пространство стека. Или вы можете хранить все свои узлы в другой структуре данных для каждого уровня, но это также требует дополнительного места.Указатели от узлов к их предкам могут иметься без (ну, два бита на узел) дополнительного хранилища, используя структуру, называемую резьбовым деревом. В многопоточном дереве нулевые ссылки представлены битом состояния, а не нулевым указателем. Затем вы можете заменить нулевые ссылки указателями на другие узлы: левые ссылки указывают на узел-преемник в обходе inorder, а правые ссылки на предшественник. Вот диаграмма в Юникоде (X представляет узел заголовка, используемый для управления деревом):
╭─┬────────────────────────────────────────╮
╭─────────────────────────▶┏━━━┯━━━┯━━▼┓│ │
│ ╭─╂─ │ 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
Много дополнительной информации о многопоточных деревьях может быть встречается в Искусство компьютерного программирования гл.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();
}
Я думаю Вы никак не могли бы сделать это, так как вы должны каким-то образом найти узлы, на которых вы остановились на пути, и определить, что вам всегда нужно пространство O (высота).