Я озадачен следующим вопросом о домашней работе для класса алгоритмов:
Предположим, что нам дают последовательность значений n x1, x2... xn, и стремимся быстро ответить на повторенные запросы формы: учитывая меня и j, найдите самое маленькое значение в xi.. xj
Разработайте структуру данных, которая использует O (n) пространство и отвечает, запросы в O (зарегистрируйте n), время.
Во-первых, я не уверен, относится ли последовательность к отсортированному набору или неотсортированному набору - но так как она не говорит иначе, что я приму неотсортированные средства последовательности.
Так, я понимаю, что это, очевидно, должно включить двоичное дерево, если мы говорим о O (зарегистрируйте N), время поиска. Так в основном я фигурирую, у Вас есть набор S
, и Вы вставляете каждый элемент в S
в двоичное дерево. Проблема, вопрос в основном хочет, чтобы я придумал способ ответить на запросы, где мне дают диапазон индексов в неотсортированный набор - и затем определяю самое низкое значение в том диапазоне в O (зарегистрируйте N), время. Как это возможно? Даже если каждое количество набора вставляется в дерево, лучшим, который я могу сделать, является поиск какое-то конкретное число в O (зарегистрируйте N), время. Это не позволяет мне находить самое низкое значение в неотсортированном диапазоне чисел в S
.
Какие-либо предложения?
Хорошо, я думаю, у меня для вас хорошее начало, и я узнал что-то новое в процессе.
Я бы взглянул на статью в Википедии о декартовых деревьях . Я не собираюсь рассказывать вам больше, опасаясь делать за вас домашнее задание, но вы кажетесь умным парнем, поэтому я думаю, вы справитесь.
Кстати, спасибо за помощь в изучении новой структуры данных!
Рассматривали ли вы дерево интервалов?
Глядя на статью в Википедии, кажется, что она полностью соответствует тому, что вы просите. http://en.wikipedia.org/wiki/Interval_tree
РЕДАКТИРОВАТЬ:
Да, похоже, что деревья интервалов не подходят для этого сценария ...
Если бы набор был отсортирован, вам не понадобится дерево. Наименьший элемент в диапазоне [i, j] будет иметь индекс i.
Итак, предположим, что элементы вашей последовательности были сохранены в порядке их индексов на листьях дерева.Можете ли вы сохранить какую-либо дополнительную информацию ( кхм , возможно, какие-то минимальные и максимальные значения) на каждом внутреннем узле, чтобы облегчить ваш запрос?
Если да, то если дерево сбалансировано, и если вы можете ответить ваш запрос, глядя только на два пути от корня к двум элементам в {i, j}, тогда вы достигнете своей стоимости поиска O (log N). Поскольку сбалансированное двоичное дерево с N листьями содержит всего (2N-1) узлов, вы также будете удовлетворять своему пределу хранения O (N).
ПОДРОБНЕЕ: рассмотрите возможность вычисления минимального значения в диапазоне [i, j].
В каждом внутреннем узле A дерева сохраните минимальное значение для всех нижележащих листьев. Это можно вычислить снизу вверх при первом построении дерева.
Теперь начнем с листа i. Поднимитесь по дереву, сохраняя в качестве минимального значения кандидата значение в i или что-нибудь, что, как известно, находится справа от i и слева от j. Остановите один узел ниже общего предка i и j.
Начать снова с листа j. Поднимитесь по дереву, снова сохраняя в качестве минимума кандидата значение j или что-нибудь, что, как известно, находится как слева от j, так и справа от i.
Тогда ваш минимум для [i, j] будет минимальным из двух вычисленных вами значений. Вычисление максимума аналогично. Общие требования к хранилищу составляют 2 значения на внутренний узел плюс два указателя на внутренний узел плюс одно значение на лист, что составляет N + 4 (N-1) для полного дерева.
Путь, который вы путешествуете вверх по дереву от листа i, - это тот же путь, который вы прошли бы вниз дерево, если бы искали лист i.
КОД C # ДЛЯ ПОИСКА:
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);
}
}
}
КОД C # ДЛЯ ТЕСТИРОВАНИЯ:
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;
}
}
}
Определение последовательности - это упорядоченное множество (не отсортированное).
Знание того, что множество является упорядоченным, позволяет использовать декартово дерево, которое является идеальной структурой данных для минимальных запросов диапазона.