SplayTree

#include <assert.h>
#include <iostream>

class CSplayTree {
public:
    ~CSplayTree();

    // Проверяет наличие ключа в дереве. Неконстантный, т.к. перебалансирует дерево в Splay.
    bool Has( int key );
    // Добавление ключа. Если ключ уже есть в дереве, возвращает false.
    bool Add( int key );
    // Удаление ключа. Если ключа нет, то возвращает false.
    bool Remove( int key );

private:
    struct CNode {
        int Key = 0;
        CNode* Left = nullptr;
        CNode* Right = nullptr;
        CNode* Parent = nullptr;
        explicit CNode( int key ) : Key( key ) {}
    };

    CNode* root = nullptr;

    CNode* find( int key );
    void splay( CNode* x );
    void deleteTree( CNode* node );

    // Проверка, что x слева от parent.
    static bool isLeft( const CNode* parent, const CNode* x ) { return parent->Left == x; }
    static void zig( CNode* x );
    static void zigZig( CNode* x );
    static void zigZag( CNode* x );
    static void rotateLeft( CNode* x );
    static void rotateRight( CNode* x );
};

CSplayTree::~CSplayTree()
{
    deleteTree( root );
}

void CSplayTree::deleteTree( CNode* node )
{
    if( node != nullptr ) {
        deleteTree( node->Left );
        deleteTree( node->Right );
        delete node;
    }
}

bool CSplayTree::Has( int key )
{
    if( root == nullptr ) {
        return false;
    }
    CNode* node = find( key );
    splay( node );
    return node->Key == key;
}

bool CSplayTree::Add( int key )
{
    if( root == nullptr ) {
        root = new CNode( key );
        return true;
    }
    CNode* node = find( key );
    if( node->Key == key ) {
        return false;
    }
    // Смотрим, где разместить новый узел.
    CNode*& newNodePlace = node->Key < key ? node->Right : node->Left;
    assert( newNodePlace == nullptr );
    newNodePlace = new CNode( key );
    newNodePlace->Parent = node;

    splay( newNodePlace );

    return true;
}

bool CSplayTree::Remove( int )
{
    // place your code here...
    return false;
}

// Ищем узел, содержащий ключ key.
// Если такого нет, то узел, под который этот ключ можно было бы вставить.
CSplayTree::CNode* CSplayTree::find( int key )
{
    assert( root != nullptr );
    CNode* node = root;
    while( true ) {
        if( node->Key == key ) {
            return node;
        } else if( node->Key < key ) {
            if( node->Right == nullptr ) {
                return node;
            }
            node = node->Right;
        } else {
            if( node->Left == nullptr ) {
                return node;
            }
            node = node->Left;
        }
    }
}

void CSplayTree::splay( CNode* x )
{
    while( x->Parent != nullptr ) {
        if( x->Parent->Parent == nullptr ) {
            zig( x );
        } else if( isLeft( x->Parent, x ) == isLeft( x->Parent->Parent, x->Parent ) ) {
            zigZig( x );
        } else {
            zigZag( x );
        }
    }
    root = x;
}

void CSplayTree::zig( CNode* x )
{
    if( isLeft( x->Parent, x ) ) {
        rotateRight( x->Parent );
    } else {
        rotateLeft( x->Parent );
    }
}

void CSplayTree::zigZig( CNode* x )
{
    if( isLeft( x->Parent, x ) ) {
        rotateRight( x->Parent->Parent );
        rotateRight( x->Parent );
    } else {
        rotateLeft( x->Parent->Parent );
        rotateLeft( x->Parent );
    }
}

void CSplayTree::zigZag( CNode* x )
{
    if( isLeft( x->Parent, x ) ) {
        rotateRight( x->Parent );
        rotateLeft( x->Parent );
    } else {
        rotateLeft( x->Parent );
        rotateRight( x->Parent );
    }
}

void CSplayTree::rotateLeft( CNode* x )
{
    assert( x != nullptr );
    CNode* parent = x->Parent;
    CNode* right = x->Right;
    x->Right = right->Left;
    if( right->Left != nullptr ) {
        right->Left->Parent = x;
    }
    right->Left = x;
    x->Parent = right;
    right->Parent = parent;
    if( parent != nullptr ) {
        if( isLeft( parent, x ) ) {
            parent->Left = right;
        } else {
            parent->Right = right;
        }
    }
}

void CSplayTree::rotateRight( CNode* x )
{
    assert( x != nullptr );
    CNode* parent = x->Parent;
    CNode* left = x->Left;
    x->Left = left->Right;
    if( left->Right != nullptr ) {
        left->Right->Parent = x;
    }
    left->Right = x;
    x->Parent = left;
    left->Parent = parent;
    if( parent != nullptr ) {
        if( isLeft( parent, x ) ) {
            parent->Left = left;
        } else {
            parent->Right = left;
        }
    }
}

int main()
{
    CSplayTree splayTree;
    std::cout << ( !splayTree.Has( 5 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Add( 6 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Has( 6 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( !splayTree.Add( 6 ) ? "Ok" : "Fail" ) << std::endl;

    std::cout << ( splayTree.Add( 4 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Add( 5 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( !splayTree.Has( 7 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Has( 5 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Has( 4 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Has( 6 ) ? "Ok" : "Fail" ) << std::endl;

    std::cout << ( splayTree.Add( 8 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Add( 3 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Has( 8 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Has( 3 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( !splayTree.Has( 7 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Has( 5 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Has( 4 ) ? "Ok" : "Fail" ) << std::endl;
    std::cout << ( splayTree.Has( 6 ) ? "Ok" : "Fail" ) << std::endl;
    return 0;
}