OSDN -- Develop and Download Open Source Software
  • R/O
  • SSH
  • HTTPS

iris-fmw: Commit


Commit MetaInfo

Revision48 (tree)
Time2010-10-24 21:39:15
Authorshirayanagi

Log Message

ツリー修正

Change Summary

Incremental Difference

--- trunk/framework/sample/Windows/test/VS2008/container_test/test_avltree.cpp (revision 47)
+++ trunk/framework/sample/Windows/test/VS2008/container_test/test_avltree.cpp (revision 48)
@@ -27,20 +27,20 @@
2727
2828 #define LOOP_NUM 100
2929
30-NO_TEST(FndAVLTreeTest, Func)
30+TEST(FndAVLTreeTest, Func)
3131 {
3232 Tree tree;
3333 int v[10] =
3434 {
35- 1,
36- 2,
37- 5,
3835 9,
36+ 6,
3937 4,
40- 6,
41- 0,
4238 8,
4339 7,
40+ 0,
41+ 1,
42+ 2,
43+ 5,
4444 3
4545 };
4646 Node node[10];
@@ -76,7 +76,7 @@
7676 tree.clear();
7777 }
7878
79-NO_TEST(FndAVLTreeTest, RandomTest)
79+TEST(FndAVLTreeTest, RandomTest)
8080 {
8181 Tree tree;
8282
--- trunk/framework/src/fnd/container/FndAVLTree.h (revision 47)
+++ trunk/framework/src/fnd/container/FndAVLTree.h (revision 48)
@@ -201,8 +201,8 @@
201201 if( !is_null_node(last) )
202202 {
203203 // 切り離し
204- if( last->m_pLeft == target ) last->m_pLeft = nullptr;
205- else last->m_pRight = nullptr;
204+ if( last->m_pLeft == target ) last->m_pLeft = node;
205+ else last->m_pRight = node;
206206 }
207207 swap = node;
208208 }
@@ -323,6 +323,7 @@
323323
324324 #ifdef _IRIS_DEBUGTEST_ENABLE
325325 check_tree_struct(this->m_root);
326+ IRIS_ASSERT( (cnt-1) == count() );
326327 #endif
327328 this->m_root = rotate_tree_sub(last, pos, swap);
328329 target->unlink();
@@ -335,157 +336,8 @@
335336 }
336337
337338 private:
338- /**
339- * @brief 右に１回転する
340- * @param [in] key = 追加か削除された値
341- * @param [in] mode = 追加か削除を表す値
342- * @param [in] parent = 回転後の親ノード
343- * @param [in] left = 回転後の親の左ノード
344- * @param [in] right = 回転後の親の右ノード
345- * @return 回転後のルートノード
346- */
347- value_ptr rotate_avl_right1(value_ptr key, s32 mode, value_ptr parent, value_ptr left, value_ptr right)
348- {
349- value_ptr p = parent;
350- value_ptr l = left;
351- value_ptr r = right;
352- value_ptr rl = static_cast<value_ptr>(parent->m_pRight);
353339
354- p->m_pParent = right->m_pParent;
355- p->m_pLeft = l;
356- p->m_pRight = r;
357- l->m_pParent = p;
358- r->m_pParent = p;
359- r->m_pLeft = rl;
360-
361- if(mode == node_type::MODE_INSERT)
362- {
363- p->m_Balance = node_type::EVEN;
364- l->m_Balance = node_type::EVEN;
365- r->m_Balance = node_type::EVEN;
366-
367- if(rl != nullptr)
368- {
369- rl->m_pParent = r;
370- if(*key < *l) l->m_Balance = node_type::LEFT;
371- else l->m_Balance = node_type::RIGHT;
372- }
373- }
374- else
375- {
376- if(p->m_Balance == node_type::EVEN) p->m_Balance = node_type::RIGHT;
377- else p->m_Balance = node_type::EVEN;
378- r->m_Balance = node_type::EVEN;
379-
380- if(rl != nullptr)
381- {
382- rl->m_pParent = r;
383- if(r->m_pRight == nullptr)
384- {
385- r->m_Balance = node_type::LEFT;
386- p->m_Balance = node_type::RIGHT;
387- }
388- else
389- {
390- if(p->m_Balance == node_type::EVEN) r->m_Balance = node_type::EVEN;
391- else r->m_Balance = node_type::LEFT;
392- }
393- }
394- }
395-
396- if(p->m_pParent == nullptr)
397- {
398- this->m_root = p;
399- }
400- else
401- {
402- if(p->m_pParent->m_pLeft == right) p->m_pParent->m_pLeft = p;
403- else p->m_pParent->m_pRight = p;
404- }
405- return this->m_root;
406- }
407-
408340 /**
409- * @brief 左に１回転する
410- * @param [in] key = 追加か削除された値
411- * @param [in] mode = 追加か削除を表す値
412- * @param [in] parent = 回転後の親ノード
413- * @param [in] left = 回転後の親の左ノード
414- * @param [in] right = 回転後の親の右ノード
415- * @return 回転後のルートノード
416- */
417- value_ptr rotate_avl_left1(value_ptr key, s32 mode, value_ptr parent, value_ptr left, value_ptr right)
418- {
419- value_ptr p = parent;
420- value_ptr l = left;
421- value_ptr r = right;
422- value_ptr lr = static_cast<value_ptr>(parent->m_pLeft);
423- IRIS_ASSERT( p == l->m_pRight );
424- IRIS_ASSERT( r == p->m_pRight );
425-
426- p->m_pParent = l->m_pParent;
427- p->m_pLeft = l;
428- p->m_pRight = r;
429- l->m_pParent = p;
430- l->m_pRight = lr;
431-
432- if(mode == node_type::MODE_INSERT)
433- {
434- p->m_Balance = node_type::EVEN;
435- l->m_Balance = node_type::EVEN;
436-
437- if(lr != nullptr)
438- {
439- lr->m_pParent = l;
440- if( is_null_node(l->m_pLeft) ) l->m_Balance = node_type::RIGHT;
441- else
442- {
443- if( l->m_pLeft->m_Balance == node_type::EVEN )
444- {
445- if( lr->m_Balance != node_type::EVEN ) l->m_Balance = node_type::LEFT;
446- }
447- else
448- {
449- if( lr->m_Balance == node_type::EVEN ) l->m_Balance = node_type::RIGHT;
450- }
451- }
452- }
453- }
454- else
455- {
456- if(p->m_Balance == node_type::EVEN) p->m_Balance = node_type::LEFT;
457- else p->m_Balance = node_type::EVEN;
458- l->m_Balance = node_type::EVEN;
459-
460- if(lr != nullptr)
461- {
462- lr->m_pParent = l;
463- if(l->m_pRight == nullptr)
464- {
465- l->m_Balance = node_type::RIGHT;
466- p->m_Balance = node_type::LEFT;
467- }
468- else
469- {
470- if(p->m_Balance == node_type::EVEN) l->m_Balance = node_type::EVEN;
471- else l->m_Balance = node_type::RIGHT;
472- }
473- }
474- }
475-
476- if(p->m_pParent == nullptr)
477- {
478- this->m_root = p;
479- }
480- else
481- {
482- if(p->m_pParent->m_pLeft == l) p->m_pParent->m_pLeft = p;
483- else p->m_pParent->m_pRight = p;
484- }
485- return this->m_root;
486- }
487-
488- /**
489341 * @brief 右に２回転する
490342 * @param [in] mode = 追加か削除を表す値
491343 * @param [in] parent = 回転後の親ノード
@@ -615,18 +467,10 @@
615467 // 追加されたほうの子ノードが左に傾いている場合は右に 1 回転
616468 if(node->m_pLeft->m_Balance == node_type::LEFT)
617469 {
618-#ifdef _IRIS_DEBUGTEST_ENABLE
619- node_ptr _p = node->m_pLeft;
620- node_ptr _l = node->m_pLeft->m_pLeft;
621- node_ptr _r = node;
622-#endif
623- this->m_root = rotate_avl_right1(key, mode, static_cast<value_ptr>(node->m_pLeft), static_cast<value_ptr>(node->m_pLeft->m_pLeft), node);
624-#ifdef _IRIS_DEBUGTEST_ENABLE
625- IRIS_ASSERT( _p->m_pLeft == _l );
626- IRIS_ASSERT( _p->m_pRight == _r );
627- IRIS_ASSERT( _l->m_pParent == _p );
628- IRIS_ASSERT( _r->m_pParent == _p );
629-#endif
470+ value_ptr p = static_cast<value_ptr>(node->m_pLeft);
471+ this->m_root = rotate_right1(p);
472+ p->m_Balance = node_type::EVEN;
473+ p->m_pRight->m_Balance = node_type::EVEN;
630474 }
631475 // 追加されたほうの子ノードが右に傾いている場合は右に 2 回転
632476 else if(node->m_pLeft->m_Balance == node_type::RIGHT)
@@ -659,31 +503,9 @@
659503 {
660504 value_ptr p = static_cast<value_ptr>(node->m_pRight);
661505 value_ptr l = node;
662- value_ptr lr = static_cast<value_ptr>(p->m_pLeft);
663- this->m_root = rotate_left1(static_cast<value_ptr>(node->m_pRight));
506+ this->m_root = rotate_left1(p);
664507 p->m_Balance = node_type::EVEN;
665- l->m_Balance = node_type::EVEN;
666- if( is_null_node(l->m_pLeft) )
667- {
668- if( !is_null_node(lr) ) l->m_Balance = node_type::RIGHT;
669- }
670- else
671- {
672- if( is_null_node(lr) ) l->m_Balance = node_type::LEFT;
673- else
674- {
675- if( l->m_pLeft->m_Balance == node_type::EVEN )
676- {
677- if( lr->m_Balance != node_type::EVEN )
678- l->m_Balance = l->is_leaf() ? node_type::RIGHT : node_type::LEFT;
679- }
680- else
681- {
682- if( lr->m_Balance == node_type::EVEN )
683- l->m_Balance = lr->is_leaf() ? node_type::LEFT : node_type::RIGHT;
684- }
685- }
686- }
508+ _balance(l);
687509 }
688510 // 追加されたほうの子ノードが左に傾いている場合は左に 2 回転
689511 else if(node->m_pRight->m_Balance == node_type::LEFT)
@@ -745,7 +567,7 @@
745567 {
746568 static const s32 mode = node_type::MODE_DELETE;
747569 if(this->m_root == nullptr) return nullptr;
748- node_ptr sub = key;
570+ value_ptr sub = key;
749571 // node が nullptr の場合はツリーがルートのみなので何も行わない
750572 if(node == nullptr) return this->m_root;
751573
@@ -756,23 +578,36 @@
756578 if(node->m_Balance == node_type::LEFT)
757579 {
758580 // 右側のノードが削除された場合
759- if(node != swapkey && *node < *key)
581+ if( *node < *sub )
760582 {
761583 // 左側のノードが右に傾いている場合は右に 2 回転
762584 if(node->m_pLeft->m_Balance == node_type::RIGHT)
763585 {
764- this->m_root = rotate_avl_right2(mode, static_cast<value_ptr>(node->m_pLeft->m_pRight), static_cast<value_ptr>(node->m_pLeft), node);
586+ value_ptr p = static_cast<value_ptr>(node->m_pLeft->m_pRight);
587+ this->m_root = rotate_avl_right2(mode, p, static_cast<value_ptr>(node->m_pLeft), node);
765588 if(node->m_pParent->m_Balance != node_type::EVEN)
766589 break;
767- node = static_cast<value_ptr>(node->m_pParent);
590+ node = p;
768591 }
769592 // 左側のノードが右に傾いていない場合は右に 1 回転
770593 else
771594 {
772- this->m_root = rotate_avl_right1(key, mode, static_cast<value_ptr>(node->m_pLeft), static_cast<value_ptr>(node->m_pLeft->m_pLeft), node);
595+ value_ptr p = static_cast<value_ptr>(node->m_pLeft);
596+ this->m_root = rotate_right1(p);
597+ if(p->m_Balance == node_type::EVEN)
598+ {
599+ p->m_Balance = node_type::RIGHT;
600+ if( is_null_node(p->m_pRight->m_pLeft) )
601+ p->m_pRight->m_Balance = node_type::EVEN;
602+ }
603+ else
604+ {
605+ p->m_Balance = node_type::EVEN;
606+ p->m_pRight->m_Balance = node_type::EVEN;
607+ }
773608 if(node->m_pParent->m_Balance != node_type::EVEN)
774609 break;
775- node = static_cast<value_ptr>(node->m_pParent);
610+ node = p;
776611 }
777612 }
778613 // 左側のノードが削除された場合
@@ -785,23 +620,61 @@
785620 else if(node->m_Balance == node_type::RIGHT)
786621 {
787622 // 左側のノードが削除された場合
788- if(node->m_pLeft == sub)
623+ if( *sub < *node )
789624 {
790625 // 右側のノードが左に傾いている場合は左に 2 回転
791626 if(node->m_pRight->m_Balance == node_type::LEFT)
792627 {
793- this->m_root = rotate_avl_left2(mode, static_cast<value_ptr>(node->m_pRight->m_pLeft), node, static_cast<value_ptr>(node->m_pRight));
794- if(node->m_pParent->m_Balance != node_type::EVEN)
628+ value_ptr p = static_cast<value_ptr>(node->m_pRight->m_pLeft);
629+ this->m_root = rotate_left2(p);
630+ if( p->m_Balance == node_type::LEFT )
631+ {
632+ p->m_pLeft->m_Balance = node_type::LEFT;
633+ p->m_Balance = node_type::EVEN;
634+ }
635+ else if( p->m_Balance == node_type::RIGHT )
636+ {
637+ p->m_pRight->m_Balance = node_type::EVEN;
638+ p->m_pLeft->m_Balance = node_type::LEFT;
639+ p->m_Balance = node_type::EVEN;
640+ }
641+ else
642+ {
643+ p->m_pRight->m_Balance = node_type::EVEN;
644+ if( is_null_node(p->m_pLeft->m_pRight) )
645+ {
646+ p->m_pLeft->m_Balance = node_type::EVEN;
647+ p->m_pLeft->m_Balance = node_type::EVEN;
648+ }
649+ else
650+ {
651+ p->m_Balance = node_type::RIGHT;
652+ p->m_pLeft->m_Balance = node_type::RIGHT;
653+ }
654+ }
655+ if(p->m_Balance != node_type::EVEN)
795656 break;
796- node = static_cast<value_ptr>(node->m_pParent);
657+ node = p;
797658 }
798659 // 右側のノードが左に傾いていない場合は左に 1 回転
799660 else
800661 {
801- this->m_root = rotate_avl_left1(key, mode, static_cast<value_ptr>(node->m_pRight), node, static_cast<value_ptr>(node->m_pRight->m_pRight));
662+ value_ptr p = static_cast<value_ptr>(node->m_pRight);
663+ this->m_root = rotate_left1(p);
664+ if(p->m_Balance == node_type::EVEN)
665+ {
666+ p->m_Balance = node_type::LEFT;
667+ if( is_null_node(p->m_pLeft->m_pRight) )
668+ p->m_pLeft->m_Balance = node_type::EVEN;
669+ }
670+ else
671+ {
672+ p->m_Balance = node_type::EVEN;
673+ p->m_pLeft->m_Balance = node_type::EVEN;
674+ }
802675 if(node->m_pParent->m_Balance != node_type::EVEN)
803676 break;
804- node = static_cast<value_ptr>(node->m_pParent);
677+ node = p;
805678 }
806679 }
807680 // 右側のノードが削除された場合
@@ -813,13 +686,8 @@
813686 // 親ノードがバランスが取れている
814687 else
815688 {
816- // 削除されたノードと交換されたノードの場合
817- if(node == swapkey)
818- {
819- node->m_Balance = node_type::RIGHT;
820- }
821689 // 左側のノードが削除された場合
822- else if(*key < *node)
690+ if( *sub < *node)
823691 {
824692 // 削除されたほうの子ノードのバランスが取れている場合
825693 IRIS_ASSERT(node->m_pLeft == nullptr || node->m_pLeft->m_Balance == node_type::EVEN);
@@ -834,11 +702,25 @@
834702 }
835703 break;
836704 }
705+ sub = node;
837706 } while((node = static_cast<value_ptr>(node->m_pParent)) != nullptr);
838707
839708 return this->m_root;
840709 }
841710
711+ /**
712+ * @brief ノードのバランスを再セット
713+ */
714+ void _balance(node_ptr ptr)
715+ {
716+ IRIS_ASSERT( ptr != nullptr );
717+ int lh = height(ptr->m_pLeft);
718+ int rh = height(ptr->m_pRight);
719+ if( lh > rh ) ptr->m_Balance = node_type::LEFT;
720+ else if( lh < rh ) ptr->m_Balance = node_type::RIGHT;
721+ else ptr->m_Balance = node_type::EVEN;
722+ }
723+
842724 #ifndef _IRIS_DEBUG
843725 public:
844726 void print(void) const {}
@@ -880,12 +762,12 @@
880762
881763 if(next->m_pLeft != nullptr)
882764 {
883- indent++;
765+ ++indent;
884766 next = static_cast<value_ptr>(next->m_pLeft);
885767 }
886768 else if(next->m_pRight != nullptr)
887769 {
888- indent++;
770+ ++indent;
889771 next = static_cast<value_ptr>(next->m_pRight);
890772 }
891773 else
@@ -895,7 +777,7 @@
895777 {
896778 parent = static_cast<value_ptr>(next->m_pParent);
897779 if(parent == nullptr) return;
898- indent--;
780+ --indent;
899781 if(parent->m_pRight == next)
900782 {
901783 next = parent;
@@ -906,7 +788,7 @@
906788 if(next->m_pRight != nullptr)
907789 {
908790 next = static_cast<value_ptr>(next->m_pRight);
909- indent++;
791+ ++indent;
910792 break;
911793 }
912794 }
@@ -965,22 +847,20 @@
965847 IRIS_ASSERT( node->m_Balance == node_type::EVEN );
966848 if( node->m_pLeft != nullptr && node->m_pRight != nullptr )
967849 {
968- if( node->m_pLeft->m_pLeft == nullptr && node->m_pLeft->m_pRight == nullptr )
850+ int lh = height(node->m_pLeft);
851+ int rh = height(node->m_pRight);
852+ if( lh < rh )
969853 {
970- if( node->m_pRight->m_pLeft == nullptr && node->m_pRight->m_pRight == nullptr )
971- {
972- IRIS_ASSERT( node->m_Balance == node_type::EVEN );
973- }
974- else
975- {
976- IRIS_ASSERT( node->m_Balance == node_type::RIGHT );
977- }
854+ IRIS_ASSERT( rh == lh+1 );
855+ IRIS_ASSERT( node->m_Balance == node_type::RIGHT );
978856 }
979- else
857+ else if( lh > rh )
980858 {
981- if( node->m_pRight->m_pLeft == nullptr && node->m_pRight->m_pRight == nullptr )
982- IRIS_ASSERT( node->m_Balance == node_type::LEFT );
859+ IRIS_ASSERT( lh == rh+1 );
860+ IRIS_ASSERT( node->m_Balance == node_type::LEFT );
983861 }
862+ else
863+ IRIS_ASSERT( node->m_Balance == node_type::EVEN );
984864 }
985865
986866 {
--- trunk/framework/src/fnd/container/FndRedBlackTree.h (revision 47)
+++ trunk/framework/src/fnd/container/FndRedBlackTree.h (revision 48)
@@ -366,6 +366,7 @@
366366 }
367367 else
368368 {
369+ IRIS_ASSERT( parent->m_pRight == swapkey );
369370 bro = static_cast<value_ptr>(parent->m_pLeft);
370371 if( bro->m_Color == node_type::RED )
371372 {
--- trunk/framework/src/fnd/container/FndBinarySearchTree.h (revision 47)
+++ trunk/framework/src/fnd/container/FndBinarySearchTree.h (revision 48)
@@ -445,6 +445,10 @@
445445 */
446446 s32 count(void) const { return count(m_root); }
447447
448+ /**
449+ * @brief ノードの高さを取得
450+ */
451+ s32 height(void) const { return height(m_root); }
448452 protected:
449453
450454 /**
@@ -863,6 +867,17 @@
863867 n += count(ptr->m_pRight);
864868 return n;
865869 }
870+
871+ /**
872+ * @brief 指定ノード以下のノードの高さを取得
873+ */
874+ s32 height(node_ptr ptr) const
875+ {
876+ if( is_null_node(ptr) ) return 0;
877+ s32 l = height(ptr->m_pLeft);
878+ s32 r = height(ptr->m_pRight);
879+ return 1 + ((l > r) ? l : r);
880+ }
866881 public:
867882 /// nullptrノード
868883 static node_ptr null_node(void)
Show on old repository browser