/Users/jst/src/grafalgo/cpp/dataStructures/searchTrees/SaBstSet.cpp

Go to the documentation of this file.

#include "SaBstSet.h"

#define left(x) node[x].left
#define right(x) node[x].right
#define p(x) node[x].p
#define kee(x) node[x].kee

namespace grafalgo {

SaBstSet::SaBstSet(int size) : BstSet(size) {}

SaBstSet::~SaBstSet() {}

index SaBstSet::splay(index x) {
        while (p(x) != 0) splaystep(x);
        return x;
}

void SaBstSet::splaystep(index x) {
        index y = p(x);
        if (y == 0) return;
        index z = p(y);
        if (z != 0) {
                if (x == left(left(z)) || x == right(right(z)))
                        rotate(y);
                else // x is "inner grandchild"
                        rotate(x);
        }
        rotate(x);
}

bst SaBstSet::find(index i) { return splay(i); }

index SaBstSet::access(keytyp k, bst& t) {
        assert (0 <= t && t <= n());
        index x = t;
        while (true) {
                     if (k < kee(x) && left(x) != 0) x = left(x);
                else if (k > kee(x) && right(x) != 0) x = right(x);
                else break;
        }
        splay(x); t = x;
        return key(x) == k ? x : 0;
}

bool SaBstSet::insert(index i, bst& t) {
        if (t == 0) { t = i; return true; }
        index x = t;
        while (1) {
                     if (kee(i) < kee(x) &&  left(x) != 0) x = left(x);
                else if (kee(i) > kee(x) && right(x) != 0) x = right(x);
                else break;
        }
             if (kee(i) < kee(x))  left(x) = i;
        else if (kee(i) > kee(x)) right(x) = i;
        else { splay(x); return false; }
        p(i) = x;
        splay(i); t = i;
        return true;
}

void SaBstSet::remove(index i, bst& t) {
        assert(1 <= i && i <= n() && 1 <= t && t <= n());
        index j;
        if (left(i) != 0 && right(i) != 0) {
                for (j = left(i); right(j) != 0; j = right(j)) {}
                swap(i,j);
        }
        // now, i has at most one child
        j = (left(i) != 0 ? left(i) : right(i));
        // j is now the index of the only child that could be non-null
        if (j != 0) p(j) = p(i);
        if (p(i) != 0) {
                     if (i ==  left(p(i)))  left(p(i)) = j;
                else if (i == right(p(i))) right(p(i)) = j;
                t = splay(p(i));
        } else t = j;
        p(i) = left(i) = right(i) = 0;
        return;
}

BstSet::BstPair SaBstSet::split(index i, bst t) {
        assert(1 <= i && i <= n() && 1 <= t && t <= n());
        splay(i);
        BstSet::BstPair pair(left(i),right(i));
        left(i) = right(i) = p(i) = 0;
        p(pair.t1) = p(pair.t2) = 0;
        return pair;
}

} // ends namespace