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

یک درخت جستجوی دودویی با اندازه ۹، عمق ۳، ریشه ۸ و برگ‌های ۱، ۴، ۷ و ۱۳.

هر چند یک هرم برای کاربردهائی که نیازمند صف‌های اولویت هستند کاملاً مناسب بوده ولی برای کاربردهایی که در آن عناصر دلخواهی باید از لیست حذف گردند، مناسب نمی‌باشد. زمان حذف یک عنصر دلخواه از یک هرم n عنصری، برابر O(n) می‌باشد (که در این زماین فقط برای یافتن عنصر موردنظر مصرف می‌شود). این زمان ارجحیتی نسبت به زبان موردنیاز برای حذف یک عنصر دلخواه از لیست خطی نامرتب ندارد. اگر قرار باشد تنها توابع جستجو، درج و حذف بر روی یک ساختمان داده انجام شوند، درخت جستجوی دودویی از بیان ساختمان داده‌هایی که تاکنون برسی کرده‌ایم بهتر خواهد بود. در حقیقت، توسط درخت جستجوی دودویی قادر خواهیم بود این کار را هم توسط مقدار کلید (برای مثال، حذف عنصری با کلید x) و هم با مرتبه (rank) (برای مثال، حذف پنجمین عنصر کوچک) آن انجام دهیم. تعریف: یک درخت جستجوی دودویی یک درخت دودویی است که ممکن است تهی باشد. اگر درخت دودویی تهی نباشد، آنگاه دارای ویژگی‌های زیر است: ۱) هر عنصر دارای یک کلید است و دو عنصر نباید دارای کلید یکسان باشند، در واقع کلیدها مجزا (منحصر به فرد) هستند.

۲) کلیدهای و اقع در زیر درخت غیر تهی چپ (در صوت وجود) باید کمتر از مقدار کلید واقع در ریشه باشند. ۳) کلیدهای واقع در زیر درخت راست (در صورت وجود) باید بزرگتر از مقدار کلید واقع در ریشه باشند. ۴) زیر درختان چپ و راست نیز خود درختان جستجوی دودویی می‌باشند.

در این تعریف عبارت‌های تکراری مشاهده می‌شود. خواص (۲)، (۳) و (۴) مجموعاً به این اصل تأکید دارند که کلیدها باید مجزا باشند. بنابراین، می‌توانیم خاصیت (۱) را به ین صورت تعریف کنیم: ریشه دارای یک کلید است. چند نمونه از درختان دودویی که در آنها عنصرها دارای کلیدهای مجزا هستند در شکل ۱ نمایش داده شده‌است. درخت شکل ۱- الف، یک درخت جستجوی دودویی نیست زیرا یک درخت راست خاصیت (۴) را برآورده نمی‌کند. این زیر درخت به این دلیل درخت جستجوی دودویی نیست که، ریشه‌ای با کلید (۲۵) و فرزند راستی با کلید کمتر از (۲۲)۲۵ دارد. شکل ۱- ب و شکل ۱- پ، درختان جستجوی دودویی هستند.

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

از آن جایی که تعریف درخت جستجوی دودویی بازگشتی است، لذا ارائه یک روش جستجوی بازگشتی نیز ساده می‌باشد. فرض کنید می‌خواهیم عنصری با کلید x را پیدا کنیم. ابتدا از ریشه شروع می‌کنیم. اگر ریشه تهی باشد، درخت جستجو فاقد هر عنصری بوده و جستجو ناموفق خواهد بود. در غیر این صورت x را با کلید موجود در ریشه مقایسه می‌کنیم. اگر x مساوی این کلید باشد آن گاه جستجو به صورت موفقیت آمیز خاتمه می‌یابد. اگر x کمتر از مقدار کلید ریشه باشد، پس هیچ عنصری در زیردرخت راست وجود ندارد که دارای کلیدی برابر x باشد. بنابراین زیردرخت چپ ریشه را جستجو می‌کنیم.

