真c++二叉樹から赤黒樹(2)への二叉樹基類
46996 ワード
この文章は二叉樹から赤黒樹シリーズの文章の第二節であり,主に二叉樹抽象基類の基本構成を紹介する.後続BST、AVL、RedBlackのために敷き詰めます
文書ディレクトリ一、前の文章のリンク~(右の波線をクリックしてディレクトリに戻る) 二、二叉樹抽象基類~ (一)変数とインタフェースを定義~ 1.必要な変数～ 2.必要なインタフェース~ 3.重要補助関数~ 4.その他の補助関数~ 5.BinTree.h~ (二)現在のノードの親の子の参照を取得~ (3)現在のノードの高さを更新~ (四)現在のノードとその祖先ノードの高さを更新~ .(五)削除関数~ (六)release.hヘッダファイル~ (七)完全BinTree.h~ 三、後序文章リンク~ 一、前の文章のリンク~(右の波線をクリックして目次に戻る)
本文を読む前に、前の文章のカタログ、前言、基本的な紹介を強くお勧めします.そうしないと、後の内容が理解できません.リンクは次のとおりです.基本ツリーノード、汎用関数ツリーノード 二、二叉木抽象基類~
(一)変数とインタフェースの定義~
1.必要な変数~
2.必要なインターフェース~
3.重要補助関数~
4.その他の補助関数~
5.BinTree.h~
(二)現在のノードの父親の子供の引用を取得する~
この関数はAVLツリーとRedBlackツリーの挿入と削除にとって重要です.この関数の役割をAVLとRedBlackツリーの対応する部分で再度説明します.
(三)現在のノードの高さを更新する~
ここでstatureは、このシリーズの第1節でグローバル領域で定義された関数で、ヘッダファイルはBInNode_です.Macro.h.
(四)現在のノードとその祖先ノードの高さを更新する~
通常、現在のノードからparentポインタに沿って逆行して、この祖先の高さが変わらないときに停止するまで、各世代の祖先の高さ記録を順次更新する必要があります.
(五)関数の削除~
この関数は,BST,AVL,RedBlackにかかわらず,すべてのツリーの解析に用いられる.
(六)release.hヘッダファイル~
(5)の削除コードには、ヘッダファイルreleaseにあるrelease関数を用いたノードの削除が見られる.h中.
この削除関数はテンプレート偏特化技術を用いた.
(七)完全なBinTree.h~
三、後序文章リンク~基本ツリーノード、汎用関数ツリーノード 基本二叉木クラスの定義と実現二叉木ベースクラス BST(二叉探索ツリーの実装)BST AVL(二叉バランス探索ツリーの実現)AVL Bツリーの実装(Bツリーのみを知りたい場合は、すべての章をスキップして、直接Bツリーを見ることができます)Bツリー 赤黒樹の実現RedBlack 一つのことを学んで、その道理を知らないで、上手ではありません!
文書ディレクトリ
本文を読む前に、前の文章のカタログ、前言、基本的な紹介を強くお勧めします.そうしないと、後の内容が理解できません.リンクは次のとおりです.
(一)変数とインタフェースの定義~
1.必要な変数~
int _size;//
BinNodePtr _root;//
2.必要なインターフェース~
，
、
（ ）
3.重要補助関数~
。（ ， ）
FromParentTo
4.その他の補助関数~
updateHeight
updateHeightAbove
remove
insert（ ， ， ）
5.BinTree.h~
template<typename T=int>
class BinTree {
protected:
using BinNodePtr = BinNode<T>*;
using BinTreePtr = BinTree<T>*;
protected:
int _size;//
BinNodePtr _root;//
public:
BinTree() :_size(0), _root(nullptr) {}
virtual ~BinTree() {
//std::cout << " " << std::endl;
if (0 < _size)remove(_root);
}
public:
constexpr int size()const { return _size; }//
constexpr bool empty()const { return !_root; }//
inline BinNodePtr root()const {//
return (_root) ? _root : nullptr;
}
constexpr int getHeight()const {//
return (this->_root) ? this->_root->_height : -1;
}
public:
template<typename VST>//
void travLevel(VST visit) {
if (_root)
_root->travLevel(visit);
}
template<typename VST>//
void travPre(VST visit,const int&method=1) {
if (_root)
_root->travPre(visit, method);
}
template<typename VST>//
void travIn(VST visit, const int& method = 1) {
if (_root)
_root->travIn(visit, method);
}
template<typename VST>//
void travPost(VST visit, const int& method = 1) {
if (_root)
_root->travPost(visit, method);
}
protected:
virtual int updateHeight(BinNodePtr x)const;// x /*vs c++ virtual constexpr*/
void updateHeightAbove(BinNodePtr x)const;// x
protected:
// ，
BinNodePtr& FromParentTo(BinNodePtr x) {/* x *//* */
return (IsRoot(x) ? this->_root : (IsLChild(x) ? x->_parent->_lchild : x->_parent->_rchild));
}
protected:
virtual BinNode<T>* insert(const T& data) = 0;// ， ， ， ，
private:
void remove(BinNodePtr x);// ， ，
};//class BinTree
(二)現在のノードの父親の子供の引用を取得する~
この関数はAVLツリーとRedBlackツリーの挿入と削除にとって重要です.この関数の役割をAVLとRedBlackツリーの対応する部分で再度説明します.
// ，
BinNodePtr& FromParentTo(BinNodePtr x) {/* x *//* */
return (IsRoot(x) ? this->_root : (IsLChild(x) ? x->_parent->_lchild : x->_parent->_rchild));
}
(三)現在のノードの高さを更新する~
ここでstatureは、このシリーズの第1節でグローバル領域で定義された関数で、ヘッダファイルはBInNode_です.Macro.h.
// x
template<typename T>
int BinTree<T>::updateHeight(BinNodePtr x)const {
//
return x->_height = 1 + std::max(stature(x->_lchild), stature(x->_rchild));
}
(四)現在のノードとその祖先ノードの高さを更新する~
通常、現在のノードからparentポインタに沿って逆行して、この祖先の高さが変わらないときに停止するまで、各世代の祖先の高さ記録を順次更新する必要があります.
// x
template<typename T>
void BinTree<T>::updateHeightAbove(BinNodePtr x)const{
if (x == nullptr)
return;
updateHeight(x);
do {
x = x->_parent;
if (x == nullptr)// ，
return;
int currentHeight = x->_height;//
int afterHeight = updateHeight(x);
if (currentHeight == afterHeight)// ，
break;
} while (x);//
}
(五)関数の削除~
この関数は,BST,AVL,RedBlackにかかわらず,すべてのツリーの解析に用いられる.
//========= ============//
template<typename T>
void BinTree<T>::remove(BinNodePtr x) {
if (nullptr==x)
return;
remove(x->_lchild);
remove(x->_rchild);/* ， */
release(x->_data);
release(x);
}
(六)release.hヘッダファイル~
(5)の削除コードには、ヘッダファイルreleaseにあるrelease関数を用いたノードの削除が見られる.h中.
この削除関数はテンプレート偏特化技術を用いた.
#pragma once
template<typename T>
struct Cleaner {
static void clean(T& x) {
#ifdef DEBUG
printf("
");
#endif // DEBUG
}
};
template<typename T>
struct Cleaner<T*> {
static void clean(T*& x) {// ， ，
if (x) {
delete x;
x = nullptr;
}
}
};
template<typename T>
static void release(T &x) {// ， , ， delete， ， 。
Cleaner<T>::clean(x);
}
(七)完全なBinTree.h~
#pragma once
#include"BinNode.h"
#include "release.h"
namespace mytree {
using namespace mytree_marcro;
template<typename T=int>
class BinTree {
protected:
using BinNodePtr = BinNode<T>*;
using BinTreePtr = BinTree<T>*;
protected:
int _size;//
BinNodePtr _root;//
public:
BinTree() :_size(0), _root(nullptr) {}
virtual ~BinTree() {
//std::cout << " " << std::endl;
if (0 < _size)remove(_root);
}
public:
constexpr int size()const { return _size; }//
constexpr bool empty()const { return !_root; }//
inline BinNodePtr root()const {//
return (_root) ? _root : nullptr;
}
constexpr int getHeight()const {//
return (this->_root) ? this->_root->_height : -1;
}
public:
template<typename VST>//
void travLevel(VST visit) {
if (_root)
_root->travLevel(visit);
}
template<typename VST>//
void travPre(VST visit,const int&method=1) {
if (_root)
_root->travPre(visit, method);
}
template<typename VST>//
void travIn(VST visit, const int& method = 1) {
if (_root)
_root->travIn(visit, method);
}
template<typename VST>//
void travPost(VST visit, const int& method = 1) {
if (_root)
_root->travPost(visit, method);
}
protected:
virtual int updateHeight(BinNodePtr x)const;// x /*vs c++ virtual constexpr*/
void updateHeightAbove(BinNodePtr x)const;// x
protected:
// ，
BinNodePtr& FromParentTo(BinNodePtr x) {/* x *//* */
return (IsRoot(x) ? this->_root : (IsLChild(x) ? x->_parent->_lchild : x->_parent->_rchild));
}
protected:
virtual BinNode<T>* insert(const T& data) = 0;// ， ， ， ，
private:
void remove(BinNodePtr x);// ， ，
};//class BinTree
//================ ==================//
// x
template<typename T>
int BinTree<T>::updateHeight(BinNodePtr x)const {
return x->_height = 1 + std::max(stature(x->_lchild), stature(x->_rchild));//
}
// x
template<typename T>
void BinTree<T>::updateHeightAbove(BinNodePtr x)const{
if (x == nullptr)
return;
updateHeight(x);
do {
x = x->_parent;
if (x == nullptr)// ，
return;
int currentHeight = x->_height;//
int afterHeight = updateHeight(x);
if (currentHeight == afterHeight)// ，
break;
} while (x);//
}
//========= ============//
template<typename T>
void BinTree<T>::remove(BinNodePtr x) {
if (nullptr==x)
return;
remove(x->_lchild);
remove(x->_rchild);/* ， */
release(x->_data);
release(x);
}
}//namespace mytree
三、後序文章リンク~