ParsX.com
پذیرش پروژه از دانشجویی ... تا سازمانی 09376225339
 
   ProfileProfile   Log in to check your private messagesLog in to check your private messages  |  FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups Log inLog in   RegisterRegister 

Binary Search Tree درخت جستجوی دودویی

 
Post new topic   Reply to topic    ParsX.com Forum Index -> طراحي الگوريتم
View previous topic :: View next topic  
Author Message
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Wed Dec 29, 2010 11:25 am    Post subject: Binary Search Tree درخت جستجوی دودویی Reply with quote

اگر X را یک گره در این درخت فرض کنیم . اگر گره ای را درسمت چپ این گره X ببینیم حتما کوچکتر مساوی با X است.
اگر گره ای در سمت راست گره X باشد یعنی حتما بزرگتر مساوی X است.

وقتی این درخت را inorder پیمایش می کنیم خروجی بصورت مرتب صعودی نمایش داده می شود.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Wed Dec 29, 2010 11:27 am    Post subject: Reply with quote

کلا جستجو کردن در این درخت ، کمینه یابی ، بیشینه یابی، عنصر قبلی، عنصر بعدی همگی با O(h) انجام می شود که h ارتفاع درخت است.
Back to top
vahid
بي تو هرگز


Joined: 26 Nov 2004
Posts: 3067
Location: Tehran

PostPosted: Wed Dec 29, 2010 3:35 pm    Post subject: Reply with quote

برای یافتن min در این درخت کافیست از ریشه به سمت چپ حرکت کنیم برگ پیدا شده مینیموم است.
برای یافتن ماکسیموم از ریشه به سمت راست پایین حرکت می کنیم برگ پیدا شده ماکسیموم است.
برای یافتن عنصر بعدی کافیست مینیموم را در زیردرخت راست پیدا کنید.
برای یافتن عنصر قبلی کافیست ماکسیموم را در زیر درخت چپ پیدا کنید.
Back to top
Display posts from previous:   
Post new topic   Reply to topic    ParsX.com Forum Index -> طراحي الگوريتم All times are GMT + 3.5 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum