アルゴリズムとデータ構造勉強会 第６回 スレッド木

Presentation on theme: "アルゴリズムとデータ構造勉強会 第６回 スレッド木"— Presentation transcript:

1 アルゴリズムとデータ構造勉強会 第６回 スレッド木
アルゴリズムとデータ構造勉強会 第６回　スレッド木

2 スレッド木とは スレッドを追加することによって、木の 　　節点を異なった順番で容易にたどれる 　　木である。

3 スレッド木の基本的性質 １．スレッドを作成するには、通りがけ順で1つ前に位置する先行節点(predecessor)と、1つ後ろに位置する後続節点(successor)のポインタを、未使用の子ポインタに格納 する。 ２．スレッドは対称で、左の子スレッドは先行節点を指し、 　　右の子スレッドは後続節点を指しており、この種の木は 　　対称なスレッド木と呼ばれる。

4 ３．各節点には２つの子ポインタがあるので、木の中にN個の節点がある場合は、２N個のリンクとスレッドが存在
　　しなければならない。これらのトラバースアルゴリズムは 　　各リンクとスレッドに１回ずつ立ち寄るので、その計算量 　　はO（２N）＝O(N) ４．木の最初の節点と最後の節点の添字を常に追跡する 　　ようにすれば、アルゴリズムの実行時間はすこし速く 　　なる。

5 C A E G B D F H 図１　スレッドを点線で示した対称なスレッド木

6 先行節点を見つけるプログラム PThreadedNode *Predecessor(PThreadedNode *node)
{ PThreadedNode *child if (node->LeftChild == NULL){ return NULL; }else if(node->HasLeftChild == TRUE){ child = node->LeftChild; while (child->HasLeftChild) { child = child->RightChild; }return child; }else{return node -> LeftChild;}; };

7 木の最初と最後の節点を見つける関数 PthreadedNode *FirstNode(); { Result = Root;
while ((Result->LeftChild)!=NULL) {Result = Result->LeftChild;} }; PThreadedNode *LastName(); while ((Result->RightChild)!=NULL) {Result = Result->RightChild;}

8 節点を昇順と降順に表示する手続き Void ReverseInorder(); Void Inorder(); { {
struct PThreadedNode node; node = LastNode; while (node != NULL) VisitNode (node->Value); node = Predecessor(node); } }; Void Inorder(); { struct PThreadedNode node; node = FirstNode; while (node != NULL) VisitNode (node->Value); node = Sucessor(node); } };

9 スレッド木の管理 スレッド木を管理するには、木のスレッドを 　　適切に保ちつつ、木に節点を追加したり、 　　木から節点を削除できなければならない。

10 C A E G B D F H X 図2　節点Xを追加されたスレッド木

11 左の子として挿入する手続き Void AddLeftChild (PThreadedNode *parent, PThreadedNode *Child); { child->LeftChild = parent ->LeftChild; child->HasLeftChild = FALSE; parent->LeftChild = child; parent->HasLeftChild = TRUE; child->RightChild = parent; child->HasRightChild = FALSE; if ((child->LeftChild) == NULL) {FirstNode = child;} };

12 左の子に新しい節点を追加する手続き 木の最初の節点と最後の節点の添字を追跡している場合は、この場所をチェックして、新しく追加された節点が木の最初の節点になっていないかどうか調べる必要がある。新しい節点の先行節点のスレッドがNULL値を持つ場合、そこが新たに最初の節点になる。 *　右の子として挿入する場合も同様である。

13 スレッド木から節点を削除 スレッド木から節点を削除するには、その前に、 その子孫を削除する必要がある。節点に子が
　　その子孫を削除する必要がある。節点に子が 　　なくなれば、その節点は簡単に削除できる。

14 C A E G B D H X 　　図３　節点Fを削除したスレッド木

15 左の子を削除する手続き void RemoveLeftChild (PThreadedNode *parent); {
struct PThreadedNode target; target = parent->LeftChild; parent->LeftChild = target->LeftChild; };

16 実習 図１に示すスレッド木をC/C++プログラムで作って、そのあと、そのスレッド木を図３に示すスレッド木にかえてください。