#include <iostream>
#include<fstream>
#include<cstring>
#include<chrono>
using namespace std;
struct Node {
string data;
int ile=1;
Node *parent;
Node *left;
Node *right;
};
typedef Node *NodePtr;
class SplayTree {
private:
int maxdepth=0;
int counter = 0;
NodePtr root;
void preOrderHelper(NodePtr node) {
if (node != nullptr) {
cout<<node->data<<" ";
preOrderHelper(node->left);
preOrderHelper(node->right);
}
}
void inOrderHelper(NodePtr node) {
if (node != nullptr) {
inOrderHelper(node->left);
cout<<node->data<<" ";
inOrderHelper(node->right);
}
}
void postOrderHelper(NodePtr node) {
if (node != nullptr) {
postOrderHelper(node->left);
postOrderHelper(node->right);
cout<<node->data<<" ";
}
}
NodePtr searchTreeHelper(NodePtr node, string key) {
counter++;
if (node == nullptr || key == node->data) {
return node;
}
if (key < node->data) {
return searchTreeHelper(node->left, key);
}
return searchTreeHelper(node->right, key);
}
void deleteNodeHelper(NodePtr node, string key) {
NodePtr x = nullptr;
NodePtr t, s;
while (node != nullptr){
if (node->data == key) {
x = node;
}
if (node->data <= key) {
node = node->right;
} else {
node = node->left;
}
}
if (x == nullptr) {
cout<<"Couldn't find key in the tree"<<endl;
return;
}
split(x, s, t);
if (s->left){
s->left->parent = nullptr;
}
root = join(s->left, t);
delete(s);
s = nullptr;
}
void printHelper(NodePtr root, string indent, bool last) {
if (root != nullptr) {
cout<<indent;
cout<<root->data<<endl;
printHelper(root->left, indent, false);
printHelper(root->right, indent, true);
}
}
void leftRotate(NodePtr x) {
NodePtr y = x->right;
x->right = y->left;
if (y->left != nullptr) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
this->root = y;
} else if (x == x->parent->left) {
x->parent->left = y;
} else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
void rightRotate(NodePtr x) {
NodePtr y = x->left;
x->left = y->right;
if (y->right != nullptr) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
this->root = y;
} else if (x == x->parent->right) {
x->parent->right = y;
} else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
// splaying
void splay(NodePtr x) {
while (x->parent) {
if (!x->parent->parent) {
if (x == x->parent->left) {
// zig rotation
rightRotate(x->parent);
} else {
// zag rotation
leftRotate(x->parent);
}
} else if (x == x->parent->left && x->parent == x->parent->parent->left) {
// zig-zig rotation
rightRotate(x->parent->parent);
rightRotate(x->parent);
} else if (x == x->parent->right && x->parent == x->parent->parent->right) {
// zag-zag rotation
leftRotate(x->parent->parent);
leftRotate(x->parent);
} else if (x == x->parent->right && x->parent == x->parent->parent->left) {
// zig-zag rotation
leftRotate(x->parent);
rightRotate(x->parent);
} else {
// zag-zig rotation
rightRotate(x->parent);
leftRotate(x->parent);
}
}
}
// joins two trees s and t
NodePtr join(NodePtr s, NodePtr t){
if (!s) {
return t;
}
if (!t) {
return s;
}
NodePtr x = maximum(s);
splay(x);
x->right = t;
t->parent = x;
return x;
}
// splits the tree into s and t
void split(NodePtr &x, NodePtr &s, NodePtr &t) {
splay(x);
if (x->right) {
t = x->right;
t->parent = nullptr;
} else {
t = nullptr;
}
s = x;
s->right = nullptr;
x = nullptr;
}
NodePtr maxDepth(NodePtr node, int g)
{
if (node == NULL)
{
if(g>maxdepth)maxdepth=g;
return 0;
}
else
{
g++;
maxDepth(node->left, g);
maxDepth(node->right, g);
}
}
public:
SplayTree() {
root = nullptr;
}
void preorder() {
preOrderHelper(this->root);
}
void inorder() {
inOrderHelper(this->root);
}
void postorder() {
postOrderHelper(this->root);
}
NodePtr searchTree(string k) {
NodePtr x = searchTreeHelper(this->root, k);
if (x) {
splay(x);
}
if(x==0) cout<<"brak";
else cout<<"jest";
return x;
}
NodePtr minimum(NodePtr node) {
while (node->left != nullptr) {
node = node->left;
}
return node;
}
NodePtr maximum(NodePtr node) {
while (node->right != nullptr) {
node = node->right;
}
return node;
}
NodePtr successor(NodePtr x) {
if (x->right != nullptr) {
return minimum(x->right);
}
NodePtr y = x->parent;
while (y != nullptr && x == y->right) {
x = y;
y = y->parent;
}
return y;
}
NodePtr predecessor(NodePtr x) {
if (x->left != nullptr) {
return maximum(x->left);
}
NodePtr y = x->parent;
while (y != nullptr && x == y->left) {
x = y;
y = y->parent;
}
return y;
}
void insertow() {cout<<"Znaleziono wykonujac "<<counter<<" Operacji"<<endl;}
void insert(string key, int ile) {
NodePtr node = new Node;
node->parent = nullptr;
node->left = nullptr;
node->right = nullptr;
node->data = key;
NodePtr y = nullptr;
NodePtr x = this->root;
while (x != nullptr) {
y = x;
if (node->data < x->data) {
x = x->left;
}
else
{
x = x->right;
}
}
node->parent = y;
if (y == nullptr) {
root = node;
} else if (node->data < y->data) {
y->left = node;
splay(node);
} else if(node->data > y->data){
y->right = node;
splay(node);
}
else{
node->ile++;
}
}
NodePtr getRoot(){
return this->root;
}
void prettyPrint() {
printHelper(this->root, "", true);
}
void depth(){int g=0;
root = maxDepth(root, g);cout<<maxdepth<<endl;}
};
int main() {
SplayTree bst;
fstream tekst;
tekst.open("joyland.txt", ios::in);
string slowo;
int ile=1;
auto t1 = std::chrono::high_resolution_clock::now();
while(tekst >> slowo){bst.insert(slowo, ile);}
auto t2 = std::chrono::high_resolution_clock::now();
double durat = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
cout<<"W czasie "<<durat<<" mikrosekund"<<endl;
tekst.close();
// bst.prettyPrint();
cout<<"Szukanie liczb: (wpisz 'stop' aby przerwac i wyswietlic wysokosc drzewa)"<<endl;
while(true)
{
string szukamy;
cout<<"Co mam znalezc?"<<endl;
cin>>szukamy;
if(szukamy=="stop") break;
bst.searchTree(szukamy);
}
bst.insertow();
cout << "Wysokosc drzewa: ";
bst.depth();
return 0;
}
