درخت چپ‌گرا

در علوم رایانه، یک درخت چپگرا یا یک هیپ چپ گرا یک صف اولویت دار است که با یک نوع از هیپ دودویی پیاده‌سازی می‌شود. هر گره یک مقدار s دارد که فاصله آن به نزدیکترین برگ می‌باشد. برعکس یک هیپ دودویی، یک درخت چپ گرا تلاش می‌کند تا متعادل نباشد تا فرزندان سمت راست هر گره مقدار کم‌ترS را بگیرد.
درخت چپ گرا توسط کلارک الن کرین (به انگلیسی: Clark Allan Crane)اختراع شد. اسم آن از آنجاگرفته شده که زیردرخت چپ معمولا بلندتر از زیردرخت راست است.
وقتی یک گره جدید در یک درخت درج می‌شود، یک درخت تک گره ساخته می‌شود و با درخت موجود ادغام می‌گردد. برای حذف عضو کمینه، ریشه حذف می‌شود و سپس زیردرخت راست و چپ با هم ادغام می‌شوند. هر دوی این کارها در زمان O(log n) اجرا می‌شوند. برای درج‌ها، زمان کندتر از هیپ دودویی است. در هیپ دودویی زمان سرشکن شده درج O(1) و در بدترین حالت آن O(log n) می‌باشد.
درخت‌های چپ گرا به دلیل ادغام سریع‌تر نسبت به هیپ دودویی که در (n) اتفاق می‌افتد مفید هستند.در بیشتر مواقع، در هیپ اریب عملکرد بهتری دارد.
سوگیری
درخت‌های چپ گرای معمول درخت‌های ارتفاع  جانبدارانه هستند اما سوگیریهای دیگری نیز می‌توانند داشته باشند مثل درخت چپ گرای وزن-جانبدارانه.
مقدار s
thumb
مقدار s یک گره فاصله آن گره تا نزدیک‌ترین برگ در نمایش درخت دودویی گسترش یافته‌است. در شکل، نمایش گسترش یافته (نشان داده نشده) درخت را پر می‌کند تا یک درخت دودویی کامل بسازد (اضافه کردن پنج برگ)، کمینه فاصله تا برگ‌ها نیز در شکل مشخص شده‌است. بنابراین مقدارs راس 4 برابر 2 است زیرا نزدیک‌ترین برگ راس 8 می‌باشد (اگر 8 توسیع شده باشد). مقدار s راس 5 برابر 1 است زیرا در نمایش گسترش یافته آن خودش یک برگ خواهد داشت.
ادغام کردن درخت‌های چپ گرای ارتفاع جانبدار
ادغام کردن دو گره با هم به این بستگی دارد که درخت بیشینه ارتفاع-جانبدارانه‌است یا کمینه ارتفاع-جانبدارانه. برای درخت کمینه ارتفاع-جانبدارانه گره پر ارزش‌تر را فرزند راست بچه کم ارزش‌تر قرار می‌دهیم.اگر گره کم ارزش‌تر یک فرزند راست داشت آنگاه گره با ارزش‌تر را با زیردرختی که ریشه‌اش فرزند راست گره کم ارزشتر هست ادغام می‌شود.
بعد از ادغام مقدارs گره کم ارزش‌تر باید به روز شود. حال بررسی می‌شود که آیا گره کم ارزش‌تر فرزند چپ دارد. اگر نداشته باشد از فرزند راست به فرزند چپ حرکت صورت می‌گیرد. اگر یک فرزند چپ داشت فرزند با بالاترین مقدارs باید به سمت چپ برود.
کد جاوا برای ادغام کردن یک درخت چپ گرای کمینه ارتفاع-جانبدار
public Node merge(Node x, Node y) {
if(x == null)
return y;
if(y == null)
return x;
// if this was a max height biased leftist tree, then the
// next line would be: if(x.element 0) {
// x.element> y.element
Node temp = x;
x = y;
y = temp;
x.rightChild = merge(x.rightChild, y);
if(x.leftChild == null) {
// left child doesnt exist, so move right child to the left side
x.leftChild = x.rightChild;
x.rightChild = null;
x.s = 1;
else {
// left child does exist, so compare s-values
if(x.leftChild.s <x.rightChild.s) {
Node temp = x.leftChild;
x.leftChild = x.rightChild;
x.rightChild = temp;
// since we know the right child has the lower s-value, we can just
// add one to its s-value
x.s = x.rightChild.s + 1;
return x;
مقدار دهی اولیه کردن یک درخت چپ گرای ارتفاع جانبدار
thumb
مقدار دهی اولیه کردن یک درخت چپ گرای ارتفاع جانبدار، عمدتا از دو راه انجام می‌شود. راه اول ادغام هر گره به‌طوریست که در هر زمان یک گره به یک HBLT(Height Biased Leftist Tree)اضافه شود. این فرایند ناکارآمد است و در زمان O(nlog n) اجرا می‌شود. روش دیگر استفاده از صف برای ذخیره هر گره و درخت حاصل است. دو بخش اول صف پاک می‌شوند، ادغام می‌شوند، و دوباره در آن‌ها نوشته می‌شود. این می‌تواند یک HBLT را در زمان O(n) مقدار دهی اولیه کند. در سه شکل موجوداین روش شرح داده شده‌است.
برای مقداردهی اولیه کردن یک HBLT کمینه، هر عنصری را که به درخت اضافه می‌شود را در صف قرار می‌دهیم. در مثال (قسمت اول از را چپ ببینید)، مجموعه اعداد 4, 8, 10, 9, 1, 3, 5, 6, 11 مقدار دهی اولیه می‌شوند. هر خط از شکل چرخه‌ی دیگری از الگوریتم را نشان می‌دهد و محتویات صف را مشخص می‌کند. پنج مرحله اول برای دنبال کردن راحت هستند. به این توجه کنید که HBLT ساخته شده به تازگی به انتهای صف اضافه می‌شود. در مرحله پنجم برای اولین بار یکی از مقادیر s بزرگتر از 1 می‌شود. مرحله ششم دو درخت ادغام شده با یکدیگر با نتایج مشخص را نشان می‌دهد.thumb
در بخش دوم، ادغام کمی پیچیده‌تر صورت می‌گیرد. درخت با ارزش کمتر (درخت x) یک فرزند راست دارد، بنابراین ادغام دوباره باید روی زیردرختی که ریشه‌اش فرزند راست درخت x و درخت دیگر است فراخوانی شود. بعد از ادغام با زیردرخت در نهایت درخت حاصل در درخت x جایگزاری می‌شود. حال مقدار s فرزند راست (s=2) بزرگتر از مقدارs فرزند چپ (s=1) است، پس باید با هم جابجا شوند. حال مقدار s ریشه گره چهارم برابر 2 است.thumb
قسمت سوم پیچیده‌ترین بخش است که در آن تابع بازگشتی ادغام دوبار فرآخوانی می‌شود(هر بار با زیردرخت فرزند راست که خاکستری نشده‌اند). در اینجا از روند ذکر شده در بخش دوم استفاده می‌شود.