red_black_tree.h

Zobrazit dokumentaci tohoto souboru.

//======== Copyright (c) 2018, FIT VUT Brno, All rights reserved. ============//
//
// Purpose:     Red-Black Self balancing Tree public interface
//
// $NoKeywords: $ivs_project_1 $red_black_tree.h
// $Authors:    Filip Vaverka <ivaverka@fit.vutbr.cz>
//              David Grochol <igrochol@fit.vutbr.cz>
// $Date:       $2018-02-08
//============================================================================//
#pragma once
 
#ifndef RED_BLACK_TREE_H_
#define RED_BLACK_TREE_H_
 
#include <utility>
#include <vector>
 
#include "red_black_tree_lib.h"
 
class BinaryTree
{
public:
    enum Color_t {
        RED = ::Color_t::RED,
        BLACK = ::Color_t::BLACK
    };
 
    typedef ::Node_t Node_t;
    /*{
        Node_t *pParent;    ///< Ukazatel na rodice uzlu, nebo NULL v pripade korene.
        Node_t *pLeft;      ///< Ukazatel na leveho potomka uzlu, nebo NULL pro listovy uzel.
        Node_t *pRight;     ///< Ukazatel na praveho potomka uzlu, nebo NULL pro listovy uzel.
        Color_t color;      ///< Barva uzlu (Color_t), tj. RED nebo BLACK.
 
        int key;            ///< Hodnota/klic tohoto uzlu.
    };*/
 
    BinaryTree() {
        BTCreate(&m_pRoot);
    }
 
    ~BinaryTree() {
        BTDestroy(&m_pRoot);
    }
 
    std::pair<bool, Node_t *> InsertNode(int key) {
 
        Node_t *pNewNode = NULL;
        bool bIsNew = BTInsertNode(&m_pRoot, key, &pNewNode);
 
        return std::make_pair(bIsNew, pNewNode);
    }
 
    void InsertNodes(const std::vector<int> &keys,
                     std::vector<std::pair<bool, Node_t *> > &outNewNodes) {
        outNewNodes.clear();
 
        std::vector<Node_t *> newNodes(keys.size());
        std::vector<int> newNodesState(keys.size());
        BTInsertNodeMany(&m_pRoot, keys.size(), &keys[0], &newNodes[0],
                &newNodesState[0]);
 
        for(size_t i = 0; i < keys.size(); ++i)
            outNewNodes.push_back(std::make_pair(newNodesState[i] != 0, newNodes[i]));
    }
 
    bool DeleteNode(int key) {
        return BTDeleteNode(&m_pRoot, key);
    }
 
    Node_t *FindNode(int key) const {
        return BTFindNode(m_pRoot, key);
    }
 
    void GetLeafNodes(std::vector<Node_t *> &outLeafNodes) {
        size_t count = 0;
 
        BTGetLeafNodes(m_pRoot, &count, NULL);
 
        outLeafNodes.resize(count);
 
        if(count > 0)
            BTGetLeafNodes(m_pRoot, &count, &outLeafNodes[0]);
    }
 
    void GetAllNodes(std::vector<Node_t *> &outAllNodes) {
        size_t count = 0;
 
        BTGetAllNodes(m_pRoot, &count, NULL);
 
        outAllNodes.resize(count);
 
        if(count > 0)
            BTGetAllNodes(m_pRoot, &count, &outAllNodes[0]);
    }
 
    void GetNonLeafNodes(std::vector<Node_t *> &outNonLeafNodes) {
        size_t count = 0;
 
        BTGetNonLeafNodes(m_pRoot, &count, NULL);
 
        outNonLeafNodes.resize(count);
 
        if(count > 0)
            BTGetNonLeafNodes(m_pRoot, &count, &outNonLeafNodes[0]);
    }
 
    Node_t *GetRoot() { return m_pRoot; }
 
protected:
    Node_t *m_pRoot;    
};
 
 
#endif // RED_BLACK_TREE_H_