Начало
Учебные материалы
Структуры данных на основе деревьев
Определения Обходы бинарного дерева Двоичное дерево поиска Система непересекающихся множеств Сбалансированные деревья Декартово дерево Декартово дерево по неявному ключу Дерево отрезков
Декартово дерево по неявному ключу
Основные операции:
Операция|Эффективность|Вызов
--|--|--
создать пустой набор |`O(1)`| ``ITreap<int> t;``
количество элементов |`O(1)`| ``size_t kol=t.size();``
получить/изменить i-й |`O(log N)`| ``auto v=t[i]; t[i]=4;``
удалить i-й |`O(log N)`| ``t.erasei(i);``
вставить значение v перед i-м |`O(log N)`| ``it.inserti(i,v);``
внутренний итератор |`O(n)`| ``t.foreach([&](int& v) { cout<<v<<"\n";});``
--
```
template <typename T>
class ITreap {
struct node {
T v; // значение элемента
size_t k; // неявный ключ - количество элементов в поддереве
int y; // случайная высота
node *left=nullptr, *right=nullptr;
node(T v) : v(v), k(1), y(rand()) { }
void update() { k=1+size(left)+size(right); }
};
node *root;
static size_t size(node *n) { return n?n->k:0; }
public:
ITreap():root(nullptr) {}
ITreap(const ITreap&)=delete; // запрет копирования
ITreap& operator=(const ITreap&)=delete; // запрет присваивания
~ITreap() { free(root); }
size_t size() const { return size(root); } // размер
...
};
```
--
Операции разрезания и слияния останутся почти такими же, но добавится вызов update для пересчета количества элементов в поддереве:
```
private:
pair<node*, node*> spliti(node* t, size_t k) { // разрезание по количеству
if (!t || k>=t->k) return {t,nullptr};
if(k==0) return {nullptr,t};
size_t l=size(t->left);
if (l<k) {
auto [t1,t2]=spliti(t->right,k-l-1);
t->right=t1;
t->update();
return {t,t2};
} else {
auto [t1,t2]=spliti(t->left,k);
t->left=t2;
t->update();
return {t1,t};
}
}
node* merge(node* t1, node* t2) { // слияние
if(!t2) return t1;
if(!t1) return t2;
if (t1->y > t2->y) {
t1->right=merge(t1->right,t2);
t1->update();
return t1;
} else {
t2->left=merge(t1,t2->left);
t2->update();
return t2;
}
}
```
--
```
node* find(size_t k) const { // поиск узла по номеру
node *p=root;
while(p) {
int l=size(p->left);
if(l==k) break;
else if(k<l) p=p->left;
else { k-=l+1; p=p->right; }
}
return p;
}
void foreach(function<void(T&)> f, node *p) // обход дерева
{
if(!p) return;
foreach(f,p->left);
f(p->v);
foreach(f,p->right);
}
```
--
```
public:
T& operator[](size_t k) { // доступ к элементу по индексу
if(k>=size()) throw runtime_error("Wrong index");
node *p=find(k);
return p->v;
}
T operator[](size_t k) const {
if(k>=size()) throw runtime_error("Wrong index");
node *p=find(k);
return p->v;
}
```
--
```
void inserti(size_t k, T v) { // вставка
if(k>size()) throw runtime_error("Wrong index");
node *m=new node(v);
auto [t1,t2]=spliti(root,k);
root=merge(merge(t1,m),t2);
}
void erasei(size_t k) { // удаление
if(k>=size()) throw runtime_error("Wrong index");
auto [t1,t]=spliti(root, k);
auto [m,t2]=spliti(t, 1);
root=merge(t1,t2);
free(m);
}
void foreach(function<void(T&)> f) {
foreach(f,root);
}
```
--
Пример использования:
```
int main()
{ ITreap<int> t;
t.inserti(0,10); // {10}
t.inserti(1,20); // {10,20}
t.inserti(1,15); // {10,15,20}
t.foreach([&](int& v){ cout<<v<<"\n";});
t[2]=25; // {10,15,25}
t.erasei(1); // {10,25}
cout<<t[0]<<"\n";
cout<<t[1]<<"\n";
}
```
--
Если совместить дерево с доступом по ключу и дерево с неявным ключом, то можно определить операции получения ключа по номеру и номера по ключу:
```c++
template <typename Key>
class KTreap {
struct node {
Key x; // ключ
size_t k; // неявный ключ - количество элементов в поддереве
int y; // случайная высота
node *left=nullptr, *right=nullptr;
node(Key x) : x(x), k(1), y(rand()) { }
void update() { k=1+size(left)+size(right); }
};
node *root;
...
public:
KTreap():root(nullptr) {}
KTreap(const KTreap&)=delete; // запрет копирования
KTreap& operator=(const KTreap&)=delete; // запрет присваивания
~KTreap() { free(root); }
size_t size() const { return size(root); } // размер
bool contains(Key k) const; // поиск как у всех BST
size_t order(Key k) const { // номер элемента по ключу
size_t ind=0;
node *n=root;
while(n)
{ if(k<n->x)
n=n->left;
else {
ind+=size(n->left);
if(n->x<k) {
++ind;
n=n->right;
}
else return ind;
}
}
return -1;
}
Key key(size_t k) const { // элемент по номеру
if(k>=size()) throw runtime_error("Wrong index");
node *p=find(k);
return p->x;
}
void visit(function<void(Key)> fun) const;
void insert(Key k);
void erase(Key k);
void erasei(size_t k);
};
```
Операция inserti не применима к этому классу.
