کد و الگوریتم درخت جست و جوی دودویی Binary search tree با ++C و java

BST-Binary search tree

آپدیت : در قسمت اول کد و الگوریتم درخت جست و جوی دو دویی را که با سی پلاس پلاس نوشته ام می بینید و در قسمت دوم کد درخت BST را با زبان جاوا که آقای Farhang Amary برایمان فرستاده اند را خواهید دید.

درخت جست و جوی دو دویی – Binary search tree :

درخت جست و جوی دودویی یکی از بهترین ساختمان داده ها است و بر اساس آن می توان ساختمان داده های متعددی تولید کرد.این درخت که به آن BST هم گفته می شود دارای ویژگی ها بسیار خوبی است ازجمله سرعت در انجام عملیات های نختلف و نگه داری از آن.

درخت جست و جوی دودویی درخت است که حداکثر دو فرزند دارد و تمام نود ها در زیر درخت سمت راست یک گره برزگ تر مساوی گره است و تمام گره ها در زیر درخت سمت چپ گره کوچک تر از گره است به شکل زیر نگاه کنید :

BST

به بالا ترین گره در درخت که فرزند هیج گره ای نیست ریشه می گویند.

برای  گره ها  ساختمان داده زیر را درنظر گرفته ام :

که دارای ویژگی های زیر است :

data : دیتا که همان مقدار یا کلید گره است و باید توجه داسته باشید که مقداری منحصر به فرد است یعنی دو گره یک مقدار ندارند ،البنه با کمی تغییر کد می توانید این مشکل را حل کنید.

parent: که اشارگری به کلاس node است و به پدر یک گره اشاره می کند ، تمام گره های پدر دارند بجز ریشه که نال است.

leftChild: اشارگری به شی از کلاس node است که به بچه ی سمت چپ یک گره اشاره می کند و در صورتی که بچه سمت چپ وجود نداشت مقدار نال را دارد.

rightChild: اشارگری به شی از کلاس node است که به بچه ی سمت راست یک گره اشاره می کند و در صورتی که بچه سمت راست وجود نداشت مقدار نال را دارد.

node : سازنده کلاس است .

در شکل زیر ساختمان داده گره ها را می بینید:

Node

برای درخت هم کلاس و ساختمان داره زیر را در نظر گرفته ام:

در ادامه تمام توابع درون آن را همراه الگوریتمشان شرح خواهیم داد:

root: این کلاس فقط یک ویژگی دارد و آن ریشه درخت است.

تابع Insert :

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

اگر ارتفاع درخت h باشد هزینه درج گره جدید برابر  او h  است.

 

تابع display :

این تابع درخت را در خروجی کنسول رسم می کند . رسم یک درخت معمولا کار سخت و زمان گیری است ولی با یه کم کد باحال می شه این کار در چند خط کد به زیبایی انجام داد :

کد تابع نمایش :

در زیر نمونه ای از رسم درخت را می بینید :

display-bst-tree

همین طور که می بینید درخت بسیار مرت چاپ شده است بطوری که هر گره زیر پدر خود قرار دارد ، همین طور ریشه مشخص شده است.

تابع minimum :

این تابع کوچک ترین گره ی درخت را بر می گرداند.همین طور که گفتیم هر گره های سمت چپ یک گره از آن گره کوچک تر هستند، پس کوچک ترین گره سمت چپ ترین گره است پس ما آن قدر به سمت چپ می رویم تا به نال برسیم.

کد زیر که تابع مینیمم است :

 

تابع maximum :

تابع ماکزیمم هم مانند تابع مینیمم است ، گره های سمت راست یک گره بزرگ تر مساوی آن گره هستند پس بزرگ ترین گره سمت راست ترین گره در درخت است  و برای رسیدن به آن از ریشه شروع می کنیم و آن قدر به راست می رویم تا به هیچ (نال) برسیم.

کد تابع ماکزیمم را در زیر می بینید:

 

تابع Search :

همین طور که از اسم درخت (Binary search tree)  مشخص است سرچ در درخت یکی از جنبه های خیلی مهم این درخت است.فرض کنید یک گره به اسم x را در درخت می خواهیم بیابیم از ریشه شروع به مقایسه می کنیم اگر x.data برابر با ریشه بود یک اشارگر به ریشه برمی گردانیم . در صورت برابر نبود ، اگر x.data بزرگ تر مساوی مقدار ریشه بود به سمت راست می رویم

