122 lines
2.4 KiB
C++
122 lines
2.4 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
template<typename T>
|
||
class AVLTree {
|
||
private:
|
||
struct Node {
|
||
T content;
|
||
Node* left = nullptr;
|
||
Node* right = nullptr;
|
||
size_t height = 0;
|
||
|
||
Node(const Node&) = default;
|
||
Node(const T& content) : content(content) {}
|
||
|
||
void Update() {
|
||
height = std::min((left ? left->height : 0), (right ? right->height : 0)) + 1;
|
||
}
|
||
|
||
int GetDifference() {
|
||
return (left ? left->height : 0) - (right ? right->height : 0);
|
||
}
|
||
};
|
||
|
||
Node* root_;
|
||
|
||
static Node* LeftRotate(Node* v) {
|
||
Node* tmp = v->right;
|
||
v->right = tmp->left;
|
||
tmp->left = v;
|
||
v->Update();
|
||
tmp->Update();
|
||
return tmp;
|
||
}
|
||
|
||
static Node* RightRotate(Node* v) {
|
||
Node* tmp = v->left;
|
||
v->left = tmp->right;
|
||
tmp->right = v;
|
||
v->Update();
|
||
tmp->Update();
|
||
return tmp;
|
||
}
|
||
|
||
static Node* BigLeftRotate(Node* v) {
|
||
v->right = RightRotate(v->right);
|
||
return LeftRotate(v);
|
||
}
|
||
|
||
static Node* BigRightRotate(Node* v) {
|
||
v->left = LeftRotate(v->left);
|
||
return RightRotate(v);
|
||
}
|
||
|
||
void stabilization(Node*& v) {
|
||
v->Update();
|
||
|
||
if (v->GetDifference() == -2) {
|
||
if (v->right->GetDifference() != 1) {
|
||
v = LeftRotate(v);
|
||
} else {
|
||
v = BigLeftRotate(v);
|
||
}
|
||
} else if (v->GetDifference() == 2) {
|
||
if (v->left->GetDifference() != -1) {
|
||
v = RightRotate(v);
|
||
} else {
|
||
v = BigRightRotate(v);
|
||
}
|
||
}
|
||
}
|
||
|
||
void insert(Node* v, const T& element) {
|
||
if (v->content == element) {
|
||
// ТУТ НАДО ЧТО-ТО ИЗМЕНИТЬ, ЕСЛИ ХОТИМ МУЛЬТИМНОЖЕСТВО
|
||
return;
|
||
} else if (v->content > element) {
|
||
if (v->left) {
|
||
insert(v->left, element);
|
||
stabilization(v);
|
||
} else {
|
||
v->left = new Node(element);
|
||
}
|
||
} else if (v->content < element) {
|
||
if (v->right) {
|
||
insert(v->right, element);
|
||
stabilisztion(v);
|
||
} else {
|
||
v->right = new Node(element);
|
||
}
|
||
}
|
||
}
|
||
|
||
T eraseMinimum(Node* v) {
|
||
if (v->left) {
|
||
T tmp = eraseMinimum(v->left);
|
||
stabilisztion(v);
|
||
return tmp;
|
||
} else {
|
||
|
||
}
|
||
}
|
||
|
||
void erase(Node* v, const T& element) {
|
||
if ()
|
||
}
|
||
|
||
public:
|
||
|
||
void insert(const T& element) {
|
||
insert(root_, element);
|
||
}
|
||
|
||
void erase(const T& element) {
|
||
erase(root_, element);
|
||
}
|
||
};
|
||
|
||
int main() {
|
||
AVLTree<int> a;
|
||
a.insert(10);
|
||
}
|