lab6

// lab6.cpp: определяет точку входа для консольного приложения.
//

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

template <typename T>
struct entry {
    int key;
    T value;
};

template <typename T>
struct node {
    int key;
    T value;
    node<T> *left, *right;
    int height;
};

template <typename T>
class bst {

private:
    node<T>* root;
    int node_count;

protected:
    void height_fix() {
        this.height = max(this->left.height, this->right.height) + 1;
        return;
    }

    node<T>* rotate_r() {
        node<T>* new_root = this.left;
        this.left = new_root.right;
        new_root.right = this;
        this.height_fix();
        new_root.hight_fix();
        return new_root;
    }

    node<T>* rotate_l() {
        node<T>* new_root = this.right;
        this.right = new_root.left;
        new_root.left = this;
        this.height_fix();
        new_root.hight_fix();
        return new_root;
    }

    node<T>* balance() {
        this.height_fix();
        int bfactor = this->left.height - this->right.height;
        if (bfactor == 2) {
            if (this->right->left.height > this->right->right.height)
                this.right = this->right.rotate_r;
            return this.rotate_l();
        }
        if (bfactor == -2) {
            if (this->right->left.height < this->right->right.height)
                this.left = this->left.rotate_l;
            return this.rotate_r();
        }
        return this;
    }

    node<T>* balance(const vector<node<T>* > path) {
        for (int i = path.size() - 2; i + 1; i--)
            path[i].left == path[i + 1] ? path[i].left = path[i + 1].balance() : path[i].right = path[i + 1].balance();
        root = root.balance();
        return root;
    }

public:
    bst() {
        root = NULL;
        node_count = 0;
    }

    void insert(const int key, const T value) {
        node<T>* ins;
        ins.key = key;
        ins.value = value;
        ins.left = ins.right = NULL;
        ins.height = 1;
        if (!cur) {
            root = ins;
            node_count = 1;
            return;
        }
        node<T>* cur = root;
        vector<node<T>* > path;
        while (!cur) {
            path.push_back(cur);
            cur.key > key ? cur = cur->left : cur = cur->right;
        }
        path.back.key > key ? path.back.left = ins : path.back.right = ins;
        root = this.balance(path&);
        node_count++;
        return;
    }

    node<T>* find(const int key, node<T>* cur = root) {
        if (!cur)
            return NULL;
        if (key == cur.key)
            return cur;
        key < cur.key ? find(key, cur.left) : find(key, cur.right);
    }

    node<T>* find(const node<T>* target, node<T>* cur = root) {
        if (cur.left == target || cur.right == target)
            return cur;
        target.key < cur.key ? find(target, cur.left) : find(target, cur.right);
    }

    void remove(const int key) {
        if (!node_count)
            return;
        node<T>* cur = root;
        vector<node<T>* > path;
        do {
            path.push_back(cur);
            cur.key > key ? cur = cur->left : cur = cur->right;
        } while (key != cur.key && !cur);
        if (!cur)
            return;
        if (!cur.left || !cur.right) {
            if (cur.left = cur.right) {
                path.back.left == cur ? path.back.left = NULL : path.back.right = NULL;
                delete cur;
                root = this.balance(path&);
                return;
            }
            if (!cur.left)
                path.back.left == cur ? path.back.left = cur.left : path.back.right = cur.left;
            else
                path.back.left == cur ? path.back.left = cur.right : path.back.right = cur.right;
            delete cur;
            root = this.balance(path&);
            return;
        }
        node<T> cur_p = path.back;
        node<T> max = max.left;
        do {
            path.push_back(max);
            max = max.right;
        } while (!cur);
        path.back.right = NULL;
        cur_p.left == cur ? cur_p.left = max : cur_p.right = max;
        max.left = cur.left;
        max.right = cur.right;
        delete cur;
        root = this.balance(path&);
        return;
    }

    /*void remove(int key) {
        if (!node_count)
            return;
        node<T>* del = find(key);
        if (!del)
            return;
        node<T>* del_p = find(del);
        if (!del.left || !del.right) {
            if (del.left == del.right) {
                del_p.left == del ? del_p.left = NULL : del_p.right = NULL;
                delete del;
                return;
            }
            if (!del.left)
                del_p.left == del ? del_p.left = del.right : del_p.right = del.right;
            else
                del_p.left == del ? del_p.left = del.left : del_p.right = del.left;
            delete del;
            return;
        }
        node<T> *cur = del.left, *cur_p = del;
        while (cur->right) {
            cur_p = cur;
            cur = cur.right;
        }
        cur_p.right = cur.left;
        del_p.left == del ? del_p.left = cur : del_p.right = cur;
        cur.left = del.left;
        cur.right = del.right;
        delete del;
    }

    void insert(int key, T value) {
        node<T> *cur = new node<T>;
        cur.key = key;
        cur.value = value;
        cur.left = cur.right = NULL;
        if (!root) {
            root = cur;
            node_count = 1;
            return;
        }
        node<T>* cur_xst = root;
        while (true){
            if (key == cur_xst.key) {
                cur_xst.value = value;
                break;
            }
            if (key < cur_xst.key) {
                if (!cur_xst.left) {
                    cur_xst.left = cur;
                    break;
                }
                else
                    cur_xst = cur_xst.left;
            else {
                if (!cur_xst.right) {
                    cur_xst.right = cur;
                    break;
                }
                else
                    cur_xst = cur_xst.right;
            }
            }
        }
        node_count++;
    }

    void insert(vector v, int idx_b = 0, int idx_e = v.size()-1) {
        int avg = (idx_b + idx_e) /2;
        this.insert(v[avg].key, v[avg].value);
        this.insert(v, idx_b, avg);
        this.insert(v, avg, idx_e);
    }*/
};

int _tmain(int argc, _TCHAR* argv[])
{
    bst<int> t;
    for (int i = 1; i <= 6; i++) {
        t.insert(i, i);
    }
    t.remove(5);
    cout << t.find(3).value << endl;

    return 0;
}