درخت جستجوی دودویی

[sa1378]

سلام
برای درخت جستجوی دودویی که من تو کتاب خوندم نوشته بود که در این درخت از ریشه شروع میکنیم و کلید های بزرگتر رو توی فرزند سمت راست و کوچکتر رو توی فرزند سمت چپ میزاریم
.
.
حالا میخوایم جستجو رو انجام بدیم (مثلا دنبال کلید x هستیم)
گفت که از ریشه شروع میکنیم
اگه مساوی بود که پیدا شده
اگه کمتر بود میریم چپ
اگه بیشتر بود میریم راست
.
.
نمیدونم درست فهمیدم یا نه
اگه اینجوری باشه مثلا توی این درخت:
122726
اگه میخوایم 5 رو پیدا کنیم:
اول : 5<20 پس میریم چپ
دوم : 5<10 پس میریم چپ
سوم : 5<7 پس میریم به چپ
ولی چپ دیگه نداریم پس تموم میشه و 5 پیدا نشده
ولی 5 توی درخت وجود داره

ممنون میشم بگین اصلش چجوریه؟

[ciavosh]

این درخت غلط چیده شده. چون 5 قطعا باید در بازوی چپ ریشه یعنی 20 باشد. یعنی چیدمان درخت نیز باید از روی قوانین آن صورت بگیرد.

[a.r.khoshghalb]

سلام
به تشکر از ciavosh (http://barnamenevis.org/member.php?339838-ciavosh).
درخت شما درخت جستجوی دودویی (یا باینری سرچ) نیست. یک درخت کاملا دلخواهه.
درخت باینری سرچ اینطوری درست میشه:
اولین عضو رو میذاری به عنوان ریشه. بعد هر عضوی خواستی اضافه کنی دقیقا طبق همون الگوریتمی که خودت گفتی میری دنبالش!
یعنی فرض کن می خوای x رو اضافه کنی، می بینی اگر x کمتر مساوی ریشه بود، میری چپ وگرنه راست و به همین صورت... انقدر میری تا به یه راسی برسی که قراره از اونجا مثلا بری راست، ولی این راس، راست نداره. x رو به عنوان بچه راست راس قرار میدی.

[مسعود اقدسی فام]

درختی که اینحا نمایش داده شده درختی هست که فرزند چپ و راست به ترتیب کوچکتر و بزرگتر هستن. این تعریف درخت جستجوی دودویی نیست.
تعریف: درخت جستجوی دودویی درخت دودویی است که عناصر زیر درخت چپ و راست هر گره از مقدار خود گره به ترتیب کوچکتر و بزرگتر هستند.
یعنی باید کل زیر درخت رو در نظر بگیرید و نه صرفا فرزند رو. پس جای 5 درست نیست. چون از 20 کوچکتر هست و سمت راست اون قرار داده. روش ساخت دودویی هم از ریشه شروع می‌شه. همین جستجویی که نوشتید رو انجام می‌دن و همون جایی که عدد مورد نظر پیدا نشد (فرزند چپ هفت) درج می‌کنن.

[sa1378]

ممنون از همه دوستان