Вступление


Здравствуйте, хабравчане. Это моя первая публикация, в которой хочу поделиться структурой данных SMAS. В конце статьи будет предоставлен С++ — класс предложенной структуры данных. Реализация рекурсивная, но моя цель — донести идею. Реализацию не рекурсивной версии — дело второе. Важно «услышать» мнения.

Что не так с деревом?


Да, всё так и можно завершать статью, всем спасибо. было бы плюнуть на значительный оверхеад памяти на вспомогательные данные в виде ссылок на левые-правые поддеревья и флаг для балансировки (разный в зависимости от используемой техники — красно-чёрные, АВЛ и т.п. деревья). Ещё один, не то чтобы минус — это постоянная модификация дерева при вставке для балансировки (тут особенно важна сложность и запутанность методов для новичков). На этом минусы заканчиваются и сложно себе представить что-то лучше и более универсальное (хеш-таблицы, ИМХО, ещё круче, но ОХ УЖ ЭТИ КОЛЛИЗИИ).

А почему не сортированные массивы?


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

Но что же не так с сортированными массивами?

Да всё так, можно заканчивать статью и использовать сортированные массивы вместо бинарных деревьев поиска радоваться сэкономленным ресурсам, если только нам не нужно добавлять-удалять элементы из такого массива, ведь если добавлять новые элементы (удалять старые), то массив скажет: "ломай пересортируй меня полностью". Но беда сортировки в том, что она медленная, если нужно вставить новый элемент где-то между остальными, тем более в начало.

Но есть и идеальный случай — когда новый элемент больше остальных и его достаточно просто дописать в конец. Это идеально — всего одна операция, но вероятностная оценка такого идеального случая заставляет нас использовать бинарные ��еревья или хеш-таблицы, или огромное множество других действительно красивых и хитроумных механизмов. Исходя из теории вероятности, такая ситуация редкая — только если все элементы добавляются в массив по-возрастанию (ирония-аналогия с бинарным деревом поиска, когда отсортированные входные данные как раз являются наихудшим случаем с вырождением дерева в связанный список с линейной сложностью).

Частный случай, как закономерность?


Но давайте рассмотрим массив всего из одного элемента. Не важно, какое значение вносится — оно всегда вписывается в начало пустого до этого массива и одно-элементный массив, естественно, всегда отсортирован. А если мы захотим вписать 2-й элемент в нашу структуру данных? Давайте просто создадим ещё один одно-элементный массив и получим два отсортированных одно-элементных массива. Получить новый отсортированный массив из двух отсортированных — простая задача, хотя не очень быстрая… Но в таком случае нам уже нужно сортировать массив не при каждой вставке, а при каждой второй вставке. Мы используем «отложенную сортировку».

А если мы хотим внести больше 2-х элементов? Хотеть-не вредно — запишем новый 2-х элементный массив куда-то и продолжим вносить элементы в одно-элементные массивы и так же на 4-м элементе у нас появится 2 2-х элементных отсортированных массива, которые мы точно так же сможем объединить в один 4-х элементный и так далее, пока не выскочит синий экран смерти и взрыв процессора с попутным образованием чёрной дыры, втягивающей в себя всё окружающее пространство-время (что-то меня понесло...) пока нам это позволит память.

Распределение нагрузки


Понятно, что этот алгоритм уже значительно сокращает количество сортировок, относительно сортировки обычного массива, ведь первый уровень массивов нужно сортировать через раз, 2-й уровень — каждую 4-ю вставку, 3-й уровень — каждую 8-ю вставку — собственно, это логарифмическая сложность.

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

Поиск


Поиск представляет из себя классический бинарный поиск по отсортированному массиву с той лишь разницей, что здесь массивов много и искать необходимо по-очереди по всем. Поэтому логарифмичность сложности поиска оспариваема(если не ошибаюсь, это удвоенная логарифмическая сложность). Но в поставленной задаче это вполне приемлемо, учитывая сэкономленную память.

Реализация


Пока закипал чайник, я вспомнил, что хотел ещё написать, но потом чайник закипел и его свист заставил меня обратно забыть то, что я хотел ещё написать…

Реализация была достаточно запутанной, ибо в голове было лишь поверхностное представление о том, как вся эта машина будет ехать — код писался чуть ли не наугад, поэтому пойду посплю с горя, в то же время программная структура алгоритма класса содержит всего 3 метода, (не считая конструктора и деструктора). Код не содержит ничего кроме работы с массивами, циклов и ООП-идеологии — всё до гениальности безумия просто и, я надеюсь, понятно.

Собственно код


#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <windows.h>

#define	undefined	2147483648

