TreesPresentation/SplayTree.h at master · samplec0de/TreesPresentation · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//
// Created by Андрей Москалёв on 24.10.2019.
//

#ifndef TREESPRESENTATION_SPLAYTREE_H
#define TREESPRESENTATION_SPLAYTREE_H

#include "Node.h"
#include <algorithm>

class SplayTree {
public:
    Node * root = nullptr;
    void insert(int key) {
        root = _insert(key, root);
    }
    void remove(int key) {
        root = _remove(key, root);
    }
    int height() {
        return _height(root);
    }

private:
    Node * _rotateRight(Node * k2);

    Node * _rotateLeft(Node * k2);

    Node * _splay(int key, Node * root);

    Node * _insert(int key, Node * root);

    Node * _remove(int key, Node * root);

    Node * _findNode(int key, Node * root);

    int _height(Node * x);
};


#endif //TREESPRESENTATION_SPLAYTREE_H