برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: درخت دودویی درخت مرتبی است که هر عنصر آن حداکثر دارای دو فرزند چپ و راست باشد. اگر یک گره فقط یک فرزند داشته باشد، باید مشخص شود که فرزند چپ است یا راست. درخت عبارت و درخت تصمیم نمونه‌هایی از کاربردهای درخت دودویی هستند. معروف به د. د. ج می‌باشد. معمولا عملیات زیر بر روی یک درخت جستجوی دودویی تعریف می‌شود: ایجاد یک درخت جستجوی خالی آزمایش خالی بودن درخت درج کردن یک کلید جدید در درخت، بدون برهم‌خوردن خاصیت درخت جستجو کردن و یافتن یک کلید خاص در درخت حذف کردن یک کلید از درخت، با حفظ خاصیت درخت پیمایش درخت جستجوی دودویی، به طوری تمام گره‌ها دقیقا یک‌بار مورد دسترسی قرارگیرند. برای پیدا کردن گرهی با یک کلید خاص مانند key در درخت، ابتدا باید از ریشه درخت شروع کنیم. اگر ریشه تهی باشد، درخت فاقد هر عنصری بوده و جستجو ناموفق خواهد بود. در غیر اینصورت، key را با مقدار گره ریشه مقایسه می‌کنیم، اگر برابر بودند، جستجو موفق است و گره ریشه همان گره موردنظر است. در غیر این صورت، دو حالت پیش خواهدآمد: key از گره ریشه کوچکتر است. در این‌حالت، هیچ عنصری در زیردرخت سمت راست وجود ندارد که مقدار کلید آن برابر با key باشد؛ بنابراین جستجو باید در زیردرخت سمت چپ ادامه‌یابد. key بزرگتر از گره ریشه است. در این حالت، هیچ عنصری در زیردرخت سمت چپ وجود ندارد که مقدار کلید آن برابر با key باشد؛ بنابراین جستجو باید در زیردرخت سمت راست ادامه‌یابد. سپس بسته به حالت یک و دو، زیردرخت سمت چپ یا زیردرخت سمت راست را به روش بازگشتی و با استفاده از الگوریتم بالا جستجو می‌کنیم. عمل جستجو در درخت جستجوی دودویی، از مرتبه است که در آن h ارتفاع درخت است. چرا که حداکثر باید به میزان عمق درخت، به طرف پایین حرکت کنیم. در این الگوریتم، هر راس ۳ اشاره‌گر دارد: اشاره‌گر به پدر اشاره‌گر به فرزند چپ اشاره‌گر به فرزند راست ممکن است الگوریتمی نیاز داشته‌باشیم که در آن تعداد فرزندان هر راس نامشخص باشد. در اینصورت به درختی نیاز داریم که در آن فرزندان هر راس رابه تعداد دلخواه بتوان‌افزود. در این الگوریتم، هر راس ۳ اشاره‌گر دارد: اشاره‌گر به پدر اشاره‌گر به فرزند چپ اشاره‌گر به راس بعدی در سمت راست خود راس و برای جستجو، ابتدا برچسب خود راس را چک می‌کنیم اگر برابر با key نبود، برچسب فرزند چپ آن را بررسی می‌کنیم و اگر برابر نبود به …
برداشت:
جستجوی درختی از جمله پرکاربردترین استفاده از یک درخت است . درخت یک مدل مناسب برای نمایش بسیاری از مفاهیم ، پدیده‌ها و رابطهٔ بین آن‌هاست . مثلا درخت فامیلی ، سلسله مراتب اداری ، عبارات ریاضی و بسیاری از بازی‌ها با درخت مدل می‌شوند . در واقع درخت‌ها ، گراف‌های خاصی هستند که در مورد ویژگی‌های آن‌ها نتایج نظری زیادی وجود دارد . درخت‌ها بسته به نوع نیاز ، تعداد برگ‌های مختلفی دارند .