برنامه ۱- جستجوی بازگشتی یگ درخت جستجوی دودویی

اگر x بزرگتر از مقدار کلید ریشه باشد، زیردرخت راست ریشه را جستجو می‌کنیم. برنامه۱، زیردرختان را به صورت بازگشتی جستجو میکند. دراین تابع فرض شده که درخت موجود جستجو به صورت پیوندی نمایش داده شده‌است (که فر می‌شود شیئی از کلاس BST است)، هر گره (BstNode) دارای سه فیلد می‌باشد: LeftChild، Rightchild و data. data شیئی از کلاس Element<Type> است و حداقل دارای فیلدی به نام key از نوع Type است. به راحتی می‌توان بازگشت برنامه ۱ را مانند برنامه ۲ با یک حلقه for تعویض کرد.

برنامه ۲- جستجوی تکراری یک درخت جستجوی دودویی

اگر بخواهیم جستجو را بر اساس مرتبه انجام دهیم، هر گره باید دارای فیلد اضافه دیگری به نام LeftSize باشد که برابر تعداد عناصر زیر درخت چپ گره به علاوه ۱ است. برای درخت جستجوی شکل ۱- ب، گره‌های با کلید ۲، ۵، ۳۰ و ۴۰ به ترتیب دارای ۱ LeftSize، ۲، ۳ و ۱ هستند. برنامه ۳، k امین عنصر کوچک را جستجو می‌کند. همان طور که مشاهده می‌کنید، یک درخت جستجوی دودویی با عمق h را باهم کلید و هم با مرتبه در زمانی معادل O(h) می‌توان جستجو کرد.

برنامه ۳- جستجوی یک درخت دودویی با مرتبه

درج عنصری به داخل درخت جستجوی دودویی برای درج یک عنصر جدید مانند x ابتدا باید مشخص کنیم که کلید این عنصر با عناصر موجود تفاوت دارد یا خیر. برای انجام این کار باید درخت را جستجو نمود. اگر جستجو ناموفق باشد، آن گاه عنصر در مکانی که جستجو خاتمه یافته درج می‌شود. به عنوان مثال برای درج یک عنصر با کلید ۸۰ به درون درخت شکل ۱- ب، ابتدا درخت را برای عنصر جستجو می‌کنیم. این جستجو در پایان ناموفق خاتمه می‌یابد و آخرین گره‌ای که ملاقات شده گره با کلید ۴۰ بوده‌است. عنصر جدید به عنوان فرزند ر است این گره درج می‌شود. درخت جستجوی حاصل در شکل ۲- الف نمایش داده شده‌است. شکل ۲-ب درخت جستجوی حاصل از درج عنصری با کلید ۳۵ به درخت جستجوی شکل ۲ قسمت الف را نشان می‌دهد. برنامه ۴ درج را با روش توضیح داده شده، پیاده سازی می‌کند. اگر گره‌ای دارای فیلد LeftSize باشد.

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

برنامه ۴- درج به درون یک درخت جستجوی دودویی

حذف عنصری از درخت جستجوی دودویی

