درخت چپ گرا

دانشنامه عمومی

در علوم رایانه، یک درخت چپگرا یا یک هیپ چپ گرا یک صف اولویت دار است که با یک نوع از هیپ دودویی پیاده سازی می شود. هر گره یک مقدار s دارد که فاصله آن به نزدیکترین برگ می باشد. برعکس یک هیپ دودویی، یک درخت چپ گرا تلاش می کند تا متعادل نباشد تا فرزندان سمت راست هر گره مقدار کم ترS را بگیرد. درخت چپ گرا توسط کلارک الن کرین ( به انگلیسی: Clark Allan Crane ) اختراع شد. اسم آن از آنجاگرفته شده که زیردرخت چپ معمولاً بلندتر از زیردرخت راست است. وقتی یک گره جدید در یک درخت درج می شود، یک درخت تک گره ساخته می شود و با درخت موجود ادغام می گردد. برای حذف عضو کمینه، ریشه حذف می شود و سپس زیردرخت راست و چپ با هم ادغام می شوند. هر دوی این کارها در زمان O ( log n ) اجرا می شوند. برای درج ها، زمان کندتر از هیپ دودویی است. در هیپ دودویی زمان سرشکن شده درج O ( 1 ) و در بدترین حالت آن O ( log n ) می باشد. درخت های چپ گرا به دلیل ادغام سریع تر نسبت به هیپ دودویی که در Θ ( n ) اتفاق می افتد مفید هستند. در بیشتر مواقع، در هیپ اریب عملکرد بهتری دارد.
درخت های چپ گرای معمول درخت های ارتفاع ـ جانبدارانه هستند اما سوگیریهای دیگری نیز می توانند داشته باشند مثل درخت چپ گرای وزن - جانبدارانه.
مقدار s یک گره فاصله آن گره تا نزدیک ترین برگ در نمایش درخت دودویی گسترش یافته است. در شکل، نمایش گسترش یافته ( نشان داده نشده ) درخت را پر می کند تا یک درخت دودویی کامل بسازد ( اضافه کردن پنج برگ ) ، کمینه فاصله تا برگ ها نیز در شکل مشخص شده است. بنابراین مقدارs راس 4 برابر 2 است زیرا نزدیک ترین برگ راس 8 می باشد ( اگر 8 توسیع شده باشد ) . مقدار s راس 5 برابر 1 است زیرا در نمایش گسترش یافته آن خودش یک برگ خواهد داشت.
با دانستن این نکته که فاصله ی یک گره تا نزدیک ترین برگ نواده اش دقیقا اندازه ی s است، می توان دریافت که هر گره در سطح s - value - 1دقیقا دارای دو فرزند است. بنابراین زیردرخت نواده ی گره x حداقل از اندازه ی 2 S − v a l u e ( x ) − 1 خواهد بود و مقدار بیشینه ی s در این گره log ⁡ ( m + 1 ) خواهد بود که m تعداد گره های زیردرخت نواده ی گره x است.
بیشتر عملگر ها بر روی درخت چپ گرای ارتفاع جانبدار با استفاده از عملگر ادغام انجام می شوند.
عمل ادغام، دو درخت چپ گرای کمینه ارتفاع جانب دارانه را به عنوان ورودی دریافت و یک درخت چپ گرای کمینه ارتفاع جانب دارانه را در خروجی ارایه می دهد.
عکس درخت چپ گراعکس درخت چپ گراعکس درخت چپ گراعکس درخت چپ گرا
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلف

پیشنهاد کاربران

بپرس