Bai7 timkiemnhiphan
- 1. C畉u tr炭c d畛 li畛u v thu畉t gi畉i T狸m ki畉m
- 2. T狸m ki畉m T狸m ki畉m tu畉n t畛 Th畛i gian t畛i nh畉t l n Ch炭ng t担i c坦 畛 ph畛c t畉p O(n) 畛ng d畛ng cho m畉ng (kh担ng s畉p x畉p) v danh s叩ch li棚n k畉t T狸m ki畉m nh畛 ph但n 畛ng d畛ng cho d達y 達 s畉p x畉p Th畛i gian th畛c hi畛n thu畉t to叩n log2 n 畛 ph畛c t畉p t鱈nh to叩n O(log n)
- 3. T狸m ki畉m T狸m ki畉m nh畛 ph但n T畉o ra m畛t d達y 達 s畉p x畉p B畛 xung vo danh s叩ch li棚n k畉t (AddToCollection) B畛 xung gi叩 tr畛 vo c叩c v畛 tr鱈 炭ng T狸m v畛 tr鱈 c1 log2 n Duy畛t xu畛ng c2 n T畛ng qu叩t c1 log2 n + c2 n Ho畉c c2 n M畛i ho畉t 畛ng g畉n v畛i d達y 達 s畉p x畉p O(n) ? Ch炭ng t担i c坦 th畛 duy tr狸 m畛t d達y 達 s畉p x畉p v畛i c叩c ho畉t 畛ng ch竪n d畉 h董n? Dominant term
- 4. C但y C但y nh畛 ph但n Bao g畛m Node C叩c c但y con tr叩i v c但y con ph畉i C畉 hai c但y con 畛u l c但y nh畛 ph但n
- 5. C但y C但y nh畛 ph但n Bao g畛m Node C叩c c但y con tr叩i v con ph畉i C畉 hai 畛u l c但y nh畛 ph但n Ch炭 箪 畛nh ngh挑a 畛 qui! M畛i c但y con L m畛t c但y Nh畛 ph但n
- 6. C但y Th畛 t畛c C畉u tr炭c d畛 li畛u struct t_node { void *item; struct t_node *left; struct t_node *right; }; typedef struct t_node *Node; struct t_collection { Node root; };
- 7. C但y Th畛 t畛c T狸m (Find ) extern int KeyCmp( void *a, void *b ); /* Returns -1, 0, 1 for a < b, a == b, a > b */ void *FindInTree( Node t, void *key ) { if ( t == (Node)0 ) return NULL; switch( KeyCmp( key, ItemKey(t->item) ) ) { case -1 : return FindInTree( t->left, key ); case 0: return t->item; case +1 : return FindInTree( t->right, key ); } } void *FindInCollection( collection c, void *key ) { return FindInTree( c->root, key ); } Less, search left Greater, search right
- 8. C但y Th畛 t畛c Find key = 22; if ( FindInCollection( c , &key ) ) . n = c->root; FindInTree( n, &key ); FindInTree(n->right,&key ); FindInTree(n->left,&key ); return n->item;
- 9. C但y ho畉t 畛ng Find C但y hon ton Chi畛u cao, h C叩c node di truy畛n tr棚n m畛t con 動畛ng t畛 g畛c 畉n m畛t l叩 S畛 c叩c node, h n = 1 + 21 + 22 + + 2h = 2h+1 - 1 h = floor( log2 n )
- 10. C但y Ho畉t 畛ng Find C但y hon ton V狸 ch炭ng t担i c畉n nhi畛u nh但t h+1 ph辿p so s叩nh, 畛 ph畛c t畉p O(h+1) ho畉c O(log n) Gi畛ng nh動 t狸m ki畉m nh畛 ph但n
- 11. T畛ng k畉t Arrays 董n gi畉n, nhanh Kh担ng m畛m d畉o O(1) O(n) inc sort O(n) O(n) O(logn) T狸m ki畉m nh畛 ph但n Add Delete Find Linked List 董n gi畉n M畛m d畉o O(1) sort -> no adv O(1) - any O(n) - specific O(n) (kh担ng t狸m ki畉m nh畛 ph但n) Trees V畉n 董n gi畉n M畛m d畉o O(log n)
- 12. C但y B畛 xung (Addition) C畛ng 21 vo c但y Ch炭ng t担i c畉n t畛i a h+1 ph辿p so s叩nh T畉o m畛t node m畛i (th畛i gian l h畉ng s畛) add l畉y c1(h+1)+c2 ho畉c c log n V狸 th畉 vi畛c b畛 xung vo m畛t c但y c滴ng chi畉m th畛i gian l log n Ignoring low order terms
- 13. C但y - Addition th畛 t畛c static void AddToTree( Node *t, Node new ) { Node base = *t; /* If it's a null tree, just add it here */ if ( base == NULL ) { *t = new; return; } else if( KeyLess(ItemKey(new->item),ItemKey(base->item)) ) AddToTree( &(base->left), new ); else AddToTree( &(base->right), new ); } void AddToCollection( collection c, void *item ) { Node new, node_p; new = (Node)malloc(sizeof(struct t_node)); /* Attach the item to the node */ new->item = item; new->left = new->right = (Node)0; AddToTree( &(c->node), new ); }
- 14. C但y B畛 xung (Addition) Find c log n Add c log n Delete c log n Hi畛u qu畉 r畉t 叩ng k畛! Tuy nhi棚n v畉n b畉t g畉p m畛t s畛 tr動畛ng h畛p ..
- 15. C但y B畛 xung (Addition) L畉y danh s叩ch k箪 t畛 ny v h狸nh thnh m畛t c但y A B C D E F ??
- 16. Trees - Addition Nh畉n danh s叩ch k箪 t畛 ny v h狸nh thnh m畛t c但y A B C D E F Trong tr動畛ng h畛p ny: ? Find ? Add ? Delete