اگر کوچک تر بود به سمت چپ می رویم این کار را مرتب انجام می دهیم تا به گره مورد نظر برسیم و اگر تا برگ های (برگ به گره های آخر درخت می گویند که هیچ فرزندی ندارند) درخت رسیدم و گره مورد نظر را پیدا نکردیم هیچ یا همان نال را بر می گردانیم که مشخص می کند گره ی مورد نظر در درخت نبوده است.

کد زیر مربوط به تا بع سرچ است :

 

تابع  inorder_tree_walk  یا Sort ( مرتب سازی):

این تابع به صورت inorder  درخت را پیمایش می کند یعنی ابتدا فرزند چپ را می بیند بعد ریشه و بعد فرزند سمت راست که این کار نود های درخت را به صورت سعودی و مرتب شده نشان می دهد.

در واقع این تابع همان  Binary sort  یا مرتب سازی دودویی است

 

تابع successor :

successor یک گره به گره ای می گویند که اگر تمام گره های یک درخت را مرتب شده و سعودی کنار هم قرار دهیم بلافاصله بعد از گره مورد نظر ما  ظاهر می شود ، این تابع در تابع حذف گره کاربرد دارد.

می توان درخت را به سورت سورت شده در آورد و بعد ساکسسور گره را پیدا کرد ولی این کار بسیار پرهزینه است . را آسان تری نیز برای این کار وجود دارد.

اگر گره ای که می خواهیم ساکسسورش را پیدا کنیم بچه ی سمت راست داشت آنگاه ساکسسور گره کوچک ترین گره در زیر درخت سمت راست گره است به شکل زیر دقت کنید:

successor

همین طور که می بینید successor  گره نود گره ی نود و پنج است که در زیر درخت سمت راست گره ی نو کوچک ترین گره است.

این روش برای زمانی بود که گره بچه ی سمت راست داشته باشد .حال اگر گره ای که می خواستیم  successor آن را پیدا کنیم فرزند سمت راست نداشت یا کلا فرزند نداشت چه کنیم؟
در این موقع از پدر گره ی مورد نظر شروع می کنیم و مرتب به بالا می رویم تا زمانی این کار را می کنیم که گره ای که رویش هستیم فرزند سمت راست پدرش باشد و به نال نرسیده باشیم.

به شکل بالا نگاه کنید successor گره ی ۸۷ را می خواهیم پیدا کنیم ، از پدر ۸۷ مه گره ی ۸۵ است شروع می کنیم به بالا رفتن ، ۸۷ پسر سمت راست ۸۵ است پس مجاز است دوباره یک گره می رویم بالا و به گره ی ۹۰ می رسیم ۸۵ گره ی سمت چپ ۹۰ است پس همین جا دست از کار می کشیم ، ۹۰ ساکسسور ۸۷ است.

کد تابع successor را در زیر می بینید :

 

تابع predecessor :

predecessor یک گره به گره ای می گویند که در حالت سورت شده تمام گره ها دقیقا قبل از گره ی مورد نظر می آید.

predecessor دقیقا پیدا کردنش شبیه ساکسسور است ولی هر کاری که برای ساکسسور می کردیم برعکسش را برای این تابع می کنیم.

کد تابع predecessor را در زیر می بینید :

 

تابع transplant :

این تابع در تابع حذف گره از درخت استفاده می شود ، این تابع دوگره u و v را به عنوان ورودی می گیرد و اگر u ریشه درخت باشد آنگاه v را ریشه درخت قرار می دهد ،اگر u ریشه دره نباشد پدر u را به v اشاره می دهد ،و اگر v نال نبود پدر v را پدر u قرار می دهد ، در واقع این تابع v را جای u قرار می دهد و از نظر رابطه با گره ی پدر کار ها را درست می کند ولی کاری به جابهجا کردن فرزندان u , v ندارد.

کد این تابع را در زیر آمده است :

تابع deletion :

این تابع گره ای را به عنوان ورودی می گیرد و آن را از درخت حذف می کند ، الگوریتم آن به این شکل است :

