Skip to content

Instantly share code, notes, and snippets.

@buttercrab

buttercrab/rbtree.h

Created January 20, 2020 02:40
Show Gist options
  • Save buttercrab/2f34074cffc9b083282476aced4257a5 to your computer and use it in GitHub Desktop.
Save buttercrab/2f34074cffc9b083282476aced4257a5 to your computer and use it in GitHub Desktop.
Download ZIP
red black tree implementation in c++
Raw
rbtree.h
/**
* @class rbtree
*
* @details Red Black Tree Implementation
*
* @author Jaeyong Sung
*
* @date April 29, 2018
*/
#ifndef COLLECTIONS_RBTREE_H
#define COLLECTIONS_RBTREE_H
#include <vector>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <utility>
// node structure of rbtree
template<class _Tp>
struct __rbtree_node_ {
typedef _Tp value_type;
typedef __rbtree_node_* node_pointer;
value_type __value;
node_pointer __parent, __left, __right;
bool __is_black;
unsigned long __count;
};
// const iterator class of rbtree
template<class _Tp>
class __rbtree_const_iterator_ {
public:
typedef _Tp value_type;
typedef value_type* pointer;
typedef value_type& reference;
typedef __rbtree_node_<_Tp>* node_pointer;
typedef std::bidirectional_iterator_tag iterator_category;
typedef ptrdiff_t difference_type;
template<class, class> friend class rbtree;
template<class, class> friend class multi_rbtree;
private:
node_pointer __ptr;
inline bool __is_nil(const node_pointer &__p) { return __p->__right == __p; }
// returns the pointer
// not for use in the outer code
// only use for rbtree class
inline node_pointer __get_np() { return __ptr; }
// returns the pointer
// not for use in the outer code
// only use for rbtree class
inline node_pointer __get_np() const { return __ptr; }
public:
explicit __rbtree_const_iterator_(node_pointer __p) : __ptr(__p) {}
// returns the value of the pointer
reference operator*() const;
// returns the pointer of the value of the pointer
const pointer operator->() const;
// postfix operator ++
// returns the next const iterator of the rbtree when sorted
// or returns the const iterator pointing __nil if the iterator is pointing last node
// or returns the const iterator pointing the first node if the iterator is pointing __nil
__rbtree_const_iterator_ &operator++();
// prefix operator ++
// returns this const iterator but it would be pointing to next node when sorted
// or pointing __nil if the iterator is pointing last node
// or pointing the first node if the iterator is pointing __nil
const __rbtree_const_iterator_ operator++(int);
// postfix operator --
// returns the previous const iterator of the rbtree when sorted
// or returns the const iterator pointing __nil if the iterator is pointing first node
// or returns the const iterator pointing the last node if the iterator is pointing __nil
__rbtree_const_iterator_ &operator--();
// prefix operator --
// returns this const iterator but it would be pointing to previous node when sorted
// or pointing __nil if the iterator is pointing first node
// or pointing the last node if the iterator is pointing __nil
const __rbtree_const_iterator_ operator--(int);
// returns if two iterators are pointing the same node
bool operator==(const __rbtree_const_iterator_ &__x);
// returns if two iterators are not pointing the same node
bool operator!=(const __rbtree_const_iterator_ &__x);
};
template<class _Tp>
typename __rbtree_const_iterator_<_Tp>::reference
__rbtree_const_iterator_<_Tp>::operator*() const { return __ptr->__value; }
template<class _Tp>
typename __rbtree_const_iterator_<_Tp>::pointer const
__rbtree_const_iterator_<_Tp>::operator->() const { return &__ptr->__value; }
template<class _Tp>
__rbtree_const_iterator_<_Tp>&
__rbtree_const_iterator_<_Tp>::operator++() {
if (__is_nil(__ptr)) {
__ptr = __ptr->__parent;
while (!__is_nil(__ptr->__left))
__ptr = __ptr->__left;
} else if (!__is_nil(__ptr->__right)) {
__ptr = __ptr->__right;
while (!__is_nil(__ptr->__left))
__ptr = __ptr->__left;
} else if (!__is_nil(__ptr)) {
while (!__is_nil(__ptr) && __ptr->__parent->__left != __ptr)
__ptr = __ptr->__parent;
if (!__is_nil(__ptr)) __ptr = __ptr->__parent;
}
return *this;
}
template<class _Tp>
__rbtree_const_iterator_<_Tp> const
__rbtree_const_iterator_<_Tp>::operator++(int) {
__rbtree_const_iterator_ __t(*this);
++(*this);
return __t;
}
template<class _Tp>
__rbtree_const_iterator_<_Tp>&
__rbtree_const_iterator_<_Tp>::operator--() {
if (__is_nil(__ptr)) {
__ptr = __ptr->__parent;
while (!__is_nil(__ptr->__right))
__ptr = __ptr->__right;
} else if (!__is_nil(__ptr->__left)) {
__ptr = __ptr->__left;
while (!__is_nil(__ptr->__right))
__ptr = __ptr->__right;
} else if (!__is_nil(__ptr)) {
while (!__is_nil(__ptr) && __ptr->__parent->__right != __ptr)
__ptr = __ptr->__parent;
if (!__is_nil(__ptr)) __ptr = __ptr->__parent;
}
return *this;
}
template<class _Tp>
__rbtree_const_iterator_<_Tp> const
__rbtree_const_iterator_<_Tp>::operator--(int) {
__rbtree_const_iterator_ __t(*this);
--(*this);
return __t;
}
template<class _Tp>
bool __rbtree_const_iterator_<_Tp>::operator==(const __rbtree_const_iterator_ &__x) { return this->__ptr == __x.__ptr; }
template<class _Tp>
bool __rbtree_const_iterator_<_Tp>::operator!=(const __rbtree_const_iterator_ &__x) { return this->__ptr != __x.__ptr; }
// the red-black rbtree class
template<class _Tp, class _Comp = std::less<_Tp>>
class rbtree {
public:
typedef _Tp value_type;
typedef _Comp comp_type;
private:
typedef __rbtree_node_<value_type> __node;
typedef __node* __node_pointer;
public:
typedef __rbtree_const_iterator_<value_type> iterator;
typedef __rbtree_const_iterator_<value_type> const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> reverse_const_iterator;
private:
// the pointer to __root and __nil
// __nil's parent would be always __root
__node_pointer __root, __nil;
unsigned long __size;
// init method - is called by constructors in the beginning for initialization
inline void __init();
// finds the value __x
// returns the pointer of node of __x if rbtree has the value
// or returns the pointer to the leaf node that was last node when searching
template<class _Compare>
inline __node_pointer __find(const value_type &__x, _Compare compare);
// finds the value __x
// returns the pointer of node of __x if rbtree has the value
// or returns the pointer to the leaf node that was last node when searching
template<class _Compare>
inline __node_pointer __find(value_type &&__x, _Compare compare);
// finds the min node from node pointer
// returns itself when it is leaf node
// precondition : __p is not __nil
inline __node_pointer __find_min(__node_pointer __p);
// finds the min node from node pointer
// returns itself when it is leaf node
// precondition : __p is not __nil
inline __node_pointer __find_min(__node_pointer __p) const;
// finds the __xth element when the values are sorted (0 based)
// returns pointer of __xth node if __x is in range
// or returns pointer to __nil
inline __node_pointer __nth_element(unsigned long __x);
// finds the index of node pointer __p when the values are sorted (0 based)
// returns the index of node pointer __p node
inline unsigned long __index_of(__node_pointer __p);
// simple lower_bound function
// returns the pointer to the first not small value of __x
template<class _Compare>
inline __node_pointer __lower_bound(const value_type &__x, _Compare compare);
// simple lower_bound function
// returns the pointer to the first not small value of __x
template<class _Compare>
inline __node_pointer __lower_bound(value_type &&__x, _Compare compare);
// simple upper_bound function
// returns the pointer to the first big value of __x
template<class _Compare>
inline __node_pointer __upper_bound(const value_type &__x, _Compare compare);
// simple upper_bound function
// returns the pointer to the first big value of __x
template<class _Compare>
inline __node_pointer __upper_bound(value_type &&__x, _Compare compare);
// returns the sibling node of the pointer of __p if __p is not root
// or returns __nil;
// preconditions : __p is not __nil
inline __node_pointer __sibling_node(__node_pointer __p);
// rotates the rbtree left from __b's parent
// when the function is finished, __b would be parent of __b's parent
// changes the root when __b's parent was root
// preconditions : __b is not __root.
void __left_rotate(__node_pointer __b);
// rotates the rbtree right from __b's parent
// when the function is finished, __b would be parent of __b's parent
// changes the root when __b's parent was root
// preconditions : __b is not __root
void __right_rotate(__node_pointer __b);
// the balance function after insert
// __p is the pointer to node that was inserted
// preconditions : __p is red and __p's parent is red
void __insert_balance(__node_pointer __p);
// inserts the value __x
// do nothing when __x is already in the rbtree
// allocates a new node that the value is __x
template<class _Compare>
__node_pointer __insert(const value_type &__x, _Compare compare);
// inserts the value __x
// do nothing when __x is already in the rbtree
// allocates a new node that the value is __x
template<class _Compare>
__node_pointer __insert(value_type &&__x, _Compare compare);
// the balance function after erase
// __x is the pointer to node of a child that was erased
// preconditions : __x's black nodes count is 1 smaller than sibling of __x's
void __erase_balance(__node_pointer __x);
// erases the pointer __x
// deallocates the one-child node and changes the value
// do nothing when __x is __nil
void __erase(__node_pointer __x);
public:
// simple constructor
rbtree();
// constructor that inserts all the value in vector __v
rbtree(const std::vector<value_type> &__v);
// constructor that inserts all the value in initialize_list __il
rbtree(const std::initializer_list<value_type> &__il);
// constructor that inserts all the value from input iterator __first to intput iterator __last
template<class _InputIterator>
rbtree(_InputIterator __first, _InputIterator __last);
rbtree(const rbtree &other);
rbtree &operator=(const rbtree &other);
// deallocates all the node
void clear();
// inserts the value __x
iterator insert(const value_type &__x);
// inserts the value __x
iterator insert(value_type &&__x);
// inserts the value all from vector __v
void insert(const std::vector<value_type> &__v);
// inserts the value all from initializer list __il
void insert(const std::initializer_list<value_type> &__il);
// inserts the value all from input iterator __first to input iterator __last
template<class _InputIterator>
void insert(_InputIterator __first, _InputIterator __last);
// erases the node that iterator is pointing at
void erase(iterator __it);
// erases the value if the rbtree has the value
void erase(const value_type &__x);
// erases the value if the rbtree has the value
void erase(value_type &&__x);
// returns the size of the rbtree
unsigned long size();
// returns if rbtree is empty
bool empty();
// returns if rbtree is empty
bool empty() const;
// returns if the rbtree has the value __x
bool has(const value_type &__x);
// returns if the rbtree has the value __x
bool has(value_type &&__x);
// returns the count of the value __x in the rbtree
unsigned long count(const value_type &__x);
// returns the count of the value __x in the rbtree
unsigned long count(value_type &&__x);
// returns the any iterator of value __x if the value is in the rbtree
// or returns end iterator
iterator find(const value_type &__x);
// returns the any iterator of value __x if the value is in the rbtree
// or returns end iterator
iterator find(value_type &&__x);
// returns the pair of find function and index_of function (0 based)
// index_of gets iterator, but this function gets the value __x
std::pair<iterator, unsigned long> find_with(const value_type &__x);
// returns the pair of find function and index_of function (0 based)
// index_of gets iterator, but this function gets the value __x
std::pair<iterator, unsigned long> find_with(value_type &&__x);
// returns the iterator pointing the nth element of the values when sorted if __x is in range (0 based)
// of returns the end iterator
iterator nth_element(const unsigned long &__x);
// returns the iterator pointing the nth element of the values when sorted if __x is in range (0 based)
// of returns the end iterator
iterator nth_element(unsigned long &&__x);
// returns the index of iterator __x in the rbtree when sorted (0 based)
// or returns the size of the rbtree when the iterator is pointing __nil
unsigned long index_of(const iterator &__x);
// returns the iterator pointing to the first not small value of __x
iterator lower_bound(const value_type &__x);
// returns the iterator pointing to the first not small value of __x
iterator lower_bound(value_type &&__x);
// returns the iterator pointing to the first bigger value of __x
iterator upper_bound(const value_type &__x);
// returns the iterator pointing to the first bigger value of __x
iterator upper_bound(value_type &&__x);
// returns the pair of lower_bound and upper_bound
std::pair<iterator, iterator> equal_range(const value_type &__x);
// returns the pair of lower_bound and upper_bound
std::pair<iterator, iterator> equal_range(value_type &&__x);
void merge(const rbtree &t);
// returns the begin iterator pointing min value
iterator begin();
// returns the const begin iterator pointing min value
const_iterator begin() const;
// returns the reverse iterator of end
// the value of the rbegin would be max value of the rbtree
reverse_iterator rbegin();
// returns the reverse iterator of end
// the value of the rbegin would be max value of the rbtree
reverse_const_iterator rbegin() const;
// returns the end iterator pointing __nil
iterator end();
// returns the end iterator pointing __nil
const_iterator end() const;
// returns the reverse iterator of begin
// the value of the rend would be __nil
reverse_iterator rend();
// returns the reverse iterator of begin
// the value of the rend would be __nil
reverse_const_iterator rend() const;
// returns the begin const iterator pointing min value
const_iterator cbegin() const;
// returns the reverse const iterator of end
// the value of the crbegin would be max value of the rbtree
reverse_const_iterator crbegin() const;
// returns the end const iterator pointing __nil
const_iterator cend() const;
// returns the reverse const iterator of begin
// the value of the crend would be __nil
reverse_const_iterator crend() const;
// destructor of the rbtree class
// deallocates all the nodes
~rbtree();
};
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::__init() {
__root = new __node;
__nil = new __node;
__root->__parent = __nil;
__root->__left = __nil;
__root->__right = __nil;
__root->__is_black = true;
__root->__count = 0;
__nil->__parent = __root;
__nil->__left = __nil;
__nil->__right = __nil;
__nil->__is_black = true;
__nil->__count = 0;
__size = 0;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__find(const value_type &__x, _Compare compare) {
__node_pointer __p = __root, __q = __p;
while (__p != __nil) {
__q = __p;
if (__x == __p->__value) return __p;
if (compare(__x, __p->__value)) __p = __p->__left;
else __p = __p->__right;
}
return __q;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__find(value_type &&__x, _Compare compare) {
__node_pointer __p = __root, __q = __p;
while (__p != __nil) {
__q = __p;
if (std::move(__x) == __p->__value) return __p;
if (compare(std::move(__x), __p->__value)) __p = __p->__left;
else __p = __p->__right;
}
return __q;
}
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__find_min(rbtree::__node_pointer __p) {
while (__p->__left != __nil)
__p = __p->__left;
return __p;
}
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__find_min(rbtree::__node_pointer __p) const {
while (__p->__left != __nil)
__p = __p->__left;
return __p;
}
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__nth_element(unsigned long __x) {
__node_pointer __p = __root;
while (__p != __nil) {
if (__x == __p->__left->__count) return __p;
if (__x < __p->__left->__count) __p = __p->__left;
else {
__x -= __p->__left->__count + 1;
__p = __p->__right;
}
}
return __nil;
}
template<class _Tp, class _Comp>
unsigned long rbtree<_Tp, _Comp>::__index_of(rbtree::__node_pointer __p) {
unsigned long ans = __p->__left->__count;
while (__p != __root) {
if (__p == __p->__parent->__right) ans += __p->__parent->__left->__count + 1;
__p = __p->__parent;
}
return ans;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__lower_bound(const value_type &__x, _Compare compare) {
__node_pointer __p = __root, __ans = __nil;
while (__p->__left != __nil && __p->__right != __nil) {
if (__x == __p->__value) {
while (__p->__left->__value == __x) __p = __p->__left;
return __p;
}
if (compare(__x, __p->__value))
__p = __p->__left;
else {
__p = __p->__right;
if (__ans == __nil || compare(__p->__value, __ans->__value)) __ans = __p;
}
}
return __ans;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__lower_bound(value_type &&__x, _Compare compare) {
__node_pointer __p = __root, __ans = __nil;
while (__p->__left != __nil && __p->__right != __nil) {
if (std::move(__x) == __p->__value) {
while (__p->__left->__value == std::move(__x)) __p = __p->__left;
return __p;
}
if (compare(std::move(__x), __p->__value))
__p = __p->__left;
else {
__p = __p->__right;
if (__ans == __nil || compare(__p->__value, __ans->__value)) __ans = __p;
}
}
return __ans;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__upper_bound(const value_type &__x, _Compare compare) {
__node_pointer __p = __root, __ans = __nil;
while (__p->__left != __nil && __p->__right != __nil) {
if (__x == __p->__value) {
while (__p->__right->__value == __x) __p = __p->__right;
return __p;
}
if (compare(__x, __p->__value))
__p = __p->__left;
else {
__p = __p->__right;
if (__ans == __nil || compare(__p->__value, __ans->__value)) __ans = __p;
}
}
return __ans;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__upper_bound(value_type &&__x, _Compare compare) {
__node_pointer __p = __root, __ans = __nil;
while (__p->__left != __nil && __p->__right != __nil) {
if (std::move(__x) == __p->__value) {
while (__p->__right->__value == std::move(__x)) __p = __p->__right;
return __p;
}
if (compare(std::move(__x), __p->__value))
__p = __p->__left;
else {
__p = __p->__right;
if (__ans == __nil || compare(__p->__value, __ans->__value)) __ans = __p;
}
}
return __ans;
}
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__sibling_node(rbtree::__node_pointer __p) {
if (__p == __root) return __nil;
if (__p == __p->__parent->__left) return __p->__parent->__right;
return __p->__parent->__left;
}
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::__left_rotate(rbtree::__node_pointer __b) {
__node_pointer __a = __b->__parent, __p = __b->__left, __q = __a->__parent;
if (__a == __root)
__root = __b;
else {
if (__a == __q->__left) __q->__left = __b;
else __q->__right = __b;
}
if (__b == __root) __b->__parent = __nil;
else __b->__parent = __q;
__b->__left = __a;
__a->__parent = __b;
__a->__right = __p;
if (__p != __nil) __p->__parent = __a;
__b->__count = __a->__count;
__a->__count = __a->__left->__count + __a->__right->__count + 1;
}
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::__right_rotate(rbtree::__node_pointer __b) {
__node_pointer __a = __b->__parent, __p = __b->__right, __q = __a->__parent;
if (__a == __root)
__root = __b;
else {
if (__a == __q->__left) __q->__left = __b;
else __q->__right = __b;
}
if (__b == __root) __b->__parent = __nil;
else __b->__parent = __q;
__b->__right = __a;
__a->__parent = __b;
__a->__left = __p;
if (__p != __nil) __p->__parent = __a;
__a->__count = __b->__count;
__b->__count = __b->__left->__count + __b->__right->__count + 1;
}
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::__insert_balance(rbtree::__node_pointer __p) {
if (__p->__parent == __root) {
__root->__is_black = true;
return;
}
__node_pointer __s = __sibling_node(__p->__parent);
__node_pointer __a = __p->__parent->__parent;
if (!__s->__is_black) {
__s->__is_black = true;
__p->__parent->__is_black = true;
if (__a != __root) {
__a->__is_black = false;
if (!__a->__parent->__is_black)
__insert_balance(__a);
}
} else {
if (__p->__parent == __a->__left) {
if (__p == __p->__parent->__right) {
__left_rotate(__p);
__right_rotate(__p);
__p->__is_black = true;
} else {
__right_rotate(__p->__parent);
__p->__parent->__is_black = true;
}
__a->__is_black = false;
} else {
if (__p == __p->__parent->__left) {
__right_rotate(__p);
__left_rotate(__p);
__p->__is_black = true;
} else {
__left_rotate(__p->__parent);
__p->__parent->__is_black = true;
}
__a->__is_black = false;
}
}
}
template<class _Tp, class _Comp>
template<class _Compare>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__insert(const value_type &__x, _Compare compare) {
__size++;
if (__size == 1) {
__root->__value = __x;
__root->__count++;
__nil->__parent = __root;
return __root;
}
__node_pointer __p = __root, __q = __p;
while (__p != __nil) {
__q = __p;
if (__p->__value == __x) return __p;
if (compare(__x, __p->__value)) __p = __p->__left;
else __p = __p->__right;
}
__p = __q;
__node_pointer __n = new __node;
__n->__parent = __p;
if (compare(__x, __p->__value)) __p->__left = __n;
else __p->__right = __n;
__n->__is_black = false;
__n->__left = __nil;
__n->__right = __nil;
__n->__value = __x;
__n->__count = 0;
for (__node_pointer __i = __n; __i != __nil; __i = __i->__parent) __i->__count++;
if (!__p->__is_black) __insert_balance(__n);
__nil->__parent = __root;
return __n;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename rbtree<_Tp, _Comp>::__node_pointer
rbtree<_Tp, _Comp>::__insert(value_type &&__x, _Compare compare) {
__size++;
if (__size == 1) {
__root->__value = std::move(__x);
__root->__count++;
__nil->__parent = __root;
return __root;
}
__node_pointer __p = __root, __q = __p;
while (__p != __nil) {
__q = __p;
if (__p->__value == std::move(__x)) return __p;
if (compare(std::move(__x), __p->__value)) __p = __p->__left;
else __p = __p->__right;
}
__p = __q;
__node_pointer __n = new __node;
__n->__parent = __p;
if (compare(std::move(__x), __p->__value)) __p->__left = __n;
else __p->__right = __n;
__n->__is_black = false;
__n->__left = __nil;
__n->__right = __nil;
__n->__value = std::move(__x);
__n->__count = 0;
for (__node_pointer __i = __n; __i != __nil; __i = __i->__parent) __i->__count++;
if (!__p->__is_black) __insert_balance(__n);
__nil->__parent = __root;
return __n;
}
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::__erase_balance(rbtree::__node_pointer __x) {
if (__x == __root) {
__x->__is_black = true;
return;
}
__node_pointer __p = __x->__parent;
if (__x == __p->__left) {
__node_pointer __s = __p->__right, __l = __s->__left, __r = __s->__right;
if (!__r->__is_black) {
__left_rotate(__s);
std::swap(__p->__is_black, __s->__is_black);
__r->__is_black = true;
} else if (!__l->__is_black) {
__right_rotate(__l);
__left_rotate(__l);
__l->__is_black = __p->__is_black;
__p->__is_black = true;
} else if (!__s->__is_black) {
__left_rotate(__s);
__p->__is_black = false;
__s->__is_black = true;
__erase_balance(__x);
} else if (!__p->__is_black) {
__p->__is_black = true;
__s->__is_black = false;
} else {
__s->__is_black = false;
__erase_balance(__p);
}
} else {
__node_pointer __s = __p->__left, __l = __s->__left, __r = __s->__right;
if (!__l->__is_black) {
__right_rotate(__s);
std::swap(__p->__is_black, __s->__is_black);
__l->__is_black = true;
} else if (!__r->__is_black) {
__left_rotate(__r);
__right_rotate(__r);
__r->__is_black = __p->__is_black;
__p->__is_black = true;
} else if (!__s->__is_black) {
__right_rotate(__s);
__p->__is_black = false;
__s->__is_black = true;
__erase_balance(__x);
} else if (!__p->__is_black) {
__p->__is_black = true;
__s->__is_black = false;
} else {
__s->__is_black = false;
__erase_balance(__p);
}
}
}
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::__erase(rbtree::__node_pointer __x) {
if (__x == __nil) return;
if (__size != 1) {
__node_pointer __a = __find_min(__x->__right);
if (__a == __nil) __a = __x;
else __x->__value = __a->__value;
if (__a->__left != __nil || __a->__right != __nil) {
__node_pointer __b;
if (__a->__right != __nil) __b = __a->__right;
else __b = __a->__left;
if (__a == __root) {
__root = __b;
__b->__is_black = true;
__b->__parent = __nil;
} else {
if (__a->__parent->__left == __a) __a->__parent->__left = __b;
else __a->__parent->__right = __b;
__b->__parent = __a->__parent;
for (__node_pointer __i = __b->__parent; __i != __nil; __i = __i->__parent) __i->__count--;
if (!__a->__is_black || !__b->__is_black) __b->__is_black = true;
else __erase_balance(__b);
}
} else {
if (__a->__is_black) __erase_balance(__a);
if (__a->__parent->__left == __a) __a->__parent->__left = __nil;
else __a->__parent->__right = __nil;
for (__node_pointer __i = __a->__parent; __i != __nil; __i = __i->__parent) __i->__count--;
}
delete __a;
}
__size--;
__nil->__parent = __root;
}
template<class _Tp, class _Comp>
rbtree<_Tp, _Comp>::rbtree() { __init(); }
template<class _Tp, class _Comp>
rbtree<_Tp, _Comp>::rbtree(const std::vector<value_type> &__v) {
__init();
insert(__v);
}
template<class _Tp, class _Comp>
rbtree<_Tp, _Comp>::rbtree(const std::initializer_list<value_type> &__il) {
__init();
insert(__il);
}
template<class _Tp, class _Comp>
template<class _InputIterator>
rbtree<_Tp, _Comp>::rbtree(_InputIterator __first, _InputIterator __last) {
__init();
insert(__first, __last);
}
template<class _Tp, class _Comp>
rbtree<_Tp, _Comp>::rbtree(const rbtree &other) {
this->__init();
for (auto &i: other) this->insert(i);
}
template<class _Tp, class _Comp>
rbtree<_Tp, _Comp>&
rbtree<_Tp, _Comp>::operator=(const rbtree &other) {
this->clear();
for (auto &i: other) this->insert(i);
return *this;
}
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::clear() { while (!empty()) __erase(__root); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::insert(const value_type &__x) { return iterator(__insert(__x, comp_type())); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::insert(value_type &&__x) { return iterator(__insert(std::move(__x), comp_type())); }
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::insert(const std::vector<value_type> &__v) { insert(__v.begin(), __v.end()); }
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::insert(const std::initializer_list<value_type> &__il) { insert(__il.begin(), __il.end()); }
template<class _Tp, class _Comp>
template<class _InputIterator>
void rbtree<_Tp, _Comp>::insert(_InputIterator __first, _InputIterator __last) {
for (; __first != __last; ++__first)
insert(*__first);
}
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::erase(rbtree::iterator __it) { __erase(__it.__get_np()); }
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::erase(const value_type &__x) {
__node_pointer __p = __find(__x, comp_type());
if (__p->__value != __x) return;
__erase(__p);
}
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::erase(value_type &&__x) {
__node_pointer __p = __find(std::move(__x), comp_type());
if (__p->__value != std::move(__x)) return;
__erase(__p);
}
template<class _Tp, class _Comp>
unsigned long rbtree<_Tp, _Comp>::size() { return __size; }
template<class _Tp, class _Comp>
bool rbtree<_Tp, _Comp>::empty() { return !__size; }
template<class _Tp, class _Comp>
bool rbtree<_Tp, _Comp>::empty() const { return !__size; }
template<class _Tp, class _Comp>
bool rbtree<_Tp, _Comp>::has(const value_type &__x) {
__node_pointer __p = __find(__x, comp_type());
return __p->__value == __x;
}
template<class _Tp, class _Comp>
bool rbtree<_Tp, _Comp>::has(value_type &&__x) {
__node_pointer __p = __find(std::move(__x), comp_type());
return __p->__value == std::move(__x);
}
template<class _Tp, class _Comp>
unsigned long rbtree<_Tp, _Comp>::count(const value_type &__x) { return index_of(upper_bound(__x)) - index_of(lower_bound(__x)); }
template<class _Tp, class _Comp>
unsigned long rbtree<_Tp, _Comp>::count(value_type &&__x) { return index_of(upper_bound(std::move(__x))) - index_of(lower_bound(std::move(__x))); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::find(const value_type &__x) {
__node_pointer __p = __find(__x, comp_type());
if (__p->__value == __x) return iterator(__p);
return end();
}
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::find(value_type &&__x) {
__node_pointer __p = __find(std::move(__x), comp_type());
if (__p->__value == std::move(__x)) return iterator(__p);
return end();
}
template<class _Tp, class _Comp>
std::pair<typename rbtree<_Tp, _Comp>::iterator, unsigned long>
rbtree<_Tp, _Comp>::find_with(const value_type &__x) {
__node_pointer __ret = __find(__x, comp_type());
if (__ret->__value == __x) return std::make_pair(iterator(__ret), __index_of(__ret));
return std::make_pair(end(), size());
}
template<class _Tp, class _Comp>
std::pair<typename rbtree<_Tp, _Comp>::iterator, unsigned long>
rbtree<_Tp, _Comp>::find_with(value_type &&__x) {
__node_pointer __ret = __find(std::move(__x), comp_type());
if (__ret->__value == std::move(__x)) return std::make_pair(iterator(__ret), __index_of(__ret));
return std::make_pair(end(), size());
}
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::nth_element(const unsigned long &__x) { return iterator(__nth_element(__x)); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::nth_element(unsigned long &&__x) { return iterator(__nth_element(__x)); }
template<class _Tp, class _Comp>
unsigned long rbtree<_Tp, _Comp>::index_of(const rbtree::iterator &__x) {
if (__x.__get_np() == __nil) return size();
return __index_of(__x.__get_np());
}
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::lower_bound(const value_type &__x) { return iterator(__lower_bound(__x, comp_type())); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::lower_bound(value_type &&__x) { return iterator(__lower_bound(std::move(__x), comp_type())); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::upper_bound(const value_type &__x) {
iterator it(__upper_bound(__x, comp_type()));
if (*it == __x) ++it;
return it;
}
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::upper_bound(value_type &&__x) {
iterator it(__upper_bound(std::move(__x), comp_type()));
if (*it == std::move(__x)) ++it;
return it;
}
template<class _Tp, class _Comp>
std::pair<typename rbtree<_Tp, _Comp>::iterator, typename rbtree<_Tp, _Comp>::iterator>
rbtree<_Tp, _Comp>::equal_range(const value_type &__x) { return std::make_pair(lower_bound(__x), upper_bound(__x)); }
template<class _Tp, class _Comp>
std::pair<typename rbtree<_Tp, _Comp>::iterator, typename rbtree<_Tp, _Comp>::iterator>
rbtree<_Tp, _Comp>::equal_range(value_type &&__x) { return std::make_pair(lower_bound(std::move(__x)), upper_bound(std::move(__x))); }
template<class _Tp, class _Comp>
void rbtree<_Tp, _Comp>::merge(const rbtree &t) { for (auto &i: t) insert(i); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::begin() {
if (empty()) return iterator(__nil);
return iterator(__find_min(__root));
}
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::const_iterator
rbtree<_Tp, _Comp>::begin() const {
if (empty()) return const_iterator(__nil);
return const_iterator(__find_min(__root));
}
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::reverse_iterator
rbtree<_Tp, _Comp>::rbegin() { return reverse_iterator(end()); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::reverse_const_iterator
rbtree<_Tp, _Comp>::rbegin() const { return reverse_const_iterator(cend()); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::iterator
rbtree<_Tp, _Comp>::end() { return iterator(__nil); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::const_iterator
rbtree<_Tp, _Comp>::end() const { return const_iterator(__nil); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::reverse_iterator
rbtree<_Tp, _Comp>::rend() { return reverse_iterator(begin()); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::reverse_const_iterator
rbtree<_Tp, _Comp>::rend() const { return reverse_const_iterator(cbegin()); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::const_iterator
rbtree<_Tp, _Comp>::cbegin() const {
if (empty()) return const_iterator(__nil);
return const_iterator(__find_min(__root));
}
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::reverse_const_iterator
rbtree<_Tp, _Comp>::crbegin() const { return reverse_const_iterator(cend()); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::const_iterator
rbtree<_Tp, _Comp>::cend() const { return const_iterator(__nil); }
template<class _Tp, class _Comp>
typename rbtree<_Tp, _Comp>::reverse_const_iterator
rbtree<_Tp, _Comp>::crend() const { return reverse_const_iterator(cbegin()); }
template<class _Tp, class _Comp>
rbtree<_Tp, _Comp>::~rbtree() { clear(); }
// the red-black multi rbtree class
template<class _Tp, class _Comp = std::less<_Tp>>
class multi_rbtree {
public:
typedef _Tp value_type;
typedef _Comp comp_type;
private:
typedef __rbtree_node_<value_type> __node;
typedef __node* __node_pointer;
public:
typedef __rbtree_const_iterator_<value_type> iterator;
typedef __rbtree_const_iterator_<value_type> const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> reverse_const_iterator;
private:
// the pointer to __root and __nil
// __nil's parent would be always __root
__node_pointer __root, __nil;
unsigned long __size;
// init method - is called by constructors in the beginning for initialization
inline void __init();
// finds the value __x
// returns the pointer of node of __x if rbtree has the value
// or returns the pointer to the leaf node that was last node when searching
template<class _Compare>
inline __node_pointer __find(const value_type &__x, _Compare compare);
// finds the value __x
// returns the pointer of node of __x if rbtree has the value
// or returns the pointer to the leaf node that was last node when searching
template<class _Compare>
inline __node_pointer __find(value_type &&__x, _Compare compare);
// finds the min node from node pointer
// returns itself when it is leaf node
// precondition : __p is not __nil
inline __node_pointer __find_min(__node_pointer __p);
// finds the min node from node pointer
// returns itself when it is leaf node
// precondition : __p is not __nil
inline __node_pointer __find_min(__node_pointer __p) const;
// finds the __xth element when the values are sorted (0 based)
// returns pointer of __xth node if __x is in range
// or returns pointer to __nil
inline __node_pointer __nth_element(unsigned long __x);
// finds the index of node pointer __p when the values are sorted (0 based)
// returns the index of node pointer __p node
inline unsigned long __index_of(__node_pointer __p);
// simple lower_bound function
// returns the pointer to the first not small value of __x
template<class _Compare>
inline __node_pointer __lower_bound(const value_type &__x, _Compare compare);
// simple lower_bound function
// returns the pointer to the first not small value of __x
template<class _Compare>
inline __node_pointer __lower_bound(value_type &&__x, _Compare compare);
// simple upper_bound function
// returns the pointer to the first big value of __x
template<class _Compare>
inline __node_pointer __upper_bound(const value_type &__x, _Compare compare);
// simple upper_bound function
// returns the pointer to the first big value of __x
template<class _Compare>
inline __node_pointer __upper_bound(value_type &&__x, _Compare compare);
// returns the sibling node of the pointer of __p if __p is not root
// or returns __nil;
// preconditions : __p is not __nil
inline __node_pointer __sibling_node(__node_pointer __p);
// rotates the rbtree left from __b's parent
// when the function is finished, __b would be parent of __b's parent
// changes the root when __b's parent was root
// preconditions : __b is not __root.
void __left_rotate(__node_pointer __b);
// rotates the rbtree right from __b's parent
// when the function is finished, __b would be parent of __b's parent
// changes the root when __b's parent was root
// preconditions : __b is not __root
void __right_rotate(__node_pointer __b);
// the balance function after insert
// __p is the pointer to node that was inserted
// preconditions : __p is red and __p's parent is red
void __insert_balance(__node_pointer __p);
// inserts the value __x
// do nothing when __x is already in the rbtree
// allocates a new node that the value is __x
template<class _Compare>
__node_pointer __insert(const value_type &__x, _Compare compare);
// inserts the value __x
// do nothing when __x is already in the rbtree
// allocates a new node that the value is __x
template<class _Compare>
__node_pointer __insert(value_type &&__x, _Compare compare);
// the balance function after erase
// __x is the pointer to node of a child that was erased
// preconditions : __x's black nodes count is 1 smaller than sibling of __x's
void __erase_balance(__node_pointer __x);
// erases the pointer __x
// deallocates the one-child node and changes the value
// do nothing when __x is __nil
void __erase(__node_pointer __x);
public:
// simple constructor
multi_rbtree();
// constructor that inserts all the value in vector __v
multi_rbtree(const std::vector<value_type> &__v);
// constructor that inserts all the value in initialize_list __il
multi_rbtree(const std::initializer_list<value_type> &__il);
// constructor that inserts all the value from input iterator __first to intput iterator __last
template<class _InputIterator>
multi_rbtree(_InputIterator __first, _InputIterator __last);
multi_rbtree(const multi_rbtree &other);
multi_rbtree &operator=(const multi_rbtree &other);
// deallocates all the node
void clear();
// inserts the value __x
iterator insert(const value_type &__x);
// inserts the value __x
iterator insert(value_type &&__x);
// inserts the value all from vector __v
void insert(const std::vector<value_type> &__v);
// inserts the value all from initializer list __il
void insert(const std::initializer_list<value_type> &__il);
// inserts the value all from input iterator __first to input iterator __last
template<class _InputIterator>
void insert(_InputIterator __first, _InputIterator __last);
// erases the node that iterator is pointing at
void erase(iterator __it);
// erases the value if the rbtree has the value
void erase(const value_type &__x);
// erases the value if the rbtree has the value
void erase(value_type &&__x);
// returns the size of the rbtree
unsigned long size();
// returns if rbtree is empty
bool empty();
// returns if rbtree is empty
bool empty() const;
// returns if the rbtree has the value __x
bool has(const value_type &__x);
// returns if the rbtree has the value __x
bool has(value_type &&__x);
// returns the count of the value __x in the rbtree
unsigned long count(const value_type &__x);
// returns the count of the value __x in the rbtree
unsigned long count(value_type &&__x);
// returns the any iterator of value __x if the value is in the rbtree
// or returns end iterator
iterator find(const value_type &__x);
// returns the any iterator of value __x if the value is in the rbtree
// or returns end iterator
iterator find(value_type &&__x);
// returns the pair of find function and index_of function (0 based)
// index_of gets iterator, but this function gets the value __x
std::pair<iterator, unsigned long> find_with(const value_type &__x);
// returns the pair of find function and index_of function (0 based)
// index_of gets iterator, but this function gets the value __x
std::pair<iterator, unsigned long> find_with(value_type &&__x);
// returns the iterator pointing the nth element of the values when sorted if __x is in range (0 based)
// of returns the end iterator
iterator nth_element(const unsigned long &__x);
// returns the iterator pointing the nth element of the values when sorted if __x is in range (0 based)
// of returns the end iterator
iterator nth_element(unsigned long &&__x);
// returns the index of iterator __x in the rbtree when sorted (0 based)
// or returns the size of the rbtree when the iterator is pointing __nil
unsigned long index_of(const iterator &__x);
// returns the iterator pointing to the first not small value of __x
iterator lower_bound(const value_type &__x);
// returns the iterator pointing to the first not small value of __x
iterator lower_bound(value_type &&__x);
// returns the iterator pointing to the first bigger value of __x
iterator upper_bound(const value_type &__x);
// returns the iterator pointing to the first bigger value of __x
iterator upper_bound(value_type &&__x);
// returns the pair of lower_bound and upper_bound
std::pair<iterator, iterator> equal_range(const value_type &__x);
// returns the pair of lower_bound and upper_bound
std::pair<iterator, iterator> equal_range(value_type &&__x);
void merge(const multi_rbtree &t);
// returns the begin iterator pointing min value
iterator begin();
// returns the const begin iterator pointing min value
const_iterator begin() const;
// returns the reverse iterator of end
// the value of the rbegin would be max value of the rbtree
reverse_iterator rbegin();
// returns the reverse iterator of end
// the value of the rbegin would be max value of the rbtree
reverse_const_iterator rbegin() const;
// returns the end iterator pointing __nil
iterator end();
// returns the end iterator pointing __nil
const_iterator end() const;
// returns the reverse iterator of begin
// the value of the rend would be __nil
reverse_iterator rend();
// returns the reverse iterator of begin
// the value of the rend would be __nil
reverse_const_iterator rend() const;
// returns the begin const iterator pointing min value
const_iterator cbegin() const;
// returns the reverse const iterator of end
// the value of the crbegin would be max value of the rbtree
reverse_const_iterator crbegin() const;
// returns the end const iterator pointing __nil
const_iterator cend() const;
// returns the reverse const iterator of begin
// the value of the crend would be __nil
reverse_const_iterator crend() const;
// destructor of the rbtree class
// deallocates all the nodes
~multi_rbtree();
};
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::__init() {
__root = new __node;
__nil = new __node;
__root->__parent = __nil;
__root->__left = __nil;
__root->__right = __nil;
__root->__is_black = true;
__root->__count = 0;
__nil->__parent = __root;
__nil->__left = __nil;
__nil->__right = __nil;
__nil->__is_black = true;
__nil->__count = 0;
__size = 0;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__find(const value_type &__x, _Compare compare) {
__node_pointer __p = __root, __q = __p;
while (__p != __nil) {
__q = __p;
if (__x == __p->__value) return __p;
if (compare(__x, __p->__value)) __p = __p->__left;
else __p = __p->__right;
}
return __q;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__find(value_type &&__x, _Compare compare) {
__node_pointer __p = __root, __q = __p;
while (__p != __nil) {
__q = __p;
if (std::move(__x) == __p->__value) return __p;
if (compare(std::move(__x), __p->__value)) __p = __p->__left;
else __p = __p->__right;
}
return __q;
}
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__find_min(multi_rbtree::__node_pointer __p) {
while (__p->__left != __nil)
__p = __p->__left;
return __p;
}
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__find_min(multi_rbtree::__node_pointer __p) const {
while (__p->__left != __nil)
__p = __p->__left;
return __p;
}
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__nth_element(unsigned long __x) {
__node_pointer __p = __root;
while (__p != __nil) {
if (__x == __p->__left->__count) return __p;
if (__x < __p->__left->__count) __p = __p->__left;
else {
__x -= __p->__left->__count + 1;
__p = __p->__right;
}
}
return __nil;
}
template<class _Tp, class _Comp>
unsigned long multi_rbtree<_Tp, _Comp>::__index_of(multi_rbtree::__node_pointer __p) {
unsigned long ans = __p->__left->__count;
while (__p != __root) {
if (__p == __p->__parent->__right) ans += __p->__parent->__left->__count + 1;
__p = __p->__parent;
}
return ans;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__lower_bound(const value_type &__x, _Compare compare) {
__node_pointer __p = __root, __ans = __nil;
while (__p->__left != __nil && __p->__right != __nil) {
if (__x == __p->__value) {
while (__p->__left->__value == __x) __p = __p->__left;
return __p;
}
if (compare(__x, __p->__value))
__p = __p->__left;
else {
__p = __p->__right;
if (compare(__p->__value, __ans->__value) || __ans == __nil) __ans = __p;
}
}
return __ans;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__lower_bound(value_type &&__x, _Compare compare) {
__node_pointer __p = __root, __ans = __nil;
while (__p->__left != __nil && __p->__right != __nil) {
if (std::move(__x) == __p->__value) {
while (__p->__left->__value == std::move(__x)) __p = __p->__left;
return __p;
}
if (compare(std::move(__x), __p->__value))
__p = __p->__left;
else {
__p = __p->__right;
if (compare(__p->__value, __ans->__value) || __ans == __nil) __ans = __p;
}
}
return __ans;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__upper_bound(const value_type &__x, _Compare compare) {
__node_pointer __p = __root, __ans = __nil;
while (__p->__left != __nil && __p->__right != __nil) {
if (__x == __p->__value) {
while (__p->__right->__value == __x) __p = __p->__right;
return __p;
}
if (compare(__x, __p->__value))
__p = __p->__left;
else {
__p = __p->__right;
if (compare(__p->__value, __ans->__value) || __ans == __nil) __ans = __p;
}
}
return __ans;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__upper_bound(value_type &&__x, _Compare compare) {
__node_pointer __p = __root, __ans = __nil;
while (__p->__left != __nil && __p->__right != __nil) {
if (std::move(__x) == __p->__value) {
while (__p->__right->__value == std::move(__x)) __p = __p->__right;
return __p;
}
if (compare(std::move(__x), __p->__value))
__p = __p->__left;
else {
__p = __p->__right;
if (compare(__p->__value, __ans->__value) || __ans == __nil) __ans = __p;
}
}
return __ans;
}
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__sibling_node(multi_rbtree::__node_pointer __p) {
if (__p == __root) return __nil;
if (__p == __p->__parent->__left) return __p->__parent->__right;
return __p->__parent->__left;
}
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::__left_rotate(multi_rbtree::__node_pointer __b) {
__node_pointer __a = __b->__parent, __p = __b->__left, __q = __a->__parent;
if (__a == __root)
__root = __b;
else {
if (__a == __q->__left) __q->__left = __b;
else __q->__right = __b;
}
if (__b == __root) __b->__parent = __nil;
else __b->__parent = __q;
__b->__left = __a;
__a->__parent = __b;
__a->__right = __p;
if (__p != __nil) __p->__parent = __a;
__b->__count = __a->__count;
__a->__count = __a->__left->__count + __a->__right->__count + 1;
}
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::__right_rotate(multi_rbtree::__node_pointer __b) {
__node_pointer __a = __b->__parent, __p = __b->__right, __q = __a->__parent;
if (__a == __root)
__root = __b;
else {
if (__a == __q->__left) __q->__left = __b;
else __q->__right = __b;
}
if (__b == __root) __b->__parent = __nil;
else __b->__parent = __q;
__b->__right = __a;
__a->__parent = __b;
__a->__left = __p;
if (__p != __nil) __p->__parent = __a;
__a->__count = __b->__count;
__b->__count = __b->__left->__count + __b->__right->__count + 1;
}
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::__insert_balance(multi_rbtree::__node_pointer __p) {
if (__p->__parent == __root) {
__root->__is_black = true;
return;
}
__node_pointer __s = __sibling_node(__p->__parent);
__node_pointer __a = __p->__parent->__parent;
if (!__s->__is_black) {
__s->__is_black = true;
__p->__parent->__is_black = true;
if (__a != __root) {
__a->__is_black = false;
if (!__a->__parent->__is_black)
__insert_balance(__a);
}
} else {
if (__p->__parent == __a->__left) {
if (__p == __p->__parent->__right) {
__left_rotate(__p);
__right_rotate(__p);
__p->__is_black = true;
} else {
__right_rotate(__p->__parent);
__p->__parent->__is_black = true;
}
__a->__is_black = false;
} else {
if (__p == __p->__parent->__left) {
__right_rotate(__p);
__left_rotate(__p);
__p->__is_black = true;
} else {
__left_rotate(__p->__parent);
__p->__parent->__is_black = true;
}
__a->__is_black = false;
}
}
}
template<class _Tp, class _Comp>
template<class _Compare>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__insert(const value_type &__x, _Compare compare) {
__size++;
if (__size == 1) {
__root->__value = __x;
__root->__count++;
__nil->__parent = __root;
return __root;
}
__node_pointer __p = __root, __q = __p;
while (__p != __nil) {
__q = __p;
if (compare(__x, __p->__value)) __p = __p->__left;
else __p = __p->__right;
}
__p = __q;
__node_pointer __n = new __node;
__n->__parent = __p;
if (compare(__x, __p->__value)) __p->__left = __n;
else __p->__right = __n;
__n->__is_black = false;
__n->__left = __nil;
__n->__right = __nil;
__n->__value = __x;
__n->__count = 0;
for (__node_pointer __i = __n; __i != __nil; __i = __i->__parent) __i->__count++;
if (!__p->__is_black) __insert_balance(__n);
__nil->__parent = __root;
return __n;
}
template<class _Tp, class _Comp>
template<class _Compare>
typename multi_rbtree<_Tp, _Comp>::__node_pointer
multi_rbtree<_Tp, _Comp>::__insert(value_type &&__x, _Compare compare) {
__size++;
if (__size == 1) {
__root->__value = std::move(__x);
__root->__count++;
__nil->__parent = __root;
return __root;
}
__node_pointer __p = __root, __q = __p;
while (__p != __nil) {
__q = __p;
if (compare(std::move(__x), __p->__value)) __p = __p->__left;
else __p = __p->__right;
}
__p = __q;
__node_pointer __n = new __node;
__n->__parent = __p;
if (compare(std::move(__x), __p->__value)) __p->__left = __n;
else __p->__right = __n;
__n->__is_black = false;
__n->__left = __nil;
__n->__right = __nil;
__n->__value = std::move(__x);
__n->__count = 0;
for (__node_pointer __i = __n; __i != __nil; __i = __i->__parent) __i->__count++;
if (!__p->__is_black) __insert_balance(__n);
__nil->__parent = __root;
return __n;
}
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::__erase_balance(multi_rbtree::__node_pointer __x) {
if (__x == __root) {
__x->__is_black = true;
return;
}
__node_pointer __p = __x->__parent;
if (__x == __p->__left) {
__node_pointer __s = __p->__right, __l = __s->__left, __r = __s->__right;
if (!__r->__is_black) {
__left_rotate(__s);
std::swap(__p->__is_black, __s->__is_black);
__r->__is_black = true;
} else if (!__l->__is_black) {
__right_rotate(__l);
__left_rotate(__l);
__l->__is_black = __p->__is_black;
__p->__is_black = true;
} else if (!__s->__is_black) {
__left_rotate(__s);
__p->__is_black = false;
__s->__is_black = true;
__erase_balance(__x);
} else if (!__p->__is_black) {
__p->__is_black = true;
__s->__is_black = false;
} else {
__s->__is_black = false;
__erase_balance(__p);
}
} else {
__node_pointer __s = __p->__left, __l = __s->__left, __r = __s->__right;
if (!__l->__is_black) {
__right_rotate(__s);
std::swap(__p->__is_black, __s->__is_black);
__l->__is_black = true;
} else if (!__r->__is_black) {
__left_rotate(__r);
__right_rotate(__r);
__r->__is_black = __p->__is_black;
__p->__is_black = true;
} else if (!__s->__is_black) {
__right_rotate(__s);
__p->__is_black = false;
__s->__is_black = true;
__erase_balance(__x);
} else if (!__p->__is_black) {
__p->__is_black = true;
__s->__is_black = false;
} else {
__s->__is_black = false;
__erase_balance(__p);
}
}
}
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::__erase(multi_rbtree::__node_pointer __x) {
if (__x == __nil) return;
if (__size != 1) {
__node_pointer __a = __find_min(__x->__right);
if (__a == __nil) __a = __x;
else __x->__value = __a->__value;
if (__a->__left != __nil || __a->__right != __nil) {
__node_pointer __b;
if (__a->__right != __nil) __b = __a->__right;
else __b = __a->__left;
if (__a == __root) {
__root = __b;
__b->__is_black = true;
__b->__parent = __nil;
} else {
if (__a->__parent->__left == __a) __a->__parent->__left = __b;
else __a->__parent->__right = __b;
__b->__parent = __a->__parent;
for (__node_pointer __i = __b->__parent; __i != __nil; __i = __i->__parent) __i->__count--;
if (!__a->__is_black || !__b->__is_black) __b->__is_black = true;
else __erase_balance(__b);
}
} else {
if (__a->__is_black) __erase_balance(__a);
if (__a->__parent->__left == __a) __a->__parent->__left = __nil;
else __a->__parent->__right = __nil;
for (__node_pointer __i = __a->__parent; __i != __nil; __i = __i->__parent) __i->__count--;
}
delete __a;
}
__size--;
__nil->__parent = __root;
}
template<class _Tp, class _Comp>
multi_rbtree<_Tp, _Comp>::multi_rbtree() { __init(); }
template<class _Tp, class _Comp>
multi_rbtree<_Tp, _Comp>::multi_rbtree(const std::vector<value_type> &__v) {
__init();
insert(__v);
}
template<class _Tp, class _Comp>
multi_rbtree<_Tp, _Comp>::multi_rbtree(const std::initializer_list<value_type> &__il) {
__init();
insert(__il);
}
template<class _Tp, class _Comp>
template<class _InputIterator>
multi_rbtree<_Tp, _Comp>::multi_rbtree(_InputIterator __first, _InputIterator __last) {
__init();
insert(__first, __last);
}
template<class _Tp, class _Comp>
multi_rbtree<_Tp, _Comp>::multi_rbtree(const multi_rbtree &other) {
this->__init();
for (auto &i: other) this->insert(i);
}
template<class _Tp, class _Comp>
multi_rbtree<_Tp, _Comp> &multi_rbtree<_Tp, _Comp>::operator=(const multi_rbtree &other) {
this->clear();
for (auto &i: other) this->insert(i);
return *this;
}
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::clear() { while (!empty()) __erase(__root); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::insert(const value_type &__x) { return iterator(__insert(__x, comp_type())); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::insert(value_type &&__x) { return iterator(__insert(std::move(__x), comp_type())); }
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::insert(const std::vector<value_type> &__v) { insert(__v.begin(), __v.end()); }
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::insert(const std::initializer_list<value_type> &__il) { insert(__il.begin(), __il.end()); }
template<class _Tp, class _Comp>
template<class _InputIterator>
void multi_rbtree<_Tp, _Comp>::insert(_InputIterator __first, _InputIterator __last) {
for (; __first != __last; ++__first)
insert(*__first);
}
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::erase(multi_rbtree::iterator __it) { __erase(__it.__get_np()); }
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::erase(const value_type &__x) {
__node_pointer __p = __find(__x, comp_type());
if (__p->__value != __x) return;
__erase(__p);
}
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::erase(value_type &&__x) {
__node_pointer __p = __find(std::move(__x), comp_type());
if (__p->__value != std::move(__x)) return;
__erase(__p);
}
template<class _Tp, class _Comp>
unsigned long multi_rbtree<_Tp, _Comp>::size() { return __size; }
template<class _Tp, class _Comp>
bool multi_rbtree<_Tp, _Comp>::empty() { return !__size; }
template<class _Tp, class _Comp>
bool multi_rbtree<_Tp, _Comp>::empty() const { return !__size; }
template<class _Tp, class _Comp>
bool multi_rbtree<_Tp, _Comp>::has(const value_type &__x) {
__node_pointer __p = __find(__x, comp_type());
return __p->__value == __x;
}
template<class _Tp, class _Comp>
bool multi_rbtree<_Tp, _Comp>::has(value_type &&__x) {
__node_pointer __p = __find(std::move(__x), comp_type());
return __p->__value == std::move(__x);
}
template<class _Tp, class _Comp>
unsigned long multi_rbtree<_Tp, _Comp>::count(const value_type &__x) { return index_of(upper_bound(__x)) - index_of(lower_bound(__x)); }
template<class _Tp, class _Comp>
unsigned long multi_rbtree<_Tp, _Comp>::count(value_type &&__x) { return index_of(upper_bound(std::move(__x))) - index_of(lower_bound(std::move(__x))); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::find(const value_type &__x) {
__node_pointer __p = __find(__x, comp_type());
if (__p->__value == __x) return iterator(__p);
return end();
}
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::find(value_type &&__x) {
__node_pointer __p = __find(std::move(__x), comp_type());
if (__p->__value == std::move(__x)) return iterator(__p);
return end();
}
template<class _Tp, class _Comp>
std::pair<typename multi_rbtree<_Tp, _Comp>::iterator, unsigned long>
multi_rbtree<_Tp, _Comp>::find_with(const value_type &__x) {
__node_pointer __ret = __find(__x, comp_type());
if (__ret->__value == __x) return std::make_pair(iterator(__ret), __index_of(__ret));
return std::make_pair(end(), size());
}
template<class _Tp, class _Comp>
std::pair<typename multi_rbtree<_Tp, _Comp>::iterator, unsigned long>
multi_rbtree<_Tp, _Comp>::find_with(value_type &&__x) {
__node_pointer __ret = __find(std::move(__x), comp_type());
if (__ret->__value == std::move(__x)) return std::make_pair(iterator(__ret), __index_of(__ret));
return std::make_pair(end(), size());
}
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::nth_element(const unsigned long &__x) { return iterator(__nth_element(__x)); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::nth_element(unsigned long &&__x) { return iterator(__nth_element(__x)); }
template<class _Tp, class _Comp>
unsigned long multi_rbtree<_Tp, _Comp>::index_of(const iterator &__x) {
if (__x.__get_np() == __nil) return size();
return __index_of(__x.__get_np());
}
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::lower_bound(const value_type &__x) { return iterator(__lower_bound(__x, comp_type())); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::lower_bound(value_type &&__x) { return iterator(__lower_bound(std::move(__x), comp_type())); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::upper_bound(const value_type &__x) {
iterator it(__upper_bound(__x, comp_type()));
if (*it == __x) ++it;
return it;
}
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::upper_bound(value_type &&__x) {
iterator it(__upper_bound(std::move(__x), comp_type()));
if (*it == std::move(__x)) ++it;
return it;
}
template<class _Tp, class _Comp>
std::pair<typename multi_rbtree<_Tp, _Comp>::iterator, typename multi_rbtree<_Tp, _Comp>::iterator>
multi_rbtree<_Tp, _Comp>::equal_range(const value_type &__x) { return std::make_pair(lower_bound(__x), upper_bound(__x)); }
template<class _Tp, class _Comp>
std::pair<typename multi_rbtree<_Tp, _Comp>::iterator, typename multi_rbtree<_Tp, _Comp>::iterator>
multi_rbtree<_Tp, _Comp>::equal_range(value_type &&__x) { return std::make_pair(lower_bound(std::move(__x)), upper_bound(std::move(__x))); }
template<class _Tp, class _Comp>
void multi_rbtree<_Tp, _Comp>::merge(const multi_rbtree &t) { for (auto &i: t) insert(i); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::begin() {
if (empty()) return iterator(__nil);
return iterator(__find_min(__root));
}
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::const_iterator
multi_rbtree<_Tp, _Comp>::begin() const {
if (empty()) return const_iterator(__nil);
return const_iterator(__find_min(__root));
}
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::reverse_iterator
multi_rbtree<_Tp, _Comp>::rbegin() { return reverse_iterator(end()); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::reverse_const_iterator
multi_rbtree<_Tp, _Comp>::rbegin() const { return reverse_const_iterator(cend()); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::iterator
multi_rbtree<_Tp, _Comp>::end() { return iterator(__nil); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::const_iterator
multi_rbtree<_Tp, _Comp>::end() const { return const_iterator(__nil); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::reverse_iterator
multi_rbtree<_Tp, _Comp>::rend() { return reverse_iterator(begin()); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::reverse_const_iterator
multi_rbtree<_Tp, _Comp>::rend() const { return reverse_const_iterator(cbegin()); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::const_iterator
multi_rbtree<_Tp, _Comp>::cbegin() const {
if (empty()) return const_iterator(__nil);
return const_iterator(__find_min(__root));
}
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::reverse_const_iterator
multi_rbtree<_Tp, _Comp>::crbegin() const { return reverse_const_iterator(cend()); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::const_iterator
multi_rbtree<_Tp, _Comp>::cend() const { return const_iterator(__nil); }
template<class _Tp, class _Comp>
typename multi_rbtree<_Tp, _Comp>::reverse_const_iterator
multi_rbtree<_Tp, _Comp>::crend() const { return reverse_const_iterator(cbegin()); }
template<class _Tp, class _Comp>
multi_rbtree<_Tp, _Comp>::~multi_rbtree() { clear(); }
#endif //COLLECTIONS_RBTREE_H
Raw
rbtree.md

Red_Black_Tree

Implementation of red black tree with iterator. It is made similar to the std::set, only set uses the allocator but this uses new operator. But this is better than std::set since it has the function to access to the index of each nodes. This is not a multiset. So, each values in the tree would be counted one.

this doc is to be updated

Tree Functions and Variable.

template<class _Tp> class __tree_iterator_

types

  • typedef _Tp value_type
  • typedef value_type *pointer
  • typedef value_type &reference
  • typedef __tree_node_<_Tp> *node_pointer
  • typedef bidirectional_iterator_tag iterator_category
  • typedef ptrdiff_t difference_type

public functions

reference operator*()

Time Complexity: O(1)

Returns the value that the iterator is pointing at. If the iterator is pointing to __nil, it will have undefined behavior depended on compiler.(Probably returns the initalation value of the value_type.

pointer operator->()

Time Complexity: O(1)

Returns the pointer to the value that the iterator is pointing at. If the iterator is pointing to __nil, it will be undefined behavior depended on compiler.

__tree_iterator_ &operator++()

It is postfix operator++. Makes this iterator to point next node when it is sorted by _Comp. If this iterator is pointing to the __nil, the next iterator would be begin(). If this iterator is end(), the next iterator would be __nil.

Time complexity: amortized O(1)

How it works: By traveling the tree in in-order, the values would be sorted.

Returns the next iterator.

__tree_iterator_ operator++(int)

It is prefix operator++. Makes this iterator to point next node when it is sorted by _Comp.

Time complexity: amortized O(1)

Returns this iterator.

__tree_iterator_ &operator--()

It is postfix operator--. Makes this iterator to point the previous node when it is sorted by _Comp. If this iterator is pointing to the __nil, the previous iterator would be end(). If this iterator is iterator-begin(), the previous iterator would be __nil.

Time complexity: amortized O(1)

How it works: By traveling the tree in in-order reverse, the values would be sorted.

Returns the previous iterator.

__tree_iterator_ operator--(int)

It is prefix operator--. Makes this iterator to point the previous node when it is sorted by _Comp.

Time complexity: amortized O(1)

Returns this iterator.

bool operator==(const __tree_iterator_ &__x)

Time Complexity: O(1)

Returns true if two iterator are pointing to same node or false.

bool operator!=(const __tree_iterator_ &__x)

Time Complexity: O(1)

Returns true if two iterator are pointing to different node or false.

private functions

inline bool __is_nil(node_pointer __p)

Time Complexity: O(1)

Returns true if the node is __nil.

node_pointer __get_np()

Used in the tree class.

Time Complexity: O(1)

Returns the node pointer that iterator is pointing.

private variable

node_pointer *__ptr

The node pointer that the iterator is pointing at.

template<class _Tp,class _Comp=less<_Tp>> class tree

types

  • typedef _Tp value_type
  • typedef _Comp comp_type
  • typedef __tree_node_<value_type> __node
  • typedef __node *__node_pointer
  • typedef __tree_iterator_<value_type> iterator
  • typedef __tree_const_iterator_<value_type> const_iterator
  • typedef std::reverse_iterator<iterator> reverse_iterator
  • typedef std::reverse_iterator<const_iterator> reverse_const_iterator

public functions

tree()

A simple constructor.

Time Complexity: O(1)

tree(vector<value_type> __v)

The constructor that inserts all the values in the __v.

Time Complexity: O(n log n) when n is the size of vector.

tree(initializer_list<value_type> __il)

The constructor that inserts all the values in the __il.

Time Complexity: O(n log n) when n is the size of the initializer_list.

template<class _InputIterator> tree(_InputIterator __first, _InputIterator __last)

The constructor that inserts all the values from _InputIterator __first to _InputIterator __last.

Time Complexity: O(n log n) when n is the distance of __last and __first.

void clear()

The clear function that deallocates all the nodes.

Time Complexity: O(n) when n is the size of the tree.

How it works: It erases __root n times. Since it is O(1) to erase __root, time complexity would be O(n).

void insert(value_type __x)

Inserts the value that is given. If the value is already in the tree, it would do nothing.

  • __x is the value to insert.

Time Complexity: O(log n) when n is the size of the tree.

How it works: It finds the position in the tree to insert and allocates a new node. Then it self-balances the tree.

void insert(vector<value_type> __v)

Inserts all the value in the vector. If some values are already in the tree, that would not be inserted.

  • __v is the vector to insert.

Time Complexity: O(m log n) when n is the size of the tree and m is size of the vector.

void insert(initializer_list<value_type> __il)

Inserts all the value in the initializer_list. If some values are already in the tree, that would not be inserted.

  • __il is the initializer_list to insert.

Time Complexity: O(m log n) when n is the size of the tree and m is size of the initializer_list.

template<class _InputIterator> void insert(_InputIterator __first, _InputIterator __last)

Inserts all the value from _InputIterator __first to _InputIterator __last. If some values are already in the tree, that would not be inserted.

  • _InputIterator __first is the iterator to start from.
  • _InputIterator __last is the iterator to end.

Time Complexity: O(m log n) when n is the size of the tree and m is the distance of __last and __first.

void erase(iterator __it)

Erases the value that the iterator is pointing.

  • __it is the iterator pointing to the tree node.

Time Complexity: O(log n) when n is the size of the tree.

How it works: It finds the node to erase and swap the value with the minimum value of the right sub-tree of the node. Then it self-balances the tree.

void erase(value_type __x)

Erases the value in the tree. If the value is already in the tree, it would do nothing.

  • __x is the value to erase.

Time Complexity: O(log n) when n is the size of the tree.

unsigned long size()

Time Complexity: O(1)

Returns the size of the tree.

bool empty()

Time Complexity: O(1)

Returns true if the tree is empty or false.

bool has(value_type __x)

Function that lets you know whether value is in the tree or not.

  • __x is the value to check.

Time Complexity: O(log n) when n is the size of the tree.

Returns true if the tree has the value.

unsigned long count(value_type __x)

Function that counts the value. Since the value can have same value up to 1, it would return 1 or 0.

  • __x is the value to check.

Time Complexity: O(log n) when n is the size of the tree.

Returns count of the value.

iterator find(value_type __x)

Finds the value in the tree.

  • __x is the value to find.

Time Complexity: O(log n) when n is the size of the tree.

Returns the iterator that is pointing the value. If the value is not in the tree, it returns end().

pair<iterator, unsigned long> find_with(value_type __x)

Function that gets find and index_of together in a pair. (0 based)

  • __x is the value to find.

Time Complexity: O(log n) when n is the size of the tree.

Returns the find and index_of into pair.

iterator nth_element(unsigned long __x)

Finds the iterator that is nth element when sorted by _Comp.

  • __x is the index to find.

Time Complexity: O(log n) when n is the size of the tree.

Returns the iterator that is pointing the value of nth element. If the index is out of the range, it will return end().

unsigned long index_of(iterator __x)

Finds the index of the index of the iterator when sorted by _Comp.

Time Complexity: O(log n) when n is the size of the tree.

Returns the index of the iterator. If the iterator is pointing __nil, it will return the size of the tree.

iterator lower_bound(value_type __x)

A simple lower bound function.

  • __x is the value to find.

Time Complexity: O(log n) when n is the size of the tree.

Returns the iterator of lower bound.

iterator upper_bound(value_type __x)

A simple upper bound function.

  • __x is the value to find.

Time Complexity: O(log n) when n is the size of the tree.

Returns the iterator of upper bound.

pair<iterator, iterator> equal_range(value_type __x)

A simple equal range function.

  • __x is the value to find.

Time Complexity: O(log n) when n is the size of the tree.

Returns the pair of lower_bound and upper_bound.

iterator begin()

A simple begin iterator.

Time Complexity: O(log n) when n is the size of the tree.

Returns the begin iterator.

reverse_iterator rbegin()

A simple reverse begin iterator.

Time Complexity: O(1)

Returns the reverse begin iterator.

iterator end()

A simple end iterator.

Time Complexity: O(1)

Returns the end iterator.

reverse_iterator rend()

A simple reverse end iterator.

Time Complexity: O(log n) when n is the size of the tree.

Returns the reverse end iterator.

const_iterator cbegin()

A simple const begin iterator.

Time Complexity: O(log n) when n is the size of the tree.

Returns the const begin iterator.

reverse_const_iterator crbegin()

A simple reverse const begin iterator.

Time Complexity: O(1)

Returns the reverse const begin iterator.

const_iterator cend()

A simple const end iterator.

Time Complexity: O(1)

Returns the const end iterator.

reverse_const_iterator crend()

A simple reverse const iterator.

Time Complexity: O(log n) when n is the size of the tree.

Returns the reverse const end iterator.

~tree()

A simple destructor that deallocates all the nodes.

Time Complexity: O(n) when n is the size of the tree.

private functions

inline void __init()

A simple initialization function. It initialize the __root and __nil.

Time Complexity: O(1)

template<class _Compare> inline __node_pointer __find(value_type __x, _Compare compare)

A find function of a value implementation.

  • __x is a value to find.
  • compare is a function to compare two values.

Time Complexity: O(log n) when n is the size of the tree.

Returns the node pointer to the value. If there is no value in the tree, it would return the last leaf node that had searched.

inline __node_pointer __find_min(__node_pointer __p)

A function to find min value from the sub-tree of the node pointer.

  • __p is the node pointer to find.

Time Complexity: O(log n) when n is the size of the tree.

Preconditions: __p is not __nil.

Returns the node pointer to the min value from pointer.

inline __node_pointer __nth_element(unsigned long __x)

An nth element function implementation.

  • __x is the index to find.

Time Complexity: O(log n) when n is the size of the tree.

Returns the node pointer to the nth element. If index is out of the range, it will return __nil.

template<class _Compare> inline unsigned long __index_of(value_type __x, _Compare compare)

An index of function implementation.

  • __x is the value to find.
  • compare is the function to compare two values.

Time Complexity: O(log n) when n is the size of the tree.

Returns the index of the value. If the tree doesn't have the value, it will return the size of the tree.

template<class _Compare> inline __node_pointer __lower_bound(value_type __x, _Compare compare)

A lower bound function implementation.

  • __x is the value to find.
  • compare is the function to compare two values.

Time Complexity: O(log n) when n is the size of the tree.

Returns the node pointer to the first not-small value.

inline __node_pointer __sibling_node(__node_pointer __p)

A sibling node pointer to input.

  • __p is the node pointer to get.

Time Complexity: O(1)

Preconditions: __p is not __nil

Returns the sibling node pointer. If __p is __root or has no sibling, it would return __nil.

void __left_rotate(__node_pointer __b)

Left rotates the tree from node pointer's parent.

  • __b is the node to rotate.

Time Complexity: O(1)

Preconditions: __p is not __nil

void __right_rotate(__node_pointer __b)

Right rotates the tree from node pointer's parent.

  • __b is the node to rotate.

Time Complexity: O(1)

Preconditions: __p is not __nil

void __insert_balance(__node_pointer __p)

Balances the tree from node pointer. Called after insertion.

  • __p is the node to balance.

Time Complexity: amortized O(1)

Preconditions: __p is red and __p's parent is red.

template<class _Compare> void __insert(value_type __x, _Compare compare)

Allocates a new node and inserts to the tree.

  • __x is the value to insert.
  • compare is the function to compare two values.

Time Complexity: O(log n)

void __erase_balance(__node_pointer __x)

Balances the tree from node pointer. Called after erase.

  • __x is the node pointer to erase.

Time Complexity: amortized O(1)

Preconditions: __x's sub-tree black nodes count is 1 smaller than sibling of __x's

void __erase(__node_pointer __x)

Deallocates the node pointer. If node pointer is __nil, it will do nothing.

  • __x is the node pointer to erase.

Time Complexity: O(log n)

private variable

__node_pointer __root

The root of the tree. It always have to be black.

__node_pointer __nil

This is the null node. It is a child of the end nodes if the node doesn't have a node to have. Also __root's parent would be nil. nil is black and it's children is nil. But, in this tree class, nil's parent would be __root to access in the iterator class.

unsigned long __size

The size of the tree.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment