Balanced Tree

Turmoil · 2020-01-18 17:32:47 · 个人记录

Balanced Tree

Size Balanced Tree

C++ source file

#include <cstdio>
#include <cstring>
#include <algorithm>
#include "size_balanced_tree.h"

using namespace std;

Size_Balanced_Tree<int> tree;

int main()
{
    int n;
    int opt, x;

//  freopen("cpp.in", "r", stdin);
//  freopen("cpp.out", "w", stdout);

    scanf("%d", &n);
    for (register int i = 1; i <= n; i++)
    {
        scanf("%d %d", &opt, &x);
        switch (opt)
        {
        case 1:
            printf("No.%-2d Insert: %d\n", i, x);
            tree.insert(tree.getRoot(), x);
            break;
        case 2:
            printf("No.%-2d Delete: %d\n", i, tree.erase(tree.getRoot(), x));
            tree.erase(tree.getRoot(), x);
            break;
        case 3:
            printf("No.%-2d Rank: %d\n", i, tree.getRank(tree.getRoot(), x));
            //printf("%d\n", tree.getRank(tree.getRoot(), x));
            break;
        case 4:
            printf("No.%-2d Select: %d\n", i, tree.select(tree.getRoot(), x));
            //printf("%d\n", tree.select(tree.getRoot(), x));
            break;
        case 5:
            printf("No.%-2d Predecessor: %d\n", i, tree.predecessor(tree.getRoot(), x));
            //printf("%d\n", tree.predecessor(tree.getRoot(), x));
            break;
        case 6:
            printf("No.%-2d Successor: %d\n", i, tree.successor(tree.getRoot(), x));
            //printf("%d\n", tree.successor(tree.getRoot(), x));
            break;
        default:
            break;
        }
    }

//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

C++ header file

#ifndef _SIZE_BALANCED_TREE_H_
#define _SIZE_BALANCED_TREE_H_

const int SIZE_BALANCED_TREE_SIZE = 1024;

template<typename _T>
struct Node
{
    _T key;
    int left, right;
    int size;

    Node()
    {
        key = 0;
        left = right = 0;
        size = 0;
    }
};

template<typename _T>
class Size_Balanced_Tree
{
private:
    Node<_T> node[SIZE_BALANCED_TREE_SIZE];
    int size;
    int root;

    void maintain(int &k, bool flag);
    void leftRotate(int &k);
    void rightRotate(int &k);

public:
    Size_Balanced_Tree();
    int &getRoot(); //return reference of root in private domain
    void insert(int &k, _T key);
    _T erase(int &k, _T key);
    _T predecessor(int &k, _T key);
    _T successor(int &k, _T key);
    _T maximum(int k);
    _T minimum(int k);
    _T select(int &k, int rank);
    _T getRank(int &k, _T key);
    void show(int k);
};

template<typename _T>
void Size_Balanced_Tree<_T>::maintain(int &k, bool flag)
{
    if (!flag)  //left has been changed, so only check left
    {
        if (node[node[node[k].left].left].size > node[node[k].right].size)
            rightRotate(k);
        else if (node[node[node[k].left].right].size > node[node[k].right].size)
        {
            leftRotate(node[k].left);
            rightRotate(k);
        }
        else
            return ;
    }
    else    //right has been changed
    {
        if (node[node[node[k].right].right].size > node[node[k].left].size)
            leftRotate(k);
        else if (node[node[node[k].right].left].size > node[node[k].left].size)
        {
            rightRotate(node[k].right);
            leftRotate(k);
        }
        else
            return ;
    }
    maintain(node[k].left, false);
    maintain(node[k].right, true);
    maintain(k, true);
    maintain(k, false);
}
template<typename _T>
void Size_Balanced_Tree<_T>::leftRotate(int &k)
{
    int new_root = node[k].right;

    if (new_root == 0)  //have no right subtree
        return ;

    node[k].right = node[new_root].left;
    node[new_root].left = k;
    node[new_root].size = node[k].size;
    node[k].size = node[node[k].left].size + node[node[k].right].size + 1;
    k = new_root;
}
template<typename _T>
void Size_Balanced_Tree<_T>::rightRotate(int &k)
{
    int new_root = node[k].left;

    if (new_root == 0)  //have no left subtree
        return ;

    node[k].left = node[new_root].right;
    node[new_root].right = k;
    node[new_root].size = node[k].size;
    node[k].size = node[node[k].left].size + node[node[k].right].size + 1;
    k = new_root;
}
template<typename _T>
Size_Balanced_Tree<_T>::Size_Balanced_Tree()
{
    memset(node, 0, sizeof(node));
    root = 0;
    size = 0;
}
template<typename _T>
int& Size_Balanced_Tree<_T>::getRoot()  //just this
{
    return root;
}
template<typename _T>
void Size_Balanced_Tree<_T>::insert(int &k, _T key)
{
    if (k == 0)
    {
        k = ++size;
        node[k].key = key;
        node[k].left = 0;
        node[k].right = 0;
        node[k].size = 1;
    }
    else
    {
        node[k].size++;
        if (key < node[k].key)
            insert(node[k].left, key);
        else
            insert(node[k].right, key);
        maintain(k, key >= node[k].key);
    }
}
template<typename _T>
_T Size_Balanced_Tree<_T>::erase(int &k, _T key)
{
    _T rv;

    node[k].size--; //remember this
    if ((key == node[k].key) || (key < node[k].key && node[k].left == 0) || (key > node[k].key && node[k].right == 0))
    {
        //find the exact one, or have no way to go on
        rv = node[k].key;

        if (node[k].left == 0 || node[k].right == 0)
            k = node[k].left + node[k].right;
        else    //node[k].key == key
            node[k].key = erase(node[k].left, node[k].key + 1); //the greatest one in the left subtree
    }
    else if (key < node[k].key)
        rv = erase(node[k].left, key);
    else
        rv = erase(node[k].right, key);

    return rv;
}
template<typename _T>
_T Size_Balanced_Tree<_T>::predecessor(int &k, _T key)  //the greatest but still smaller than it
{
    if (k == 0)
        return key;
    _T rv;
    if (key <= node[k].key)
        rv = predecessor(node[k].left, key);
    else
    {
        rv = predecessor(node[k].right, key);
        if (rv == key)  //now, node[k].key < key
            rv = node[k].key;
    }

    return rv;
}
template<typename _T>
_T Size_Balanced_Tree<_T>::successor(int &k, _T key)    //the smallest but still greater than it
{
    if (k == 0)
        return key;
    _T rv;
    if (key >= node[k].key)
        rv = successor(node[k].right, key);
    else
    {
        rv = successor(node[k].left, key);
        if (rv == key)
            rv = node[k].key;
    }

    return rv;
}
template<typename _T>
_T Size_Balanced_Tree<_T>::maximum(int k)
{
    while (node[k].right != 0)
        k = node[k].right;

    return node[k].key;
}
template<typename _T>
_T Size_Balanced_Tree<_T>::minimum(int k)
{
    while (node[k].left != 0)
        k = node[k].left;

    return node[k].key;
}
template<typename _T>
_T Size_Balanced_Tree<_T>::select(int &k, int rank)
{
    _T rv;

    if (rank == node[node[k].left].size + 1)
        rv = node[k].key;
    else if (rank <= node[node[k].left].size)
        rv = select(node[k].left, rank);
    else
        rv = select(node[k].right, rank - node[node[k].left].size - 1);

    return rv;
}   
template<typename _T>
_T Size_Balanced_Tree<_T>::getRank(int &k, _T key)
{
    if (k == 0)
        return 1;

    _T rv = 0;

    if (key <= node[k].key)
        rv = getRank(node[k].left, key);
    else
        rv = node[node[k].left].size + 1 + getRank(node[k].right, key);

    return rv;
}

#endif