– اگر گره هیچ فرزندی نداشت خوب کاری خاصی انجام نمی دهیم فقط حذفش می کنیم.

– اگر گره فرزند سمت راست نداشت با استفاده از تابع transplant فرزند سمت چپش را جایش می گذاریم.

-اگر گره فرزند فقط سمت راست  داشت ، با استفاده از transplant فرزند سمت راستش را جایش می می گذاریم.

– اگر گره دو فرزند داشت ، آنگاه  successor گره را پیدا می کنیم ،
-اگر ساکسسور گره فرزند گره مورد نظر نبود : آنگاه با استفاده از transplant بچه ی سمت راست ساکسسور را جا ساسسکسور می گداریم و فرزند راشت ساکسسور را فرزند راست گره ی مورد نظر قرار می دهیم،و در ادامه با استفاده از تابع transplant ساکسسور را جای گره ی مورد نظز می گذاریم و بچه ی سمت چپ ساکسسور را بچه ی سمت راست گره ی مورد می کنیم.

-اگر ساکسسور گره ی فرزند گره ی مورد نظر بود:با استفاده از تابع transplant ساکسسور را جای گره ی مورد نظز می گذاریم و بچه ی سمت چپ ساکسسور را بچه ی سمت راست گره ی مورد می کنیم.

یه خورده چیزی که خواستم بگم عجیب قریب شد اگر به کد نگاه کنید حتما متوجه منظورم می شوید :

 

 تابع menu :

این تابع منویی برای  کار کردن با درخت جست و جوی دودویی می سازد مانند شکل زیر:

menu

کد منو را در زیر می بینید:

 

و در آخر هم کد کلی درخت جست و جوی دو دویی (Binary search tree – BST ) را می بینید همراه main  برنامه :

 

قسمت دوم:
کد درخت جست و جوی دو دویی (BST) را با زبان جاوا می بینید که آقای  Farhang Amary  لطف کرده اند و در اختیارمان قرار داده اند.

جمله خودشون در مورد کد زیر:

 

پیاده سازی نود و درخت جستجوی دودویی رو به صورت جنریک (کلید و مقدار) که کلید، هر نوعی که واسط Comparable رو پیاده سازی کنه قبول میکنه ، به همراه توابع جستجو ،درج ، حذف ،کمترین و بیشترین رو نوشتم

کد های برنامه در دوفایل جداگانه به اسم BST.java  و BSTNode.java قرار دارد که در زیر آن را مشاهده می کنید:

BST.java :

 

BSTNode.java :

 

Digg This
Reddit This
Stumble Now!
Buzz This
Vote on DZone
Share on Facebook
Bookmark this on Delicious
Kick It on DotNetKicks.com
Shout it
Share on LinkedIn
Bookmark this on Technorati
Post on Twitter
Google Buzz (aka. Google Reader)