حذف گه برگ این نوع درخت کار ساده‌ای است. به عنوان مثال، برای حذف ۳۵ از درخت شکل ۲- ب باید فیلد فرزند چپ والد این گره را برابر صفر قرار داده و گره را آزاد نمود. به این ترتیب درخت شکل ۲- الف حاصل می‌شود. برای حذف عنصر ۸۰ از این درخت، فیلد فرزند سمت راست (righhtchild) گره ۴۰ را برابر صفر قرار می‌دهیم که درخت شکل ۱- ب حاصل می‌شود و گره حاوی ۸۰ آزاد می‌شود. حذف عنصر غیرپایانی که فقط یک فرزند دارد نیز آسان است. اگر محتوی عنصری که می‌خواهد حذف شود، آزاد شده و تنها فرزندش جای گره آزاد شده را می‌گیرد. بنابراین برای حذف عنصر ۵ از درخت شکل ۲- الف به سادگی اشاره گر گره والد (یعنی گره‌ای که حاوی ۳۰ است) را برای اشاره به تنها فرزندش (یعنی گره‌ای که شامل ۲ است) تغییر می‌دهیم. زمانی که قرار است یک گره با دو فرزند حذف شود، بزرگ‌ترین عنصر زیر درخت چپ و یا کوچک‌ترین عنصر زیر درخت راست آن جایگزین آن می‌شود. سپس این فرآیند را با حذف این عنصر جایگزین از زیردرختی که از آن گرفته شده‌است، دنبال می‌کنیم. برای مثال فرض کنید می‌خواهیم عنصری با کلید ۳۰ را از درخت شکل ۲- ب حذف کرده و سپس آن را با بزرگ‌ترین عنصر موجود در زیر درخت چپش (۵) و یا کوچک‌ترین عنصر در زیر درخت راستش (۳۵) جایگزین کنیم. ۵ به ریشه متقل شده و درخت شکل ۳- الف حاصل می‌شود. اکنون باید دومین ۵ را حذف کنیم. از آن جایی که این گره فقط یک فرزند دارد، اشاره گر والدش طوری تغییر می‌یابد که به این فرزند اشاره کند. اکنون شکل ۳-ب به دست می‌آید. می‌توان اثبات نمود که بزرگترین و کوچک‌ترین عضو در یک درخت همیشه در گره با درجه حداکثر ۱ قرار دارد. بنابراین حذف از چنین گره‌ای کاملاً ساده می‌باشد. نوشتن این تابع را به عنوان تمرین به شما محول کرده‌ایم. واضح است که اگر درخت دارای عمق h باشد آن گاه حذف از این درخت در زمان O(h) انجام خواهد گرفت.

الحاق و تقسیم درختان دودویی

