Меня озадачивает следующий вопрос о домашнем задании для класса алгоритмов:
Предположим, что нам задана последовательность из n значений x 1, x 2... x n и искать быстро отвечать на повторяющиеся запросы form: данные я и j, найдите наименьший значение в x i... x j
Создайте структуру данных, которая использует O (n) пространство и ответы на запросы в O (log n) время.
Во-первых, я не уверен, относится ли последовательность к отсортированному набору или к несортированному множеству, но, поскольку он не говорит об этом, я буду считать, что средства последовательности несортированы.
Итак, я понимаю, что это, очевидно, должно включать двоичное дерево, если мы говорим о времени поиска O (log N). В принципе, я полагаю, у вас есть набор S, и вы вставляете каждый элемент в S в двоичное дерево. Проблема в том, что вопрос в основном требует, чтобы я придумал способ ответа на запросы, где мне задан диапазон индексов в несортированный набор, - и затем определите самое низкое значение в этом диапазоне в O (log N) времени. Как это возможно? Даже если каждый номер набора вставляется в дерево, лучше всего я могу найти любое конкретное число в O (log N) времени. Это не позволяет мне найти наименьшее значение в несортированном диапазоне чисел в S.
Любые предложения?
Хорошо, я думаю, у меня есть хорошее начало для вас, и я узнал что-то новое в этом процессе.
Я бы взглянул на запись в Википедии Декартовы деревья. Я не собираюсь рассказывать вам больше, потому что боюсь сделать домашнее задание для вас, но вы, кажется, умный парень, поэтому я полагаю, что вы можете это исправить.
Спасибо, что помогли мне изучить новую структуру данных, кстати!
Если набор был отсортирован, вам не понадобится дерево. Наименьший элемент в диапазоне [i, j] имел бы индекс i.
Итак, предположим, что элементы вашей последовательности были сохранены в порядке их индексов у листьев дерева. Можете ли вы сохранить какую-либо дополнительную информацию (например, возможно, какой-то минимум и максимум) в каждом интерьере node, чтобы облегчить ваш запрос?
Если да, то если дерево сбалансировано, и если вы можете ответить на свой запрос, посмотрев только на два пути от корня до двух элементов в {i, j}, то вы достигнете своего O (log N). Поскольку сбалансированное двоичное дерево с N листьями содержит (2N-1) полные узлы, вы также будете удовлетворять своему пределу хранения O (N).
ПОДРОБНОЕ ОПИСАНИЕ: Рассмотрим вычисление минимального значения в диапазоне [i, j].
В каждом внутреннем дереве node A дерева сохраняйте минимальное значение для всех листьев под ним. Это может быть вычислено снизу вверх, когда дерево сначала построено.
Теперь начните с листа i. Поднимитесь по дереву, сохраняя в качестве вашего кандидата минимальное значение значение в я или все, что известно как справа от i, так и слева от j. Остановите один node ниже взаимного предка я и j.
Начните снова с листа j. Поднимитесь по дереву, снова сохраняя в качестве вашего кандидата минимум значение в j или все, что известно как слева, так и справа от i.
Ваш минимум для [i, j] является минимальным из двух вычисленных значений. Вычисление максимума аналогично. Общая потребность в хранилище - 2 значения на внутреннее пространство node плюс два указателя на внутреннюю часть node плюс одно значение на лист, что равно N + 4 (N-1) для полного дерева.
Путь, по которому вы перемещаетесь по дереву из листа i, - это тот же путь, по которому вы едете по дереву, если будете искать лист i.
С# КОД ДЛЯ ПОИСКА:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace RangeSearch
{
public class RangeSearch
{
int[] tree;
int N;
int LeafLocation(int leafNumber) { return leafNumber + N - 1; }
int LeafValue(int leafNumber) { return tree[ LeafLocation(leafNumber)]; }
int LeftChild(int x) { return 2*x + 1; }
int RightChild(int x) { return 2*x + 2; }
int Parent(int x) { return (x-1)/2; }
bool IsPowerOf2(int x) { while (x > 0) { if (x == 1) return true; if ((x & 1) == 1 ) return false; x = x >> 1; } return false; }
bool IsAncestorOf( int x, int y ) { if( x>y ) return false; return x==y || IsAncestorOf(LeftChild(x), y) || IsAncestorOf(RightChild(x),y); } // note: violating time bound for legibility, can fix by storing min/max descendant index at each node
public RangeSearch(params int[] vals)
{
if (!IsPowerOf2(vals.Length))
throw new ArgumentException("this implementation restricted to N being power of 2");
N = vals.Length;
tree = new int[2 * N - 1];
// the right half of the array contains the leaves
vals.CopyTo(tree, N - 1);
// the left half of the array contains the interior nodes, each of which holds the minimum of all its children
for (int i = N - 2; i >= 0; i--)
tree[i] = Math.Min(tree[LeftChild(i)], tree[RightChild(i)]);
}
public int FindMin(int a, int b)
{
if( a>b )
throw new ArgumentException( "FindMin expects a range [a,b] with a<=b" );
int x = Walk( a, true, b);
int y = Walk( b, false, a);
return Math.Min(x, y);
}
int Walk( int leafNumber, bool leftSide, int otherLeafNumber )
{
int minSoFar = LeafValue(leafNumber);
int leafLocation = LeafLocation(leafNumber);
int otherLeafLocation = LeafLocation(otherLeafNumber);
int parent = Parent(leafLocation);
bool cameFromLeft = (leafLocation == LeftChild(parent));
return Walk2(minSoFar, parent, cameFromLeft, leftSide, otherLeafLocation);
}
int Walk2(int minSoFar, int node, bool cameFromLeft, bool leftSide, int otherLeafLocation)
{
if (IsAncestorOf(node, otherLeafLocation))
return minSoFar;
if (leftSide)
minSoFar = !cameFromLeft ? minSoFar : Math.Min(minSoFar, tree[RightChild(node)]);
else
minSoFar = cameFromLeft ? minSoFar : Math.Min(minSoFar, tree[LeftChild(node)]);
return Walk2(minSoFar, Parent(node), node == LeftChild(Parent(node)), leftSide, otherLeafLocation);
}
}
}
С# CODE TO TEST IT:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace RangeSearch
{
class Program
{
static void Main(string[] args)
{
RangeSearch rngA = new RangeSearch(9, 3, 7, 1);
System.Diagnostics.Trace.Assert(3 == rngA.FindMin(0, 2) );
System.Diagnostics.Trace.Assert(1 == rngA.FindMin(0, 3));
System.Diagnostics.Trace.Assert(1 == rngA.FindMin(1, 3));
RangeSearch rngB = new RangeSearch(1, 7, 3, 9);
System.Diagnostics.Trace.Assert(3 == rngB.FindMin(1, 3));
System.Diagnostics.Trace.Assert(1 == rngB.FindMin(0, 3));
System.Diagnostics.Trace.Assert(1 == rngB.FindMin(0, 2));
RangeSearch rngC = new RangeSearch(17, 21, 77, 70, 58, 79, 79, 89);
System.Diagnostics.Trace.Assert(21 == rngC.FindMin(1, 7));
RangeSearch rngD = new RangeSearch(94, 78, 88, 72, 95, 97, 89, 83);
System.Diagnostics.Trace.Assert(72 == rngD.FindMin(1, 6));
RangeSearch rngE = new RangeSearch(0, 66, 6, 43, 34, 34, 63, 49);
System.Diagnostics.Trace.Assert(34 == rngE.FindMin(3, 4));
Random rnd = new Random();
for (int i = 0; i < 1000000; i++)
{
int[] tmp = new int[64];
for (int j = 0; j < tmp.Length; j++)
tmp[j] = rnd.Next(0, 100);
int a = rnd.Next(0, tmp.Length);
int b = rnd.Next(a, tmp.Length);
RangeSearch rng = new RangeSearch(tmp);
System.Diagnostics.Trace.Assert(Min(tmp, a, b) == rng.FindMin(a, b));
}
}
static int Min(int[] ar, int a, int b)
{
int x = ar[a];
for (int i = a + 1; i <= b; i++)
x = Math.Min(x, ar[i]);
return x;
}
}
}
Определение sequence является упорядоченным set (не отсортировано).
Зная, что упорядоченное множество позволяет вам использовать Декартовое дерево, которое является идеальной структурой данных для Минимальные минимальные запросы.
Вы считали дерево интервалов?
Глядя на запись в википедии, она, похоже, соответствует тому, что вы просите. http://en.wikipedia.org/wiki/Interval_tree
EDIT:
Да, кажется, что деревья интервалов не подходят для этого сценария...
Некоторые подталкивания:
Предположим, вы каким-то образом сохранили минимум всех выровненных * подмассивов длиной 1, 2, 4, 8,...? Как немногие из этих минимумов вы можете уйти, глядя на правильный ответ? Как их сохранить, чтобы вы могли эффективно их извлекать?
(* например, store min (x 0... 3)) и min (x 4... x 7), но не min (x 1... x 4))