Нагруженное дерево

Префиксное дерево — абстрактный тип данных, структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. В отличие от бинарных деревьев, в листьях дерева не хранится ключ. Значение ключа можно получить просмотром всех родительских узлов, каждый из которых хранит один или несколько символов алфавита. Корень дерева связан с пустой строкой. Таким образом, потомки узла имеют общий префикс, откуда и произошло название данного АТД. Значения, связанные с ключом, обычно не связаны с каждым узлом, а только с листьями и, возможно, некоторыми внутренними узлами.

Альтернативные названия на русском — бор (первый перевод монографии Д.Кнута, Т.3), луч (второй перевод монографии Д.Кнута, Т.3), нагруженное дерево (книга Ахо и др. «Структуры данных и алгоритмы», стр.152), там же и происхождение названия. На английском — Trie.

Пример реализации на C++

template <typename DATA_T>
class Trie{
	struct Node{
		Array<Node*> Link;
		DATA_T* Data;
		void FillNulls();
		Node();
		Node(const DATA_T& InData);
		~Node();
		bool IsNoLinks();
		bool IsNoData();
		bool IsEmpty();
		size_t Count();
		void Clear(bool IsStart=false);
		Node* LeftChild();
		Node* RightChild();
		size_t SearchForLinkTo(Node* InNode);
	};
	Node Start;
	size_t IndexByKeyAt(const String& InKey, size_t Position);
	void DeleteNodeWithParents(Node* NodeToDelete, Array<Node*>& Parents);
public:
	class Iterator{
		Trie* CurrentTrie;
		Node* CurrentNode;
		Array<Node*> Stack;
		void GoLeft();
		void GoRight();
		void SetBad();
		void GoNext();
		void GoPrevious();
	public:
		Iterator(const Iterator& InIterator);
		Iterator(Trie& InTrie, bool IsBegin=true);
		operator bool();
		Iterator& operator++();
		Iterator& operator--();
		Iterator operator++(int);
		Iterator operator--(int);
		Iterator& operator+=(size_t n);
		Iterator& operator-=(size_t n);
		Iterator& operator=(const Iterator& InIterator);
		Iterator& operator=(const String& InKey);
		DATA_T& operator*();
		void Delete();
	};
	Trie();
	~Trie();
	Iterator GetBegin();
	Iterator GetEnd();
	void Add(const String& InKey, const DATA_T& InData);
	void Delete(const String& InKey);
	DATA_T& operator[](const String& InKey);
	size_t Count();
	void Clear();
	Iterator Find(const DATA_T& Unknown);
};
 
template <typename DATA_T>
void Trie<DATA_T>::Node::FillNulls(){
	for(size_t i=0; i<=255; i++)
		Link.AddLast(NULL);
}
 
template <typename DATA_T>
Trie<DATA_T>::Node::Node():Data(NULL){
	FillNulls();
}
 
template <typename DATA_T>
Trie<DATA_T>::Node::Node(const DATA_T& InData):Data(new DATA_T(InData)){
	FillNulls();
}
 
template <typename DATA_T>
Trie<DATA_T>::Node::~Node(){
	delete Data;
}
 
template <typename DATA_T>
bool Trie<DATA_T>::Node::IsNoLinks(){
	for(typename Array<Node*>::Iterator i(Link); i; i++)
		if(*i)
			return false;
	return true;
}
 
template <typename DATA_T>
bool Trie<DATA_T>::Node::IsNoData(){
	return !Data;
}
 
template <typename DATA_T>
bool Trie<DATA_T>::Node::IsEmpty(){
	return IsNoLinks() && IsNoData();
}
 
template <typename DATA_T>
size_t Trie<DATA_T>::Node::Count(){
	size_t ReturnValue=0;
	if(Data)
		++ReturnValue;
	for(typename Array<Node*>::Iterator i(Link); i; i++)
		if(*i)
			ReturnValue+=(*i)->Count();
	return ReturnValue;
}
 