اگرچه که جستجو، درج و حذف عملکردهایی هستند که اغلب بر روی درخت جستجوی دودویی انجام می‌شوند، اما اعمال دیگری نیز وجود دارند که در کاربردهای به خصوصی کارآیی دارند. برخی از این اعمال در زیر آمده‌اند: الف) C.Three WayJoin : این تابع، یک درخت جستجوی دودویی مانند C ایجاد می‌کند که این درخت مرکب از عناصر اولیه درختان جستجوی دودویی A و B و هم چنین عنصر منفردی به نام x است. فرض شده‌است که هر عنصر A کلیدی کوچک تر از کلید x و هر عنصر B را از بین ببرد. ب) C.Two WayJoin (A،B) : این تابع، دو درخت جستجوی دودویی A و B را برای بدست آوردن یک درخت جستجوی دودویی به نام C که شامل تمام عناصر اولیه در A و B است، با یکدیگر الحاق می‌کند. فرض می‌شود که تمام کلیدهای A کوچک تر از تمام کلیدهای B هستند و این عمل الحاق هر دوی این دخرتان را از بین خواهد برد. پ) A.Split (i، B، x، C) : درخت جستجوی دودویی A را به سه بخش تقسیم می‌کند، به این صورت که B یک درخت جستجوی دودویی است که شامل تمام عناصر A می‌باشد که کلیدی کمتر از i دارند؛ اگر A شامل نصری با کلید i باشد آن گاه این کلید به درون پارامتر مرجع x کپ شده و اشاره گری به x برگردانده می‌شود (در غیر این صورت، مقدار صفر برگردانده می‌شود که نشان دهنده این است که عنصری با کلید i در A وجود ندارد). C یک درخت جستجوی دودویی است که شامل تمام رکوردهای A می‌باشد که کلیدی بزرگتر از i دارند. عمل جداسازی ممکن است باعث پاک شدن A شود. یک الحاق سه طرفه (three-way) را به راحتی می‌توان انجام داد. به راحتی یک گره جدید به دست آورده و فیلد داده (data) آن را برابر x، فرزند چپش را اشاره گری به A، و فرزند راستش را اشاره گری به B قرار می‌دهیم. این گره سازنده ریشه C است. زمان موردنیاز برای این عملکرد، O(۱) است و عمق جدید C برابر max {height (A)، height (B)}+۱ است. الحاق دو طرفه (two-way) را در نظر بگیرید. اگر هر کدام از درختان A یا B خالی باشند C نتیجه خواهد شد. وقتی هیچ کدام تهی نباشند، ابتدا باید رکورد x از A که دارای بالاترین ارزش کلید است را حذف کنیم. درخت جستجوی دودویی حاصل را A می‌نامیم. برای ادامه فرآیند، عمل الحاق سه طرفه را به صورت C.Three WayJoin انجام می‌دهیم. کل زمان موردنیاز برای انجام الحاق دو طرفه برابر O(height (A)) بوده و عمق C نیز برابر max{height(A)، height(B)}+۱ است. اگر همراه با هر درخت عمق آن را نیز نگه داریم، زمان اجرا را می‌توان به O(min{heght(A)،height(B)} کاهش داد. سپس رکوردی از A را حذف می‌کنیم که دارای بزرگ‌ترین مقدار کلید است، به شرط این که عمق A بیشتر از عمق B نباشد؛ در غیر این صورت رکوردی از B که دارای کوچک‌ترین مقدار کلید است را حذف می‌کنیم. بعد از این کار یک عمل الحاق سه طرفه انجام می‌شود. برای انجام عمل تقسیم، ابتدا متوجه می‌شویم که تقسیم از ریشه (یعنی (i=A.rootdata.key کاری نسبتاً ساده‌است. در این حالت، B زیر درخت چپ x،A رکورد موجود در ریشه و C زیر درخت راست A است. اگر i کوچک تر از کلید موجود در ریشه باشد، آن گاه ریشه به همراه درخت راستش باید در C باشند. اگر i بزرگ تر از کلید ریشه باشد، ریشه و زیر درخت جستجوی چپش باید در B باشند. با توجه به این مشاهدات، می‌توانیم عمل تقسیم را با پیمودن درخت جستجوی A برای یافتن رکوردی با کلید i انجام دهیم. همین طور که به سمت پایین حرکت می‌کنیم دو درخت B و C را تکمیل می‌کنیم. الگوریتم این مساله در برنامه ۵ آمده‌است. برای ساده کردن دستورات، کار، را با دو گروه head، Y و Z به ترتیب برای B و C شروع می‌کنیم. B به عنوان زیردرخت سمت راست Y و C به عنوان فرزند چپ Z رشد می‌کند. L(R به گره‌ای از Y(Z اشاره می‌کند که در آن، زیر درختان بعدی A که باید قسمتی از B(C باشند، متصل می‌شوند. اتصال یک زیردرخت به B(C به عنوان فرزند راست (چپ) L(R انجام میگیرد.

برنامه ۵- تقسیم یک درخت جستجوی دودویی

تجزیه و تحلیل تابع Split :

حلقه while باعث حفظ این خاصیت می‌شود که تمام کلیدها در زیر درختی با ریشه p بزرگ تر از
کلیدهایی هستند که در Y و کوچک تر از کلیدهایی هستند که در Z موجودند. اثبات درستی این تابع
کاری ساده‌است و زمان اجرای آن O(height(A است. به سادگی می‌توان این مسئله را اثبات کرد که B و C عمقشان بیشتر از A نیست.

عمق یک درخت جستجوی دودویی

اگر به اندازه کافی دقت نشود، عمق یک درخت جستجوی دودویی با n عنصر می‌تواند به بزرگی n باشد. برای مثال این حالت وقتی پیش می‌آید که از برنامه ۴ برای درج کلیدهایی با مقادیر [۱٬۲،۳،…،n] در یک درخت جستجوی دودویی تهی استفاده کنیم. اما هنگامی که درج و حذف با استفاده از توابع مطرح شده به صورت اتفاقی انجام می‌شود، عمق درخت جستجوی دودویی به طور متوسط برابر ( O(log n خواهد بود. درختان جستجو با عمق O(log n بدترین حالت را درختان جستجوی متوازن (متعادل) می‌نامند. درختان جستجوی متعادلی وجود دارند که عمل جستجو، درج و حذف را در زمان (O(h ممکن می‌سازند. قابل توجه‌ترین درختان در بین این موارد، درختان AVL، ۲-۳، ۲-۳-۴، قرمز/ سیاه، و B-tree هستند.

پیوندهای خارجی

معرفی، درج و حذف از درخت جستجوی دودویی درخت جستجوی دودویی

منبع

ساختمان داده نوشته الیس هورویتز

هر چند یک هرم برای کاربردهائی که نیازمند صف‌های اولویت هستند کاملاً مناسب بوده ولی برای کاربردهایی که در آن عناصر دلخواهی باید از لیست حذف گردند، مناسب نمی‌باشد. زمان حذف یک عنصر دلخواه از یک هرم n عنصری، برابر O(n) می‌باشد (که در این زماین فقط برای یافتن عنصر موردنظر مصرف می‌شود). این زمان عرجحیتی نسبت به زبان موردنیاز برای حذف یک عنصر دلخواه از لیست خطی نامرتب ندارد اگر قرار باشد تنها توابع جستجو، (درج و حذف) بر روی یک ساختمان داده انجام شوند، درخت جستجوی دودویی از بیان ساختمان داده‌هایی که تاکنون برسی کرده‌ایم بهتر خواهد بود. در حقیقت، توسط درخت جستجوی دودویی قادر خواهیم بود این کار را هم توسط مقدار کلید(برای مثال حذف عنصری با کلید ایکس)و هم با مرتبه (رنک)(برای مثال :حذف پنجمین عنصر کوچک)ان انجام میدهیم. د. تعریف: یک درخت جستجوی دودویی یک درخت دودویی است که ممکن است تهی باشد. اگردودویی تهی نباشد، آنگاه دارای ویژگی‌های زیر است: 1:هر عنصر دارای یک کلید است و دو عنصر نباید دارای کلید یکسان باشند، در واقع کلیدها مجزا (منحصر به فرد) هستند.

کلیدهای و اقع در زیر درخت غیر تهی چپ (در صوت وجود) باید کمتر از مقدار کلید واقع در ریشه باشند.2 کلیدهای واقع در زیر درخت راست (در صورت وجود) باید بزرگتر از مقدار کلید واقع در ریشه باشند.3 زیر درختان چپ و راست نیز, خود درختان جستجوی دودویی می‌باشند.4

در این تعریف عبارت‌های تکراری مشاهده می‌شود. خواص (۲)، (۳) و (۴) مجموعاً به این اصل تأکید دارند که کلیدها باید مجزا باشند. بنابراین، می‌توانیم خاصیت (۱) را به این صورت تعریف کنیم: ریشه دارای یک کلید است. چند نمونه از درختان دودویی که در آنها عنصرها دارای کلیدهای مجزا هستند در شکل ۱ نمایش داده شده‌است. درخت شکل ۱- الف، یک درخت جستجوی دودویی نیست زیرا یک درخت راست خاصیت (۴) را برآورده نمی‌کند. این زیر درخت به این دلیل درخت جستجوی دودویی نیست که، ریشه‌ای با کلید (۲۵) و فرزند راستی با کلید کمتر از (۲۲)۲۵ دارد. شکل ۱- ب و شکل ۱- پ، درختان جستجوی دودویی هستند.

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

از آن جایی که تعریف درخت جستجوی دودویی بازگشتی است، لذا ارائه یک روش جستجوی بازگشتی نیز ساده می‌باشد. فرض میکنید عنصری با کلید ایکس را پیدا کنیم , ابتدا از ریشه شروع می‌کنیم. اگر ریشه تهی باشد، درخت جستجو فاقد هر عنصری بوده و مساوی این کلید باشد بوده. x را با کلید موجود در ریشه مقایسه می‌کنیم. اگر x جستجو نا موفق خواهد بود در غیر این صورت باشد.. انگاه جست وجو ناموفق خواهد بود در غیر این صورت ایکس را با کلید موجود در ریشه مقایسه میکنیم .اگرایکس مساوی این کلید باشد انگاه جست و جو به صورت موفقیت امیزی خاتمه میابد .اگر ایکس کمتر از مقدار کلید ریشه باشد پس هیچ عنصری در زیر درخت راست وجود ندارد که دارای کلیدی برابر ایکس باشد.بنابراین زیر درخت چپ را جست و جو میکنیم

برنامه ۱- جستجوی بازگشتی یگ درخت جستجوی دودویی

اگر x بزرگتر از مقدار کلید ریشه باشد، زیردرخت راست ریشه را جستجو می‌کنیم. زیردرختان را به صورت بازگشتی جستجو میکنند. دراین تابع فرض شده که درخت موجود جستجو به صورت پیوندی نمایش داده شده‌است (که فرض می‌شود شیئی از کلاس BST است)، هر گره (BstNode) دارای سه فیلد می‌باشد: LeftChild، Rightchild و data. data شیئی از کلاس Element<Type> است و حداقل دارای فیلدی به نام key از نوع Type است. به راحتی می‌توان بازگشت برنامه ۱ را مانند برنامه ۲ با یک حلقه for تعویض کرد.

برنامه ۲- جستجوی تکراری یک درخت جستجوی دودویی

اگر بخواهیم جستجو را بر اساس مرتبه انجام دهیم، هر گره باید دارای فیلد اضافه دیگری به نام LeftSize باشد که برابر تعداد عناصر زیر درخت چپ گره به علاوه ۱ است. برای درخت جستجوی شکل ۱- ب، گره‌های با کلید ۲، ۵، ۳۰ و ۴۰ به ترتیب دارای ، ۲، ۳ و ۱ LeftSize و1هستند. برنامه ۳، k امین عنصر کوچک را جستجو می‌کند. همان طور که مشاهده می‌کنید، یک درخت جستجوی دودویی با عمق h را باهم کلید و هم با مرتبه در زمانی معادل O(h )می‌توان جستجو کرد. برنامه ۳- جستجوی یک درخت دودویی با مرتبه

درج عنصری به داخل درخت جستجوی دودویی :برای درج یک عنصر جدید مانند x ابتدا باید مشخص کنیم که کلید این عنصر با عناصر موجود تفاوت دارد یا خیر؟. برای انجام این کار باید درخت را جستجو نمود. اگر جستجو ناموفق باشد، آن گاه عنصر در مکانی که جستجو خاتمه یافته درج می‌شود. به عنوان مثال برای درج یک عنصر با کلید ۸۰ به درون درخت شکل ۱- ب، ابتدا درخت را برای عنصر جستجو می‌کنیم. این جستجو در پایان ناموفق خاتمه می‌یابد و آخرین گره‌ای که ملاقات شده گره با کلید ۴۰ بوده‌است. عنصر جدید به عنوان فرزند راست این گره درج می‌شود. درخت جستجوی حاصل در شکل ۲- الف نمایش داده شده‌است. شکل ۲-ب درخت جستجوی حاصل از درج عنصری با کلید ۳۵ به درخت جستجوی شکل ۲ قسمت الف را نشان می‌دهد. برنامه ۴ درج را با روش توضیح داده شده، پیاده سازی می‌کند. اگر گره‌ای دارای فیلد LeftSize باشد.

1: