赤と黒の木のC++完全なソースコードの実現
23203 ワード
赤と黒の木のC++完全なソースコードの実現
作者:July、saturnman.時間:2010年3月29日.出典:http://blog.csdn.net/v_JULYvです.声明:著作権所有、権利侵害は必ず追及する.
前言: マホガニーシリーズの文章は5編目に書きました.第三篇の文章:赤と黒の木のcソースコードの実現と分析、c言語で完全に赤と黒の木を実現しましたが、個人的な感じ、コードはまだはっきりしていません.ここで、c++の完全なソースコードを提供し、読者を提供します.
このソースコードは多くのコンパクトされています.また、C++の実装方法を採用しているので、コードの維持と再利用が容易です.何か問題がありましたら、ご指摘ください.
第一部、赤と黒の木のc++完全なソースコードの実現
本文は赤と黒の木c++の完全なソースコードを含んでいます.すべての解釈は注釈の中に含まれています.すべての赤と黒の木に関する原理と各種の挿入、削除操作の状況は全部本人の赤と黒の木シリーズの前の4つの文章の中で詳しく述べました.そして、この赤と黒の木シリーズの第五篇の文章の中で、赤と黒の木は最初から最後までノードを挿入して削除する全過程のデモンストレーション図で、すべての挿入と削除の状況を一つ一つ展示し尽くしました. したがって、赤と黒の木のすべての原理については、他の文章を参照してください.したがって、関連する原理は、本明細書ではもはや説明しない.
ok、以下は赤黒樹c++のソースコードの全部です.まずRBTree.h、それからRBTree.cppです.
RBTree.h
第二部分、プログラムにバグがありますか?
2.1、赤と黒の木は絶対的なバランスが必要ですか?
上記のc++ソースは上記のテスト結果から見ても大丈夫です.しかし、プログラムには隠しバグがあります.次の二つのステップに分けて、このソースコードをテストします.
1、まずRBTree.hの最後に下記のコードを追加します.
public:void PrintTree(){u printNode];prvate:void_prinntNode(RB Node*node){if(node==NULL𞓜node==m nullNode)return;if(node->parent==NULL𞓜node->parent==munulNode){printf==================mmmunulullNode de de de de de de de de de de de de de de de de de de de dededededededeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffparent:%d/n",node->>data,node->parent->data,}else if(node->parent->Right==node){printf("right:%d,parent:%d/n"node->data,node->parent->>data,"{u printNode->left];
2、RBTree.cppファイルを書き換えます.
//file RBTree.cpp/written by saturnman、200108.udated by Juily、2010339.すべてのヘッダファイルは全部補充されました.今は直接このソースコードをコピーして確認できます.Juily、udated、2010.5.06.include((zhi include)//(zhi include)//(zhi include)///(zhi include)「RBTree.h」/もし.hファイルとcppファイルを一つのファイルに入れたら、この文はusing namespace stdを削除します.int main(){RB Treeeetree;tree.Insert(12,12);tree.Insert(1,1);tree.Insert(9,9);tree.Insert(2,2);tree.Insert(0,0);tree.Insert(11,11);tree.Insert.Insert(7,7);treee.Insert(((7,7))))))))+treee.Insert+treee.Intreee.Insert(((((((((((((((())))))))))))))))))))))))))))))k(i);random_shuffle(v.begin()、v.end();copy(v.begin()、v.end()、ostreamuuiterator(cout);cout<>
後にテストした結果、間違いがありました.つまり、次のノードに順番に挿入します.12、1、9、0、2、11、7の後、赤と黒の木は次のようになります.
ルートノード9を削除し、上記のプログラムを経て運転した結果、以下のようになります.
つまり上記の運転結果は、対応するマホガニーの状態は以下の通りです.
はい、ご覧のように、上記のプログラムはルートノード9を削除した後、正しい赤と黒の木の状態はルートノード9の代わりに7であるべきです.7は新しいルートノードになり、ノード7は黒であり、上記の結果は完全に間違っています.赤と黒の木はすでに完全にバランスが取れていません.これでやっと発見されました.
説明:このプログラムのバグはネットユーザーの鑫に指摘されました.また、ネット上の多くのプログラムには、この問題が存在していることが分かりました.http://sd.csdn.net/a/20110506/297285.html赤い木のflashのデモンストレーションバージョンにもこのような問題があります.
残念ですが、テストを重ねました.赤い木のflashバージョンに問題があります.:http://www.cs.usfca.edu/~galles/visualzation/flash.このシーケンスを順次に挿入すると、15,1,9,2,0,12,16,7,11,13,17,14,14,000本のノード9を削除し、重大なエラーが出てきます.上のバージョンは簡単なステップで7を9の代わりにルートノードにして、7つのノードを黒にします.ツリーはその後の調整がなく、完全にバランスが取れません.問題が出たら、この赤い木の間違いflashバージョンがもっと多くの人を誤解させないようにしたいです.また、問題は友達の鑫が出したものです.この問題を覚えておきます.解決すれば、ブログに発表します.その後:鑫はavlツリーにも問題があります.July、構造のアルゴリズムの道博主です.2010.5.07.
しかし事実は、果たしてそうなのか?以下の2.1節の修正を見てください.
2.1、赤と黒の木は厳格なバランスを要求しない
修正:このプログラムには何の問題もありません.前に意識していなかったために、上記のような錯覚を起こしました.つまり、赤と黒の木は厳密な意味ではなく、二叉で木を探しています.それは自分の5つの性質を満足すればいいです.厳密なバランスは要求されません.だから、上の例では、12、1、9、0、2、11、7、根の結点9を削除してください.同じように、赤と黒の5つの性質に違反していません.だから、私は凡庸な人です.sorry.
それともこの言葉ですか?何か問題があったら、誰かに指摘してください.
第三部分、読者フィードバック
RB_Tree挿入削除操作についての議論
July:
すみません、RB Treeの完全な実現コードについては、すでにあなたのブログに書いてありますが、コードの中に修正が必要なところがあると思います.
起因
私はこのごろRB Treeを勉強しています.RB Treeの性質を無視しました.(3):葉の結点は全部黒で、RB Treeの操作について何日間か悩んでいます.私はまだ意識していない時に、偶然あなたのブログを見て、答えをもらいたいです.そして、その中には議論すべきところがあります.
エラー
下図は修正関数InsertFixUpを挿入する部分のスクリーンショットです.
あなたの記事の住所:http://blog.csdn.net/v_july_v/article/details/6285620
図 1
「アルゴリズム導論」で述べたように、InsertFixUpでは、whileサイクルごとに3つの状況に直面します.
case 1:zのおじさんyは赤いです.
case 2:zのおじさんyは黒で、zは右の子供です.
case 3:zのおじさんyは黒で、zは左の子供です.
なお、case 2はcase 3に落下しているので、この2つのケースは互いに反発するものではありません.あなたのコードの中で、case 2とcase 3をそれぞれifとelseの中に置いて、互いに独立することになります.これは違います.
修正
したがって、図1において「①」のelseは追加できませんので、削除します.
残念なことに、あなたのRB_Treeの削除修正操作はDeleteFixUpにも同様のエラーが発生したと思います.DeleteFixUpに対して処理された4つのケースも同様に反発し合うものではなく、あなたはif...else if...case 2,3,4を全部独立させます.
以上は拙者の愚見です.間違ったところがあれば、また検討してください.
楊 スーパー
CSDN ID:crischaos
201.10.06
考証:楊兄の手紙指導に感謝します.アルゴリズム導論書のもとの挿入状況の修復コードから見て:
マホガニーシリーズの最初の5つの記事:
4、
ステップ1図1コード、R-B Tree
1、
赤黒い木を徹底的に理解するように教えます.
5、
赤と黒のツリーを挿入して、リンクを削除する全行程のデモンストレーション.
3、
赤と黒の木のcソースコードの実現と分析
2、
マホガニーのアルゴリズムの実現と分析
6、お礼:
http://saturnman.blog.163.com/.
終わります.
作者:July、saturnman.時間:2010年3月29日.出典:http://blog.csdn.net/v_JULYvです.声明:著作権所有、権利侵害は必ず追及する.
前言: マホガニーシリーズの文章は5編目に書きました.第三篇の文章:赤と黒の木のcソースコードの実現と分析、c言語で完全に赤と黒の木を実現しましたが、個人的な感じ、コードはまだはっきりしていません.ここで、c++の完全なソースコードを提供し、読者を提供します.
このソースコードは多くのコンパクトされています.また、C++の実装方法を採用しているので、コードの維持と再利用が容易です.何か問題がありましたら、ご指摘ください.
第一部、赤と黒の木のc++完全なソースコードの実現
本文は赤と黒の木c++の完全なソースコードを含んでいます.すべての解釈は注釈の中に含まれています.すべての赤と黒の木に関する原理と各種の挿入、削除操作の状況は全部本人の赤と黒の木シリーズの前の4つの文章の中で詳しく述べました.そして、この赤と黒の木シリーズの第五篇の文章の中で、赤と黒の木は最初から最後までノードを挿入して削除する全過程のデモンストレーション図で、すべての挿入と削除の状況を一つ一つ展示し尽くしました. したがって、赤と黒の木のすべての原理については、他の文章を参照してください.したがって、関連する原理は、本明細書ではもはや説明しない.
ok、以下は赤黒樹c++のソースコードの全部です.まずRBTree.h、それからRBTree.cppです.
RBTree.h
//file RBTree.h
//written by saturnman,20101008。
//updated by July,20110329。
/*-----------------------------------------------
:
July saturnman c++ ,
, 。
------------------------------------------------*/
#ifndef _RB_TREE_H_
#define _RB_TREE_H_
#include
#include
#include
#include
using namespace std;
template
class RB_Tree
{
private:
RB_Tree(const RB_Tree& input){}
const RB_Tree& operator=(const RB_Tree& input){}
private:
enum COLOR{ RED, BLACK };
class RB_Node
{
public:
RB_Node()
{
//RB_COLOR = BLACK;
right = NULL;
left = NULL;
parent = NULL;
}
COLOR RB_COLOR;
RB_Node* right;
RB_Node* left;
RB_Node* parent;
KEY key;
U data;
};
public:
RB_Tree()
{
this->m_nullNode = new RB_Node();
this->m_root = m_nullNode;
this->m_nullNode->right = this->m_root;
this->m_nullNode->left = this->m_root;
this->m_nullNode->parent = this->m_root;
this->m_nullNode->RB_COLOR = BLACK;
}
bool Empty()
{
if (this->m_root == this->m_nullNode)
{
return true;
}
else
{
return false;
}
}
// key
RB_Node* find(KEY key)
{
RB_Node* index = m_root;
while (index != m_nullNode)
{
if (keykey)
{
index = index->left; // ,
}
else if (key>index->key)
{
index = index->right; // ,
}
else
{
break;
}
}
return index;
}
//-------------------------- ----------------------------------
// , :
/*RB-INSERT(T, z)
1 y ← nil[T] // y x 。
2 x ← root[T] // x ,
3 while x ≠ nil[T]
4 do y ← x
5 if key[z] < key[x] // , ..
6 then x ← left[x]
7 else x ← right[x] // ,x , x NIL 。
8 p[z] ← y //y z 。
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z // 8-13 , z 。
14 left[z] ← nil[T]
15 right[z] ← nil[T] // ,
16 color[z] ← RED // z
17 RB-INSERT-FIXUP(T, z)
*/
// z , ,
// RB-INSERT-FIXUP(T, z) 。
bool Insert(KEY key, U data)
{
RB_Node* insert_point = m_nullNode;
RB_Node* index = m_root;
while (index != m_nullNode)
{
insert_point = index;
if (keykey)
{
index = index->left;
}
else if (key>index->key)
{
index = index->right;
}
else
{
return false;
}
}
RB_Node* insert_node = new RB_Node();
insert_node->key = key;
insert_node->data = data;
insert_node->RB_COLOR = RED;
insert_node->right = m_nullNode;
insert_node->left = m_nullNode;
if (insert_point == m_nullNode) //
{
m_root = insert_node;
m_root->parent = m_nullNode;
m_nullNode->left = m_root;
m_nullNode->right = m_root;
m_nullNode->parent = m_root;
}
else
{
if (key < insert_point->key)
{
insert_point->left = insert_node;
}
else
{
insert_point->right = insert_node;
}
insert_node->parent = insert_point;
}
InsertFixUp(insert_node); // InsertFixUp 。
}
//--------------------- --------------------------------
//3 , ( )。
/*
RB-INSERT-FIXUP(T, z)
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED
5 then color[p[z]] ← BLACK ? Case 1
6 color[y] ← BLACK ? Case 1
7 color[p[p[z]]] ← RED ? Case 1
8 z ← p[p[z]] ? Case 1
9 else if z = right[p[z]]
10 then z ← p[z] ? Case 2
11 LEFT-ROTATE(T, z) ? Case 2
12 color[p[z]] ← BLACK ? Case 3
13 color[p[p[z]]] ← RED ? Case 3
14 RIGHT-ROTATE(T, p[p[z]]) ? Case 3
15 else (same as then clause with "right" and "left" exchanged)
16 color[root[T]] ← BLACK
*/
// , , c++ :
void InsertFixUp(RB_Node* node)
{
while (node->parent->RB_COLOR == RED)
{
if (node->parent == node->parent->parent->left) //
{
RB_Node* uncle = node->parent->parent->right;
if (uncle->RB_COLOR == RED) // 1,z y 。
{
node->parent->RB_COLOR = BLACK;
uncle->RB_COLOR = BLACK;
node->parent->parent->RB_COLOR = RED;
node = node->parent->parent;
}
else if (uncle->RB_COLOR == BLACK) // 2:z y ,。
{
if (node == node->parent->right) // z
{
node = node->parent;
RotateLeft(node);
}
//else // 3:z y , z 。
//{
node->parent->RB_COLOR = BLACK;
node->parent->parent->RB_COLOR = RED;
RotateRight(node->parent->parent);
//}
}
}
else // 1 ,z , 。
//15 else (same as then clause with "right" and "left" exchanged)
{
RB_Node* uncle = node->parent->parent->left;
if (uncle->RB_COLOR == RED)
{
node->parent->RB_COLOR = BLACK;
uncle->RB_COLOR = BLACK;
uncle->parent->RB_COLOR = RED;
node = node->parent->parent;
}
else if (uncle->RB_COLOR == BLACK)
{
if (node == node->parent->left)
{
node = node->parent;
RotateRight(node); // ,
}
//else
//{
node->parent->RB_COLOR = BLACK;
node->parent->parent->RB_COLOR = RED;
RotateLeft(node->parent->parent); // , 。
//}
}
}
}
m_root->RB_COLOR = BLACK;
}
//
bool RotateLeft(RB_Node* node)
{
if (node == m_nullNode || node->right == m_nullNode)
{
return false;//can't rotate
}
RB_Node* lower_right = node->right;
lower_right->parent = node->parent;
node->right = lower_right->left;
if (lower_right->left != m_nullNode)
{
lower_right->left->parent = node;
}
if (node->parent == m_nullNode) //rotate node is root
{
m_root = lower_right;
m_nullNode->left = m_root;
m_nullNode->right = m_root;
//m_nullNode->parent = m_root;
}
else
{
if (node == node->parent->left)
{
node->parent->left = lower_right;
}
else
{
node->parent->right = lower_right;
}
}
node->parent = lower_right;
lower_right->left = node;
}
//
bool RotateRight(RB_Node* node)
{
if (node == m_nullNode || node->left == m_nullNode)
{
return false;//can't rotate
}
RB_Node* lower_left = node->left;
node->left = lower_left->right;
lower_left->parent = node->parent;
if (lower_left->right != m_nullNode)
{
lower_left->right->parent = node;
}
if (node->parent == m_nullNode) //node is root
{
m_root = lower_left;
m_nullNode->left = m_root;
m_nullNode->right = m_root;
//m_nullNode->parent = m_root;
}
else
{
if (node == node->parent->right)
{
node->parent->right = lower_left;
}
else
{
node->parent->left = lower_left;
}
}
node->parent = lower_left;
lower_left->right = node;
}
//-------------------------- ----------------------------------
// , , , :
// : 、 :
//http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx。
bool Delete(KEY key)
{
RB_Node* delete_point = find(key);
if (delete_point == m_nullNode)
{
return false;
}
if (delete_point->left != m_nullNode && delete_point->right != m_nullNode)
{
RB_Node* successor = InOrderSuccessor(delete_point);
delete_point->data = successor->data;
delete_point->key = successor->key;
delete_point = successor;
}
RB_Node* delete_point_child;
if (delete_point->right != m_nullNode)
{
delete_point_child = delete_point->right;
}
else if (delete_point->left != m_nullNode)
{
delete_point_child = delete_point->left;
}
else
{
delete_point_child = m_nullNode;
}
delete_point_child->parent = delete_point->parent;
if (delete_point->parent == m_nullNode)//delete root node
{
m_root = delete_point_child;
m_nullNode->parent = m_root;
m_nullNode->left = m_root;
m_nullNode->right = m_root;
}
else if (delete_point == delete_point->parent->right)
{
delete_point->parent->right = delete_point_child;
}
else
{
delete_point->parent->left = delete_point_child;
}
if (delete_point->RB_COLOR == BLACK && !(delete_point_child == m_nullNode && delete_point_child->parent == m_nullNode))
{
DeleteFixUp(delete_point_child);
}
delete delete_point;
return true;
}
//--------------------- -----------------------------------
// , 23 :
/*
RB-DELETE-FIXUP(T, x)
1 while x ≠ root[T] and color[x] = BLACK
2 do if x = left[p[x]]
3 then w ← right[p[x]]
4 if color[w] = RED
5 then color[w] ← BLACK ? Case 1
6 color[p[x]] ← RED ? Case 1
7 LEFT-ROTATE(T, p[x]) ? Case 1
8 w ← right[p[x]] ? Case 1
9 if color[left[w]] = BLACK and color[right[w]] = BLACK
10 then color[w] ← RED ? Case 2
11 x p[x] ? Case 2
12 else if color[right[w]] = BLACK
13 then color[left[w]] ← BLACK ? Case 3
14 color[w] ← RED ? Case 3
15 RIGHT-ROTATE(T, w) ? Case 3
16 w ← right[p[x]] ? Case 3
17 color[w] ← color[p[x]] ? Case 4
18 color[p[x]] ← BLACK ? Case 4
19 color[right[w]] ← BLACK ? Case 4
20 LEFT-ROTATE(T, p[x]) ? Case 4
21 x ← root[T] ? Case 4
22 else (same as then clause with "right" and "left" exchanged)
23 color[x] ← BLACK
*/
// , , c++ 。
void DeleteFixUp(RB_Node* node)
{
while (node != m_root && node->RB_COLOR == BLACK)
{
if (node == node->parent->left)
{
RB_Node* brother = node->parent->right;
if (brother->RB_COLOR == RED) // 1:x w 。
{
brother->RB_COLOR = BLACK;
node->parent->RB_COLOR = RED;
RotateLeft(node->parent);
}
else // 2:x w ,
{
if (brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK)
// w 。
{
brother->RB_COLOR = RED;
node = node->parent;
}
else if (brother->right->RB_COLOR == BLACK)
// 3:x w ,w (w )。
{
brother->RB_COLOR = RED;
brother->left->RB_COLOR = BLACK;
RotateRight(brother);
}
//else if(brother->right->RB_COLOR == RED)
// 4:x w , w 。
//{
brother->RB_COLOR = node->parent->RB_COLOR;
node->parent->RB_COLOR = BLACK;
brother->right->RB_COLOR = BLACK;
RotateLeft(node->parent);
node = m_root;
//}
}
}
else // 1 ,node 。
//22 else (same as then clause with "right" and "left" exchanged)
// , , , , 。 。
{
RB_Node* brother = node->parent->left;
if (brother->RB_COLOR == RED)
{
brother->RB_COLOR = BLACK;
node->parent->RB_COLOR = RED;
RotateRight(node->parent);
}
else
{
if (brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK)
{
brother->RB_COLOR = RED;
node = node->parent;
}
else if (brother->left->RB_COLOR == BLACK)
{
brother->RB_COLOR = RED;
brother->right->RB_COLOR = BLACK;
RotateLeft(brother);
}
//else if(brother->left->RB_COLOR==RED)
//{
brother->RB_COLOR = node->parent->RB_COLOR;
node->parent->RB_COLOR = BLACK;
brother->left->RB_COLOR = BLACK;
RotateRight(node->parent);
node = m_root;
//}
}
}
}
m_nullNode->parent = m_root; // node ,
node->RB_COLOR = BLACK; // 。
}
//
inline RB_Node* InOrderPredecessor(RB_Node* node)
{
if (node == m_nullNode) //null node has no predecessor
{
return m_nullNode;
}
RB_Node* result = node->left; //get node's left child
while (result != m_nullNode) //try to find node's left subtree's right most node
{
if (result->right != m_nullNode)
{
result = result->right;
}
else
{
break;
}
} //after while loop result==null or result's right child is null
if (result == m_nullNode)
{
RB_Node* index = node->parent;
result = node;
while (index != m_nullNode && result == index->left)
{
result = index;
index = index->parent;
}
result = index; // first right parent or null
}
return result;
}
//
inline RB_Node* InOrderSuccessor(RB_Node* node)
{
if (node == m_nullNode) //null node has no successor
{
return m_nullNode;
}
RB_Node* result = node->right; //get node's right node
while (result != m_nullNode) //try to find node's right subtree's left most node
{
if (result->left != m_nullNode)
{
result = result->left;
}
else
{
break;
}
} //after while loop result==null or result's left child is null
if (result == m_nullNode)
{
RB_Node* index = node->parent;
result = node;
while (index != m_nullNode && result == index->right)
{
result = index;
index = index->parent;
}
result = index; //first parent's left or null
}
return result;
}
//debug
void InOrderTraverse()
{
InOrderTraverse(m_root);
}
void CreateGraph(string filename)
{
//delete
}
void InOrderCreate(ofstream& file, RB_Node* node)
{
//delete
}
void InOrderTraverse(RB_Node* node)
{
if (node == m_nullNode)
{
return;
}
else
{
InOrderTraverse(node->left);
cout << node->key << endl;
InOrderTraverse(node->right);
}
}
~RB_Tree()
{
clear(m_root);
delete m_nullNode;
}
private:
// utility function for destructor to destruct object;
void clear(RB_Node* node)
{
if (node == m_nullNode)
{
return;
}
else
{
clear(node->left);
clear(node->right);
delete node;
}
}
private:
RB_Node *m_nullNode;
RB_Node *m_root;
};
#endif /*_RB_TREE_H_*/
RBTree.cpp//file RBTree.cpp
//written by saturnman,20101008。
//updated by July,20110329。
// , ( , )。
//July、updated,2011.05.06。
#include
#include
#include
#include
#include
#include"RBTree.h" // .h , cpp ,
using namespace std;
int main()
{
RB_Tree tree;
vector v;
for(int i=0;i<20;++i)
{
v.push_back(i);
}
random_shuffle(v.begin(),v.end());
copy(v.begin(),v.end(),ostream_iterator(cout," "));
cout<
運転効果図(まず、各結点を一つずつ挿入してから、すべての結点を削除します):第二部分、プログラムにバグがありますか?
2.1、赤と黒の木は絶対的なバランスが必要ですか?
上記のc++ソースは上記のテスト結果から見ても大丈夫です.しかし、プログラムには隠しバグがあります.次の二つのステップに分けて、このソースコードをテストします.
1、まずRBTree.hの最後に下記のコードを追加します.
public:void PrintTree(){u printNode];prvate:void_prinntNode(RB Node*node){if(node==NULL𞓜node==m nullNode)return;if(node->parent==NULL𞓜node->parent==munulNode){printf==================mmmunulullNode de de de de de de de de de de de de de de de de de de de dededededededeffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffparent:%d/n",node->>data,node->parent->data,}else if(node->parent->Right==node){printf("right:%d,parent:%d/n"node->data,node->parent->>data,"{u printNode->left];
2、RBTree.cppファイルを書き換えます.
//file RBTree.cpp/written by saturnman、200108.udated by Juily、2010339.すべてのヘッダファイルは全部補充されました.今は直接このソースコードをコピーして確認できます.Juily、udated、2010.5.06.include((zhi include)//(zhi include)//(zhi include)///(zhi include)「RBTree.h」/もし.hファイルとcppファイルを一つのファイルに入れたら、この文はusing namespace stdを削除します.int main(){RB Treeeetree;tree.Insert(12,12);tree.Insert(1,1);tree.Insert(9,9);tree.Insert(2,2);tree.Insert(0,0);tree.Insert(11,11);tree.Insert.Insert(7,7);treee.Insert(((7,7))))))))+treee.Insert+treee.Intreee.Insert(((((((((((((((())))))))))))))))))))))))))))))k(i);random_shuffle(v.begin()、v.end();copy(v.begin()、v.end()、ostreamuuiterator(cout);cout<>
後にテストした結果、間違いがありました.つまり、次のノードに順番に挿入します.12、1、9、0、2、11、7の後、赤と黒の木は次のようになります.
ルートノード9を削除し、上記のプログラムを経て運転した結果、以下のようになります.
つまり上記の運転結果は、対応するマホガニーの状態は以下の通りです.
はい、ご覧のように、上記のプログラムはルートノード9を削除した後、正しい赤と黒の木の状態はルートノード9の代わりに7であるべきです.7は新しいルートノードになり、ノード7は黒であり、上記の結果は完全に間違っています.赤と黒の木はすでに完全にバランスが取れていません.これでやっと発見されました.
説明:このプログラムのバグはネットユーザーの鑫に指摘されました.また、ネット上の多くのプログラムには、この問題が存在していることが分かりました.http://sd.csdn.net/a/20110506/297285.html赤い木のflashのデモンストレーションバージョンにもこのような問題があります.
残念ですが、テストを重ねました.赤い木のflashバージョンに問題があります.:http://www.cs.usfca.edu/~galles/visualzation/flash.このシーケンスを順次に挿入すると、15,1,9,2,0,12,16,7,11,13,17,14,14,000本のノード9を削除し、重大なエラーが出てきます.上のバージョンは簡単なステップで7を9の代わりにルートノードにして、7つのノードを黒にします.ツリーはその後の調整がなく、完全にバランスが取れません.問題が出たら、この赤い木の間違いflashバージョンがもっと多くの人を誤解させないようにしたいです.また、問題は友達の鑫が出したものです.この問題を覚えておきます.解決すれば、ブログに発表します.その後:鑫はavlツリーにも問題があります.July、構造のアルゴリズムの道博主です.2010.5.07.
しかし事実は、果たしてそうなのか?以下の2.1節の修正を見てください.
2.1、赤と黒の木は厳格なバランスを要求しない
修正:このプログラムには何の問題もありません.前に意識していなかったために、上記のような錯覚を起こしました.つまり、赤と黒の木は厳密な意味ではなく、二叉で木を探しています.それは自分の5つの性質を満足すればいいです.厳密なバランスは要求されません.だから、上の例では、12、1、9、0、2、11、7、根の結点9を削除してください.同じように、赤と黒の5つの性質に違反していません.だから、私は凡庸な人です.sorry.
それともこの言葉ですか?何か問題があったら、誰かに指摘してください.
第三部分、読者フィードバック
RB_Tree挿入削除操作についての議論
July:
すみません、RB Treeの完全な実現コードについては、すでにあなたのブログに書いてありますが、コードの中に修正が必要なところがあると思います.
起因
私はこのごろRB Treeを勉強しています.RB Treeの性質を無視しました.(3):葉の結点は全部黒で、RB Treeの操作について何日間か悩んでいます.私はまだ意識していない時に、偶然あなたのブログを見て、答えをもらいたいです.そして、その中には議論すべきところがあります.
エラー
下図は修正関数InsertFixUpを挿入する部分のスクリーンショットです.
あなたの記事の住所:http://blog.csdn.net/v_july_v/article/details/6285620
図 1
「アルゴリズム導論」で述べたように、InsertFixUpでは、whileサイクルごとに3つの状況に直面します.
case 1:zのおじさんyは赤いです.
case 2:zのおじさんyは黒で、zは右の子供です.
case 3:zのおじさんyは黒で、zは左の子供です.
なお、case 2はcase 3に落下しているので、この2つのケースは互いに反発するものではありません.あなたのコードの中で、case 2とcase 3をそれぞれifとelseの中に置いて、互いに独立することになります.これは違います.
修正
したがって、図1において「①」のelseは追加できませんので、削除します.
残念なことに、あなたのRB_Treeの削除修正操作はDeleteFixUpにも同様のエラーが発生したと思います.DeleteFixUpに対して処理された4つのケースも同様に反発し合うものではなく、あなたはif...else if...case 2,3,4を全部独立させます.
以上は拙者の愚見です.間違ったところがあれば、また検討してください.
楊 スーパー
CSDN ID:crischaos
201.10.06
考証:楊兄の手紙指導に感謝します.アルゴリズム導論書のもとの挿入状況の修復コードから見て:
//--------------------- --------------------------------
//3 , ( )。
/*
RB-INSERT-FIXUP(T, z)
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED
5 then color[p[z]] ← BLACK ? Case 1
6 color[y] ← BLACK ? Case 1
7 color[p[p[z]]] ← RED ? Case 1
8 z ← p[p[z]] ? Case 1
9 else if z = right[p[z]]
10 then z ← p[z] ? Case 2
11 LEFT-ROTATE(T, z) ? Case 2
12 color[p[z]] ← BLACK ? Case 3
13 color[p[p[z]]] ← RED ? Case 3
14 RIGHT-ROTATE(T, p[p[z]]) ? Case 3
15 else (same as then clause with "right" and "left" exchanged)
16 color[root[T]] ← BLACK
*/
// , , c++ : ....
確かに楊兄が言ったように、当然のことです.(その後の削除状況の修復も含む).後日、統一的に修正します.再度ありがとうございます.July、201.10.06更新.マホガニーシリーズの最初の5つの記事:
4、
ステップ1図1コード、R-B Tree
1、
赤黒い木を徹底的に理解するように教えます.
5、
赤と黒のツリーを挿入して、リンクを削除する全行程のデモンストレーション.
3、
赤と黒の木のcソースコードの実現と分析
2、
マホガニーのアルゴリズムの実現と分析
6、お礼:
http://saturnman.blog.163.com/.
終わります.