template <typename DATA_T>
void Trie<DATA_T>::Node::Clear(bool IsStart){
	for(typename Array<Node*>::Iterator i(Link); i; i++)
		if(*i)
			(*i)->Clear();
	if(!IsStart)
		delete this;
	else
		for(typename Array<Node*>::Iterator i(Link); i; i++)
			*i=NULL;
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Node* Trie<DATA_T>::Node::LeftChild(){
	for(typename Array<Node*>::Iterator i(Link); i; i++)
		if(*i)
			return *i;
	return NULL;
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Node* Trie<DATA_T>::Node::RightChild(){
	for(typename Array<Node*>::Iterator i(Link.GetEnd()); i; i--)
		if(*i)
			return *i;
	return NULL;
}
 
template <typename DATA_T>
size_t Trie<DATA_T>::Node::SearchForLinkTo(typename Trie<DATA_T>::Node* InNode){
	size_t ReturnValue=0;
	for(typename Array<Node*>::Iterator i(Link); i; i++){
		if(*i==InNode)
			return ReturnValue;
		ReturnValue++;
	}
	return 256;
}
 
template <typename DATA_T>
Trie<DATA_T>::Trie(){}
 
template <typename DATA_T>
Trie<DATA_T>::~Trie(){
	Clear();
}
 
template <typename DATA_T>
size_t Trie<DATA_T>::IndexByKeyAt(const String& InKey, size_t Position){
	return ((String)InKey)[Position]+128;
}
 
template <typename DATA_T>
void Trie<DATA_T>::Add(const String& InKey, const DATA_T& InData){
	Node* Current=&Start;
	for(size_t i=0; i<InKey.Length(); i++){
		size_t Index=IndexByKeyAt(InKey, i);
		if(!Current->Link[Index])
			Current->Link[Index]=new Node();
		Current=Current->Link[Index];
	}
	if(Current->Data)
		throw String("Not unique key!");
	Current->Data=new DATA_T(InData);
}
 
template <typename DATA_T>
void Trie<DATA_T>::DeleteNodeWithParents(Trie<DATA_T>::Node* NodeToDelete, Array<Node*>& Parents){
	NodeToDelete->Data=NULL;
	if(NodeToDelete->IsEmpty())
		delete NodeToDelete;
	size_t i=Parents.Count();
	while(i-->0){
		Parents[i]->Link[Parents[i]->SearchForLinkTo(NodeToDelete)]=NULL;
		if(Parents[i]->IsEmpty())
			delete Parents[i];
		else
			break;
		NodeToDelete=Parents[i];
	}
}
 
template <typename DATA_T>
void Trie<DATA_T>::Delete(const String& InKey){
	Array<Node*> Stack;
	Node* Current=&Start;
	for(size_t i=0; i<InKey.Length(); ++i){
		size_t Index=IndexByKeyAt(InKey, i);
		if(!Current->Link[Index])
			throw String("This record does not exist!");
		Stack.AddLast(Current);
		Current=Current->Link[Index];
	}
	DeleteNodeWithParents(Current, Stack);
}
 
template <typename DATA_T>
DATA_T& Trie<DATA_T>::operator[](const String& InKey){
	Node* Current=&Start;
	for(size_t i=0; i<InKey.Length(); i++){
		size_t Index=IndexByKeyAt(InKey, i);
		if(!Current->Link[Index])
			throw String("This record does not exist!");
		Current=Current->Link[Index];
	}
	return *Current->Data;
}
 
template <typename DATA_T>
size_t Trie<DATA_T>::Count(){
	return Start.Count();
}
 
template <typename DATA_T>
void Trie<DATA_T>::Clear(){
	Start.Clear(true);
}
 
template <typename DATA_T>
Trie<DATA_T>::Iterator::Iterator(Trie<DATA_T>& InTrie, bool IsBegin):CurrentTrie(&InTrie),CurrentNode(&InTrie.Start){
	if(IsBegin)
		GoLeft();
	else
		GoRight();
}
 
template <typename DATA_T>
Trie<DATA_T>::Iterator::Iterator(const Trie<DATA_T>::Iterator& InIterator):CurrentTrie(InIterator.CurrentTrie),CurrentNode(InIterator.CurrentNode){
	for(typename Array<Node*>::Iterator i(((typename Trie<DATA_T>::Iterator&)InIterator).Stack); i; ++i)
		Stack.AddLast(*i);
}
 
template <typename DATA_T>
Trie<DATA_T>::Iterator::operator bool(){
	return CurrentNode!=NULL && CurrentNode->Data!=NULL;
}
 
template <typename DATA_T>
void Trie<DATA_T>::Iterator::GoLeft(){
	while(!CurrentNode->IsNoLinks())
		for(typename Array<Node*>::Iterator i(CurrentNode->Link); i; i++)
			if(*i){
				Stack.AddLast(CurrentNode);
				CurrentNode=*i;
			}
}
 
template <typename DATA_T>
void Trie<DATA_T>::Iterator::GoRight(){
	while(!CurrentNode->IsNoLinks())
		for(typename Array<Node*>::Iterator i(CurrentNode->Link.GetEnd()); i; i--)
			if(*i){
				Stack.AddLast(CurrentNode);
				CurrentNode=*i;
			}
}
 
template <typename DATA_T>
void Trie<DATA_T>::Iterator::SetBad(){
	CurrentNode=NULL;
	Stack.Clear();
}
 
template <typename DATA_T>
void Trie<DATA_T>::Iterator::GoNext(){
	Node* RightNode=CurrentNode->RightChild();
	if(RightNode){
		Stack.AddLast(CurrentNode);
		CurrentNode=RightNode;
		GoLeft();
		return;
	}
	if(Stack.Count()==0){
		SetBad();
		return;
	}
	typename Array<Node*>::Iterator i=Stack.GetEnd();
	if((*i)->RightChild()!=CurrentNode){
		typename Array<Node*>::Iterator j=++(*i)->Link.Find(CurrentNode);
		while(!*j)
			++j;
		CurrentNode=*j;
		return;
	}
	while(CurrentNode==(*i)->RightChild()){
		CurrentNode=*i--;
		Stack.DeleteLast();
		if(Stack.Count()==0){
			SetBad();
			return;
		}
	}
	CurrentNode=*i;
	Stack.DeleteLast();
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Iterator& Trie<DATA_T>::Iterator::operator++(){
	if(!CurrentNode)
		return *this;
	GoNext();
	while(CurrentNode && !CurrentNode->Data)
		GoNext();
	return *this;
}
 
template <typename DATA_T>
void Trie<DATA_T>::Iterator::GoPrevious(){
	Node* LeftNode=CurrentNode->LeftChild();
	if(LeftNode){
		Stack.AddLast(CurrentNode);
		CurrentNode=LeftNode;
		GoRight();
		return;
	}
	if(Stack.Count()==0){
		SetBad();
		return;
	}
	typename Array<Node*>::Iterator i=Stack.GetEnd();
	if((*i)->LeftChild()!=CurrentNode){
		typename Array<Node*>::Iterator j=--(*i)->Link.Find(CurrentNode);
		while(!*j)
			--j;
		CurrentNode=*j;
		return;
	}
	while(CurrentNode==(*i)->LeftChild()){
		CurrentNode=*i--;
		Stack.DeleteLast();
		if(Stack.Count()==0){
			SetBad();
			return;
		}
	}
	CurrentNode=*i;
	Stack.DeleteLast();
}
 
 
template <typename DATA_T>
typename Trie<DATA_T>::Iterator& Trie<DATA_T>::Iterator::operator--(){
	if(!CurrentNode)
		return *this;
	GoPrevious();
	while(CurrentNode && !CurrentNode->Data)
		GoPrevious();
	return *this;
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Iterator Trie<DATA_T>::Iterator::operator++(int){
	Iterator Old(*this);
	++*this;
	return Old;
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Iterator Trie<DATA_T>::Iterator::operator--(int){
	Iterator Old(*this);
	--*this;
	return Old;
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Iterator& Trie<DATA_T>::Iterator::operator+=(size_t n){
	for(; n; n--)
		++(*this);
	return *this;
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Iterator& Trie<DATA_T>::Iterator::operator-=(size_t n){
	for(; n; n--)
		--(*this);
	return *this;
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Iterator& Trie<DATA_T>::Iterator::operator=(const Trie<DATA_T>::Iterator& InIterator){
	CurrentNode=InIterator.CurrentNode;
	CurrentTrie=InIterator.CurrentTrie;
	Stack.Clear();
	for(typename Array<Node*>::Iterator i((Array<Node*>&)InIterator.Stack); i; ++i)
		Stack.AddLast(*i);
	return *this;
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Iterator& Trie<DATA_T>::Iterator::operator=(const String& InKey){
	CurrentNode=&CurrentTrie->Start;
	for(size_t i=0; i<InKey.Length(); i++){
		size_t Index=CurrentTrie->IndexByKeyAt(InKey, i);
		if(!CurrentNode->Link[Index])
			throw String("This record does not exist!");
		Stack.AddLast(CurrentNode);
		CurrentNode=CurrentNode->Link[Index];
	}
	return *this;
}
 
template <typename DATA_T>
DATA_T& Trie<DATA_T>::Iterator::operator*(){
	if(!(*this))
		throw String("Reading from bad iterator!");
	return *CurrentNode->Data;
}
 
template <typename DATA_T>
void Trie<DATA_T>::Iterator::Delete(){
	if(!(*this))
		throw String("Delete from bad iterator. Nothing to delete!");
	CurrentTrie->DeleteNodeWithParents(CurrentNode, Stack);
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Iterator Trie<DATA_T>::GetBegin(){
	return Iterator(*this);
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Iterator Trie<DATA_T>::GetEnd(){
	return Iterator(*this, false);
}
 
template <typename DATA_T>
typename Trie<DATA_T>::Iterator Trie<DATA_T>::Find(const DATA_T& Unknown){
	Iterator Result(*this);
	while (Result&& !(*Result==Unknown))
		++Result;
	return Result;
}