۴۳ دیدگاه

  • سلام و عرض ادب، بسیار لذت بردم و استفاده کردم از مطالب خوبتون، امیدوارم روز به روز در راه نشر علم و دانش موفق تر باشید و آرزوی سلامتی و دل خوش دارم براتون. جدا زحمت می کشید، خسته نباشید، باعث افتخار هستید.
    ارادتمند

  • حیف ام اومد بخونم ولی تشکر نکنم ؛
    ممنون از مطالب خوبی که میذارین
    :*)

  • سلام سایت خیلی خوبی هست مرسی
    من میخوام شجره‌نامه درست کنم بعد اگه بیشتر از دوتا فرزند داشته باشه نمیشه از دو دویی استفاده کنم اگه میشه یک راهنمایی کنین یا کدش رو بدین مرسی

    • خوب از یک درخت غیر دوتایی استفاده کن! ببین برای ساخت درخت دوتایی هر راس درختت دو اشاره گر دارد یکی به فرزند چپ و یکی به راست ! حالا یک راه ساده این است که اشاره گر های درون راس درخت را افزایش دهیم

      • منظورتون رو نفهمیدم درختی که میخوام بسازم پویا هست و ممکن هست تعداد فرزندان زیاد باشه برای همین نمیشه به تعداد فرزندان اشاره گر زد
        برای سرچ کردن هم مشکل پیدا کردم باید پیمایش ککنیم درخت رو اما وقتی اشاره گری ببه فرزندان دیگه نداریم نمیشه

        • یک کتاب الگوریتم خیلی معروف هست به اسم
          Introduction to algorithm
          که به
          CLRS
          هم معروف ، هر کدام از کاراکترهای بالا اول فامیلی هر کدام از نویسنده هاش است.

          به صفحه ی ۲۴۷ شکل شماره ی ۱۰.۱۰ ویرایش ۳ این کتاب مراجعه کن – مشکلت حل می شه.

          • خیلی مرسی مشکل من حل شد خیلی ممنون اگه مشکل خوردم باز مزاحم میشم خیلی ممنون

  • سلام ممنون بابت برنامه خوبتون واقعا مفید بود . یه سوال داشتم :
    بازسازی درخت جستجوی دودویی چه فرقی با کدی که شما گذاشتین داره؟

    • سلام – ببین ک بالا درخت جست و جوی دودویی رو به صورت عادی می سازد یعنی ما یک نود را وارد درخت می کنیم و طبق قواعد درخت باینری دودویی یک جایی از درخت قرار می گیره که بعضی واقع باعث می شه درخت به صورت نامتوازن رشد کند و عمق درخت در یک قسمت زیاد شود اون موقع دیگه هزینه ی جست و جو در درخت دیگر lg n نیست بلکه n lg n است. به همین دلیل باید یک سری الگوریتم های دیگه هستند مانند red black tree که حذف و اضافه کردن نود به درخت رو طوری انجام می دهند که درخت متوازن می ماند.

      • سلام
        ببینید من جواب سوالمو نگرفتم . راستش استادم یه پروژه تعیین کرده برای بازسازی درخت جستجوی دودویی و من شبیه این کد رو نوشتم و تحویل استادم دادم ولی ایشون میگه من بازسازی میخوام نه خود کد رو . میشه راهنمایی م کنید بازسازی درخت یعنی چی؟

  • سلام……میخواستم اگه درخت رو بازسازی کنم یعنی وقتی یک مقدار رو حذف کنم که جاش خالی نمونه و مقدار بعدی جایگزینش بشه (((به اصطلاح بازسازی درخت جستجوی دودویی کنم)) باید چیکار کنم—خیلی ممنون

  • با سلام خدمت open-mind ببخشید برای موازنه کردن این درخت میشه راهنمایی کنید؟

  • salam
    man y database daram ke mikham searchi ke roosh bzanam ro ba search binary bashe.
    kasi rahi baladi ke bge.

  • سوال:
    ۱.آیا میشه در یک نود از درخت، دو یا چند داده ذخیره کرد؟
    ۲.و یکی از اون داده ها رو به عنوان کلید نود درنظر گرفت؟
    ممنون میشم جواب بدید.

    • فرهاد دلیرانی

      سلام بله ، من از یک دیتا از نوع عدد صحیح استفاده کردم ، هدفم این بود که کارکرد درخت باینری رو نشان بدهم ، شما می تونی مانند کد جاوا آخر پست برنامتو جنریک بنویسی یعنی مهم نباشه به کلاست درختت چی می دی.برای این کار کد درخت bst به صورت template س بنویس

  • اگه میشه پیمایش ترتیب سطح درخت دودویی رو بزارید رو سایت

  • سلام وقت بخیر
    میشه جواب پیامای منا بدید؟؟؟؟؟؟خواهش میکنم

  • سلام میشه جواب منا بدید؟

  • سلام آقای دلیرانی وقت بخیر
    این سوال به این بخش ربطی نداره ولی من در اجرای این برنامه دچار مشکل شدم …در خط ۲۹ برنامه
    (srand time0)()وقتی با devاز میکنم خطا در اجرا میده این خطا را میده ([Error] ‘getch’ was not declared in this scope)و برنامه را ران نمیکنه میشه بهم کمک کنید هرچه سریع تر
    ۱دنیا ممنون
    #include

    using std::cout;

    using std::cin;

    using std::endl;

    #include

    #include

    using std::setw;

    const int RACE_END = 70;

    void moveTortoise(int * const);

    void moveHare(int * const);

    void printCurrentPositions(const int * const, const int * const);

    int main()

    {

    int tortoise = 1, hare = 1, timer = 0;

    srand(time(0));

    cout << "ON YOUR MARK, GET SET\nBANG !!!!"

    <= hare)

    cout << "\nTORTOISE WIN. Yuch.\n";

    cout << "TIME ELABSED = " << timer << " seconds" <= 1 && x <= 5) //fast plod

    *turtlePtr += 3;

    else if (x == 6 || x == 7) //slip

    *turtlePtr -= 6;

    else //slow plod

    ++(*turtlePtr);

    if(*turtlePtr RACE_END)

    *turtlePtr = RACE_END;

    }

    //+++++++++++++++

    void moveHare(int * const rabbitPtr)

    {

    int y = 1 + rand() % 10;

    if(y == 3 || y == 4) //big hop

    *rabbitPtr += 9;

    else if(y == 5) //big slip

    *rabbitPtr -= 12;

    else if(y >= 6 && y 8) //small slip

    *rabbitPtr -= 2;

    if(*rabbitPtr RACE_END)

    *rabbitPtr = RACE_END;

    }

    //——————-

    void printCurrentPositions(const int * const snapperPtr, const int * const bunnyPtr)

    {

    if(*bunnyPtr == *snapperPtr)

    cout << setw(*bunnyPtr) << "oUCH!!!";

    else if (*bunnyPtr < *snapperPtr)

    cout << setw(*snapperPtr – *bunnyPtr) << 'T'

    << setw(*snapperPtr – *bunnyPtr) << 'T';

    else

    cout << setw(*snapperPtr) << 'T'

    << setw(*bunnyPtr – *snapperPtr) << 'H';

    cout << '\n';

    }

  • سلام و عرض ادب
    ببخشید چطوری میشه مثل شما دو تا کلاس در ویژوال استادیو ۲۰۱۰ تعریف کرد؟؟
    من این کار رو کردم ولی error دادو براش ناشناس بود
    خواهش میکنم کمکم کنید

  • قربون دستت !!!!!!!!!!!!!!!!!

  • خیلی دمت گرمه اگه کدنمایش گرافیکی درختم بنویسی داداشی!

  • کارتون عالیه، متشکریم.
    در مورد این مطلب یک نکته مهم اینکه اگر یک Object از کلاس bst در کلاس node قرار میدادید (اشاره گری به درخت حاوی گره جاری) کدهای مربوط به برخی متدهای دیگه میتونست بسیار بهینه بشه همچنین به نظر بنده این یک نقص است در کد وقتی کلاسها و کد قابلیت تشخیص اینکه یک گره به کدام درخت تعلق دارد را نداشته باشد.

    • فرهاد دلیرانی

      تشکر از نظر خوبتان. متاسفانه من این کد بیشتر برای بررسی الگوریتمی درخت جست و جوی دو دویی نوشتم ، اگر شما کد این درخت رو با نکاتی که خود ذکر کرده اید نوشته اید می توانید آن را برایم ایمیل کنید تا آن را در اختیار سایر دوستان و خوانندگان قرار دهیم.

      • راستش وقت نکردم هنوز تو سی پلاس پلاس انجام بدم ولی چون خودم جاواکار هستم اومدم برای یادآوری واسه خودم دقیقاً یک پروژه به اسم mydatastructures ایجاد کردم و میخوام پیاده سازی تمام ساختمانهای داده و الگوریتمهای مربوطه رو تو این پکیج بنویسم خیلی لازم میشه فعلاً پیاده سازی نود و درخت جستجوی دودویی رو به صورت جنریک (کلید و مقدار) که کلید، هر نوعی که واسط Comparable رو پیاده سازی کنه قبول میکنه ، به همراه توابع جستجو ،درج ، حذف ،کمترین و بیشترین رو نوشتم همین الان جفت کلاس ها رو واستون ایمیل میکنم

  • باسلام
    من هفته آینده پروژه دارم میخواستم که من وراهنمایی کنید درمورد الگوریتم هافمن.توقسمت پیاده سازی درختش گیرکردم
    ممنون میشم اگه راهنمایی کنید

  • بسیار عالی بود! تشکر.
    همچین مطالبی تو وب پارسی بسیار کمیاب است. کارتون رو ادامه بدید، و دسته بندیتون رو بهتر کنید.

پاسخ دهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *