Новичок
Профиль
Группа: Участник
Сообщений: 16
Регистрация: 9.12.2009
Репутация: 1
Всего: 1
|
Необходимо сделать операцию рандомизированного добавления в итеративной форме.Сделал добавление в рекурсивном виде по готовому псевдокоду но не прокатило и я спалился, а на итеративный алгоритм псевдокода к сожалению не имеется  в общем есть итеративный алгоритм Insert добавления в обычное BST дерево (закоментирован подсчёт сыновей у узла) | Код |
bool Insert (K _key, T _data) //Вставка
{
count = 0;
//stack <typename Tree<T,K>::Node*> s;
Node* t = root;
Node* prev;
if (t == NULL)
{
root = new Node(_key, _data);
count++;
size++;
return true;
}
while (t != NULL)
{
count++;
prev = t;
//s.push(t);
if (_key == t->key)
{
return false;
}
if (_key < t->key)
t = t->left;
else
t = t->right;
}
count++;
if (_key < prev->key)
prev->left = new Node(_key, _data);
else
prev->right = new Node(_key, _data);
/*while (!s.empty())
{
t = s.top();
s.pop();
t->n++;
}*/
size++;
return true;
}
|
И есть рекурсивный алгоритм вставки в Рандомизированное дерево | Код |
bool RandInsert(T k,T d)
{
count = 0;
int r=0;
root=_RandInsert(root,k,r,d);
count++;
if (r==0) return false;
return true;
}
////====================================================
Node* _RandInsert(Node* t, T k,int &r,T d)
{
if (t==NULL)
{
t=new Node(k,d);
count++;
r=1;
size++;
return t;
};
if (t->key==k)
{
r=0;
return t;
}
if (rand()<RAND_MAX/((t->n)+1))
{
int k1=t->n;
Node* tmp=_RandRootInsert(t,k,r,d);
tmp->n=k1+1;
return tmp;
};
t->n+=1;
if (k<t->key)
{
t->left=_RandInsert(t->left,k,r,d);
count++;
if (r==0) t->n-=1;
return t;
}
else
{
t->right=_RandInsert(t->right,k,r,d);
count++;
if (r==0) t->n-=1;
return t;
}
}
//////====================================================
//
Node* _RandRootInsert(Node *t,T k,int &r,T d)
{
if (t==NULL)
{
t=new Node(k,d);
r=1;
t->n=0;
count++;
size++;
return t;
}
if (t->key==k)
{
r=0;
return t;
}
if (k<t->key)
{
count++;
t->left=_RandRootInsert(t->left,k,r,d);
return Right(t,t->left);
}
else
{
count++;
t->right=_RandRootInsert(t->right,k,r,d);
return Left(t,t->right);
}}
Node* Right(Node *t, Node *x)
{
Node *p=x->right;
x->right=t;
t->left=p;
calc_n(t);
calc_n(x);
return x;
}
Node *Left(Node *t, Node *x)
{
Node *p=x->left;
x->left=t;
t->right=p;
calc_n(t);
calc_n(x);
return x;
}
|
Прошу народных умельцев собрать из этих алгоритмов итеративный для добавления в радномизированное дерево у самого что то никак. | Код |
#include <iostream>
#include <stack>
using namespace std;
template <class T, class K> class Tree
{
class Node
{
public:
Node *left; //Указатель на левого сына
Node *right; //Указатель на правого сына
int n; //Размер поддерева
T data; //Ключ
K key; //Данные
public:
Node (K _key, T _data) //Конструктор
{
left = right = NULL;
data = _data;
key = _key;
n = 1;
}
Node (Node &node) //Конструктор копирования
{
key = node.key;
data = node.data;
n = 1;
left = right = NULL;
}
void printNode () //Печать узла
{
cout << "<key: " << key << "; data: " << data << ">";
}
};
friend class Node;
Node *root; //Указатель на корень дерева
int size; //Размер дерева
int count;
void calc_n (Node *t)
{
if (t != NULL)
{
if (t->left != NULL)
t->n = 1 + (t->left)->n;
else
t->n = 1;
if (t->right != NULL)
t->n = t->n + (t->right)->n;
}
}
public:
bool Insert (K _key, T _data) //Вставка
{
count = 0;
//stack <typename Tree<T,K>::Node*> s;
Node* t = root;
Node* prev;
if (t == NULL)
{
root = new Node(_key, _data);
count++;
size++;
return true;
}
while (t != NULL)
{
count++;
prev = t;
//s.push(t);
if (_key == t->key)
{
return false;
}
if (_key < t->key)
t = t->left;
else
t = t->right;
}
count++;
if (_key < prev->key)
prev->left = new Node(_key, _data);
else
prev->right = new Node(_key, _data);
/*while (!s.empty())
{
t = s.top();
s.pop();
t->n++;
}*/
size++;
return true;
}
////////////////////////////////////////////////////////////////////////////
bool RandInsert(T k,T d)
{
count = 0;
int r=0;
root=_RandInsert(root,k,r,d);
count++;
if (r==0) return false;
return true;
}
////====================================================
Node* _RandInsert(Node* t, T k,int &r,T d)
{
if (t==NULL)
{
t=new Node(k,d);
count++;
r=1;
size++;
return t;
};
if (t->key==k)
{
r=0;
return t;
}
if (rand()<RAND_MAX/((t->n)+1))
{
int k1=t->n;
Node* tmp=_RandRootInsert(t,k,r,d);
tmp->n=k1+1;
return tmp;
};
t->n+=1;
if (k<t->key)
{
t->left=_RandInsert(t->left,k,r,d);
count++;
if (r==0) t->n-=1;
return t;
}
else
{
t->right=_RandInsert(t->right,k,r,d);
count++;
if (r==0) t->n-=1;
return t;
}
}
//////====================================================
//
Node* _RandRootInsert(Node *t,T k,int &r,T d)
{
if (t==NULL)
{
t=new Node(k,d);
r=1;
t->n=0;
count++;
size++;
return t;
}
if (t->key==k)
{
r=0;
return t;
}
if (k<t->key)
{
count++;
t->left=_RandRootInsert(t->left,k,r,d);
return Right(t,t->left);
}
else
{
count++;
t->right=_RandRootInsert(t->right,k,r,d);
return Left(t,t->right);
}}
Node* Right(Node *t, Node *x)
{
Node *p=x->right;
x->right=t;
t->left=p;
calc_n(t);
calc_n(x);
return x;
}
Node *Left(Node *t, Node *x)
{
Node *p=x->left;
x->left=t;
t->right=p;
calc_n(t);
calc_n(x);
return x;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool RandDelete(T k)
{
count = 0;
int r=0;
root=_RandDelete(root,k,r);
if (r==0) return false;
else size--;
return true;
}
Node* _RandDelete(Node *t,T k,int &r)
{
if (t==NULL)
{
r=0;
return NULL;
}
if (k<t->key)
{
count++;
t->left=_RandDelete(t->left,k,r);
if (r==1) t->n--;
calc_n(t);
return t;
}
if (k>t->key)
{
count++;
t->right=_RandDelete(t->right,k,r);
if (r==1) t->n--;
calc_n(t);
return t;
}
Node *tmp=t;
t=Join_LR(t->left,t->right);
calc_n(t);
delete tmp;
r=1;
return t;
}
Node* Join_LR(Node* t,Node* t1)
{
if (t==NULL) {return t1;}
if (t1==NULL){return t; }
if((t->n)<=0){
calc_n(t1);
return t1;
}
if((t1->n)<=0){
calc_n(t);
return t;
}
if ((rand()/(RAND_MAX/((t->n)+(t1->n)+1)))<t->n)
{
t->right=Join_LR(t->right,t1);
calc_n(t);
count++;
return t;
}
else
{
t1->left=Join_LR(t,t1->left);
calc_n(t1);
count++;
return t1;
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bool Delete (K _key) //Удаление по ключу
{
Node *t = root;
//stack <typename Tree<T,K>::Node*> s;
Node *prev = NULL, *next, *temp;
count = 0;
while (t != NULL && t->key != _key){
count++;
//s.push(t);
prev = t;
if (_key < t->key)
t = t->left;
else
t = t->right;
}
count++;
if (t == NULL)
return false;
//s.push(t);
if (t->left != NULL && t->right != NULL)
{
temp = t;
prev = t;
t = t->right;
//s.push(t);
while (t->left != NULL)
{
count++;
prev = t;
t = t->left;
//s.push(t);
}
next = t->right;
}
else
{
temp = NULL;
if (t->left == NULL)
next = t->right;
if (t->right == NULL)
next = t->left;
}
if (prev == NULL)
{
root = next;
delete t;
size--;
return true;
}
else
if (t->key < prev->key)
prev->left = next;
else
prev->right = next;
if (temp != NULL)
{
temp->key = t->key;
temp->data = t->data;
}
//s.pop();
delete t;
/*while (!s.empty())
{
t = s.top();
s.pop();
calc_n(t);
}*/
size--;
return true;
}
};
|
|
[C++]Рандомизированное дерево поиска на основе BST, Итеративный алгоритм вставки. 
Загрузка ...
