redblack_tree.hpp

Go to the documentation of this file.

 
#pragma once
 
#include <type_traits>
#include "book.hpp"
 
#define rbtree RBTree
 
#define rbtnode RbtNode
 
using namespace std;
 
enum Color { RED, BLACK };
 
class RbtNode {
public:
    int key; 
    book value; 
    RbtNode *left; 
    RbtNode *right; 
    RbtNode *parent; 
    Color color; 
public:
    RbtNode(int k, const book& v) : key(k), value(v), left(nullptr), right(nullptr), parent(nullptr), color(RED) {}
 
    RbtNode* sibling() const;
};
 
class RBTree
{
private:
    rbtnode *root; 
    int color_flip_count; 
    void rotate_left(rbtnode *&, rbtnode *&); 
    void rotate_right(rbtnode *&, rbtnode *&); 
    void fix_colorviolation(rbtnode *&, rbtnode *&); 
    rbtnode* insert_node(rbtnode* root_node, rbtnode* node); 
    void remove(rbtnode* node); 
    rbtnode* BSTreplace(rbtnode* x); 
    rbtnode* successor(rbtnode* x); 
    void fix_double_black(rbtnode* node); 
public:
    RBTree();
 
    int ColorFlipCount();
 
    rbtnode* begin();
 
    rbtnode* end();
 
    void add(book book_info);
 
    void remove(int key);
 
    rbtnode* find(int key) const;
 
    std::vector<int> findclosest(int targetId) const;
 
    rbtnode* operator[](int key) const;
 
    bool empty() const;
};