Алгоритмы и структуры данных осень 2013 лекция 5

  • Published on
    17-Dec-2014

  • View
    435

  • Download
    3

Embed Size (px)

DESCRIPTION

 

Transcript

  • 1. 5. . 1. . .

2. 1. () , . () , . . , . , . 2 ( ). () . 2 3. 3. , . . 4. () . , . y x ( x y), x y . 3 4. 5. ( ) , . . , , . , .4 5. 5 6. . Queue ICPC Challenge 2012 Tournament (queue.acm.org):6 7. . .7 8. .8 9. .9 10. 1. ( ) . . . 2. , N , N 1 . . . . N = 1. , . . N + 1 . . 1 . N , N 1 . , N , ... 10 11. 6. () , 3. 6. () ( ) , .11 12. 7. N- , N + 1. 7. N- ( ) , N .12 13. 8. . , . .13 14. 9. N- N . , , . .14 15. // int. struct CBinaryNode { int Data; CBinaryNode* Left; // NULL, . CBinaryNode* Right; // NULL, . CBinaryNode* Parent; // NULL, . };// . struct CTreeNode { int Data; CTreeNode* Next; // NULL, . CTreeNode* First; // NULL, . CTreeNode* Parent; // NULL, . }; 15 16. 10. - - . 11. (DFS) , : * () - , * , * . DFS Depth First Search. 16 17. ( ). , . : E, D, B, A, C, H, F, G. ( ). , . : A, C, B, D, G, F, H, E. 17 18. ( ). , . : A, B, C, D, E, F, G, H.18 19. // . void TraverseDFS( CBinaryNode* node ) { if( node == NULL ) return; TraverseDFS( node->Left ); TraverseDFS( node->Right ); visit( node ); };19 20. . . . . . : // . int Count( CBinaryNode* node ) { if( node == 0 ) return 0; return Count( node->Left ) + Count( node->Right ) + 1; };20 21. , . .21 22. 12. (BFS) (), . BFS Breadth First Search. , , . : * , , * () , * . .: E, D, H, B, F, A, C, G. 22 23. 23 24. // . void TraverseBFS( CBinaryNode* root ) { queue q; q.put( root ); while( !q.empty() ) { CBinaryNode* node = q.pop(); visit( node ); if( node->Left != NULL ) q.push( node->Left ); if( node->Right != NULL ) q.push( node->Right ); } };24 25. 13. (binary search tree, BST) , , : X X X. :25 26. : 1. .2. , . 3. . 4. . 5. .26 27. . : X K.: , K , , . : , , , . K X. K == X, . K > X, K X. K < X, K X. : O(h), h . 27 28. // . . NULL, // . CNode* Find( CNode* node, int value ) { if( node == NULL ) return NULL; if( node->Data == value ) return node; if( node->Data > value ) return Find( node->Left, value ); else return Find( node->Right, value ); };28 29. . : X.: . : , . : O(h), h .29 30. // . CNode* FindMinimum( CNode* node ) { assert( node != NULL ); while( node->Left != NULL ) node = node->Left; return node; };30 31. . : X K.: K ( ). : , . K X. K < X, K X. K X. : O(h), h . 31 32. // . typedef CNode* PCNode; // . parent. void Insert( PCNode& node, int value ) { if( node == NULL ) { node = new CNode( value ); return; } if( node->Data > value ) Insert( node->Left, value ); else Insert( node->Right, value ); };32 33. . : X K.: K ( ). : , . K X. K < X, K . K > X, K . K == X, :1. . X, .2. . X, .3. . 33 34. . 3. . , . X, Y . Y , Y X . Y. Z Y. Z, Z. Z Z Z. : O(h), h .34 35. // . typedef CNode* PCNode; // . false, . bool Delete( PCNode& node, int value ) { if( node == NULL ) return false; if( node->Data == value ) { // , . DeleteNode( node ); return true; } return Delete( node->Data > value ? node->Left : node->Right, value ); };35 36. // . typedef CNode* PCNode; // . void DeleteNode( PCNode& node ) { if( node->Left == NULL ) { // . CNode* right = node->Right; // , NULL. delete node; node = right; } else if( node->Right == NULL ) { // . CNode* left = node->Left; // . delete node; node = left; } else { // . // . CNode* right = node->Right; if( right->Left == NULL ) { // . node->Data = right->Data; node->Right = right->Right; delete right; } else { // . CNode* minParent = right; for( ; minParent->Left->Left != NULL; minParent = minParent->Left ); CNode* min = minParent->Left; node->Data = min->Data; minParent->Left = min->Right; // NULL. delete min; } } } 36 37. . -, - , , -.37 38. - 38 39. - 39 40. - 40 41. - 41 42. - 1. , , . 2. . 3. "" . - .42 43. ? !

Recommended

View more >