class ARRAY
{
private:
	ARRAY*nextLevel;
	unsigned int
		*keyResult,	// Здесь будет указатель на вновь создаваемый массив из двух - keyLeft, keyRight
		*keyLeft,	// Указатель на первый подмассив
		*keyRight,	// Указатель на второй подмассив
		*keyTemp,	// Указательно на временный подмассив
		*valResult,	// То же самое,
		*valLeft,	// но для
		*valRight,	// массивов
		*valTemp,	// значений
		countResult,countLeft,countRight,	// Счётчики позиции для отложенного пошагового слияния массивов 1 и 2 в массив 0 соответственно.
		len;//        Размерность массивов(размерность 0-го в 2 раза больше)
	void upd() //пошаговое отложенное слияние двух массивов в один
	{
		if(keyResult)
		{
			if(countLeft<len)
			{
				if(countRight<len)
				{
					if(keyLeft[countLeft]<keyRight[countRight])//если текущий элемент 1-го подмассива меньше 2-го - вносим его
					{
						keyResult[countResult]=keyLeft[countLeft];
						valResult[countResult]=valLeft[countLeft];
						countResult++;
						countLeft++;
					}
					else//если текущий элемент 2-го подмассива меньше 1-го - вносим его в массив слияния
					{
						keyResult[countResult]=keyRight[countRight];
						valResult[countResult]=valRight[countRight];
						countResult++;
						countRight++;
					}
				}
				else  //значит 2-й массив уже весь перемещён и необходимо добавить сл. элемент из первого подмассива
				{
					keyResult[countResult]=keyLeft[countLeft];
					valResult[countResult]=valLeft[countLeft];
					countResult++;
					countLeft++;
				}
			}
			else
			{
				if(countRight<len)   //значит 1-й массив уже весь перемещён - добавляем сл. элемент из второго подмассива
				{
					keyResult[countResult]=keyRight[countRight];
					valResult[countResult]=valRight[countRight];
					countResult++;
					countRight++;
				}
				//в противном случае все элементы обоих массивов уже присутствуют в результирующем - ничего не делаем
			}
			if(countResult==len*2)   //Если после очередного шага слияние завершилось
			{
				if(!nextLevel)nextLevel=new ARRAY;  //Создаём сл. уровень, если он ещё не существует
				nextLevel->set(keyResult,valResult,len*2);
				keyResult=NULL;
				keyLeft=NULL;
				keyRight=NULL;
				keyTemp=NULL;
				valResult=NULL;
				valLeft=NULL;
				valRight=NULL;
				valTemp=NULL;
			}
		}
		if(nextLevel)nextLevel->upd();
	}
	void set(unsigned int*Key,unsigned int*Val,unsigned int Len)
	{
		len=Len;
		if(!keyTemp){keyTemp=Key;valTemp=Val;}
		else
		{
			keyLeft=Key;
			valLeft=Val;
			keyRight=keyTemp;
			valRight=valTemp;
			keyTemp=NULL;
			valTemp=NULL;
			countResult=0;
			countLeft=0;
			countRight=0;
			keyResult=new unsigned int[len*2];
			valResult=new unsigned int[len*2];
		}
		upd();
	}
public:
	~ARRAY()
	{
		if(keyResult)delete[]keyResult;
		if(keyLeft)delete[]keyLeft;
		if(keyRight)delete[]keyRight;
		if(keyTemp)delete[]keyTemp;
		if(valResult)delete[]valResult;
		if(valLeft)delete[]valLeft;
		if(valRight)delete[]valRight;
		if(valTemp)delete[]valTemp;
		if(nextLevel)delete nextLevel;
	}
	ARRAY()
	{
		keyResult=NULL;
		keyLeft=NULL;
		keyRight=NULL;
		keyTemp=NULL;
		valResult=NULL;
		valLeft=NULL;
		valRight=NULL;
		valTemp=NULL;
		countResult=0;
		countLeft=0;
		countRight=0;
		len=0;
		nextLevel=NULL;
	}
	void set(unsigned int Key,unsigned int Val)
	{
		unsigned int*k=new unsigned int[1];k[0]=Key;
		unsigned int*v=new unsigned int[1];v[0]=Val;
		set(k,v,1);
	}
	unsigned int get(unsigned int Key)
	{
		unsigned int l,r,i;
		if(keyTemp)
		{
			l=0;r=len;
			while(l!=r-1)
			{
				i=(l+r)/2;
				if(keyTemp[i]<Key)l=i;
				else if(keyTemp[i]>Key)r=i;
				else return valTemp[i];
			}
			if(keyTemp[l]==Key)return valTemp[l];
		}
		if(keyLeft)
		{
			l=0;r=len;
			while(l!=r-1)
			{
				i=(l+r)/2;
				if(keyLeft[i]<Key)l=i;
				else if(keyLeft[i]>Key)r=i;
				else return valLeft[i];
			}
			if(keyLeft[l]==Key)return valLeft[l];
		}
		if(keyRight)
		{
			l=0;r=len;
			while(l!=r-1)
			{
				i=(l+r)/2;
				if(keyRight[i]<Key)l=i;
				else if(keyRight[i]>Key)r=i;
				else return valRight[i];
			}
			if(keyRight[l]==Key)return valRight[l];
		}
		if(nextLevel)return nextLevel->get(Key);
		else return undefined;
	}
};

void main()
{
	ARRAY*arr=new ARRAY;
	char inp[256];
	unsigned int Key,Val;
	while(gets(inp)&&inp[0])
	{
		if(inp[0]=='+'){Key=atoi(&inp[1]);gets(inp);Val=atoi(inp);arr->set(Key,Val);}
		else if(inp[0]=='='){Key=atoi(&inp[1]);Val=arr->get(Key);if(Val!=undefined)printf("%d\n",Val);else printf("undefined\n");}
		else system("cls");
	}
	delete arr;
}


ЗЫ:
В алгоритме не реализовано удаление, хотя некоторые эротические фантазии есть. Но это уже отдельная статья. Здесь же я попытался по умничать донести саму идею и если у кого-то есть свои мысли по реализации удаления — велком. Хотя на самом деле данная структура разрабатывалась для специфической задачи, не требующей удаления да и вообще ничего кроме быстрой вставки и быстрого поиска, появилось желание доработать класс, реализовав прочие, часто нужные в повседневной жизни работе методы, чем и займусь когда рак на горе свиснет — нибудь.