درخت چپ‌گرا

در علوم رایانه، یک درخت چپگرا یا یک هیپ چپ گرا یک صف اولویت دار است که با یک نوع از هیپ دودویی پیاده‌سازی می‌شود. هر گره یک مقدار s دارد که فاصله آن به نزدیکترین برگ می‌باشد. برعکس یک هیپ دودویی، یک درخت چپ گرا تلاش می‌کند تا متعادل نباشد تا فرزندان سمت راست هر گره مقدار کم ترS را بگیرد.
درخت چپ گرا توسط کلارک الن کرین (به انگلیسی: Clark Allan Crane)اختراع شد. اسم آن از آنجاگرفته شده که زیردرخت چپ معمولاً بلندتر از زیردرخت راست است.
وقتی یک گره جدید در یک درخت درج می‌شود، یک درخت تک گره ساخته می‌شود و با درخت موجود ادغام می‌گردد. برای حذف عضو کمینه، ریشه حذف می‌شود و سپس زیردرخت راست و چپ با هم ادغام می‌شوند. هر دوی این کارها در زمان O(log n) اجرا می‌شوند. برای درج‌ها، زمان کندتر از هیپ دودویی است. در هیپ دودویی زمان سرشکن شده درج O(1) و در بدترین حالت آن O(log n) می‌باشد.
درخت‌های چپ گرا به دلیل ادغام سریع تر نسبت به هیپ دودویی که در Θ(n) اتفاق می‌افتد مفید هستند.در بیشتر مواقع، در هیپ اریب عملکرد بهتری دارد.

سوگیری

درخت‌های چپ گرای معمول درخت‌های ارتفاع ـ جانبدارانه هستند اما سوگیریهای دیگری نیز می‌توانند داشته باشند مثل درخت چپ گرای وزن-جانبدارانه.

مقدار s

مقدار s یک گره فاصله آن گره تا نزدیک‌ترین برگ در نمایش درخت دودویی گسترش یافته‌است. در شکل، نمایش گسترش یافته (نشان داده نشده) درخت را پر می‌کند تا یک درخت دودویی کامل بسازد (اضافه کردن پنج برگ)، کمینه فاصله تا برگ‌ها نیز در شکل مشخص شده‌است. بنابراین مقدارs راس 4 برابر 2 است زیرا نزدیک‌ترین برگ راس 8 می‌باشد (اگر 8 توسیع شده باشد). مقدار s راس 5 برابر 1 است زیرا در نمایش گسترش یافته آن خودش یک برگ خواهد داشت.

با دانستن این نکته که فاصله‌ی یک گره تا نزدیک‌ترین برگ نواده‌اش دقیقا اندازه‌ی s است، می‌توان دریافت که هر گره در سطح s-value - 1دقیقا دارای دو فرزند‌ است. بنابراین زیردرخت نواده‌ی گره x حداقل از اندازه‌ی $2^{S-value(x)}-1$ خواهد بود و مقدار بیشینه‌ی s در این گره $\log {(m+1)}$خواهد بود که m تعداد گره‌های زیردرخت نواده‌ی گره x است.

عمل‌گرها بر روی درخت‌های چپ‌گرای ارتفاع جانبدار

بیشتر عملگر‌ها بر روی درخت چپ‌گرای ارتفاع جانبدار با استفاده از عملگر ادغام انجام‌ می‌شوند.

ادغام کردن درخت‌های چپ گرای کمینه ارتفاع جانبدار

عمل ادغام، دو درخت چپ‌گرای کمینه ارتفاع جانب‌دارانه را به عنوان ورودی دریافت و یک درخت چپ‌گرای کمینه ارتفاع جانب‌دارانه را در خروجی ارایه می‌دهد.

ادغام کردن دو گره با هم به این بستگی دارد که درخت بیشینه ارتفاع-جانبدارانه‌است یا کمینه ارتفاع-جانبدارانه. برای درخت کمینه ارتفاع-جانبدارانه گره پر ارزش تر را فرزند راست بچه کم ارزش تر قرار می‌دهیم.اگر گره کم ارزش تر یک فرزند راست داشت آنگاه گره با ارزش تر را با زیردرختی که ریشه اش فرزند راست گره کم ارزشتر هست ادغام می‌شود.

بعد از ادغام مقدار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 <y.element)
  if(x.element.compareTo(y.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 doesn't 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;
}

مقدار دهی اولیه کردن یک درخت چپ گرای ارتفاع جانبدار

مقدار دهی اولیه کردن یک درخت چپ گرای ارتفاع جانبدار، عمدتاً از دو راه انجام می‌شود. راه اول ادغام هر گره به‌طوریست که در هر زمان یک گره به یک HBLT(Height Biased Leftist Tree)اضافه شود. این فرایند ناکارآمد است و در زمان O(nlog n) اجرا می‌شود. روش دیگر استفاده از صف برای ذخیره هر گره و درخت حاصل است. دو بخش اول صف پاک می‌شوند، ادغام می‌شوند، و دوباره در آن‌ها نوشته می‌شود. این می‌تواند یک HBLT را در زمان O(n) مقدار دهی اولیه کند. در سه شکل موجوداین روش شرح داده شده‌است.

برای مقداردهی اولیه کردن یک HBLT کمینه، هر عنصری را که به درخت اضافه می‌شود را در صف قرار می‌دهیم. در مثال (قسمت اول از را چپ ببینید)، مجموعه اعداد [4, 8, 10, 9, 1, 3, 5, 6, 11] مقدار دهی اولیه می‌شوند. هر خط از شکل چرخهٔ دیگری از الگوریتم را نشان می‌دهد و محتویات صف را مشخص می‌کند. پنج مرحله اول برای دنبال کردن راحت هستند. به این توجه کنید که HBLT ساخته شده به تازگی به انتهای صف اضافه می‌شود. در مرحله پنجم برای اولین بار یکی از مقادیر s بزرگتر از 1 می‌شود. مرحله ششم دو درخت ادغام شده با یکدیگر با نتایج مشخص را نشان می‌دهد.

در بخش دوم، ادغام کمی پیچیده تر صورت می‌گیرد. درخت با ارزش کمتر (درخت x) یک فرزند راست دارد، بنابراین ادغام دوباره باید روی زیردرختی که ریشه اش فرزند راست درخت x و درخت دیگر است فراخوانی شود. بعد از ادغام با زیردرخت در نهایت درخت حاصل در درخت x جایگزاری می‌شود. حال مقدار s فرزند راست (s=2) بزرگتر از مقدارs فرزند چپ (s=1) است، پس باید با هم جابجا شوند. حال مقدار s ریشه گره چهارم برابر 2 است.

قسمت سوم پیچیده‌ترین بخش است که در آن تابع بازگشتی ادغام دو بار فرآخوانی می‌شود(هر بار با زیردرخت فرزند راست که خاکستری نشده‌اند). در اینجا از روند ذکر شده در بخش دوم استفاده می‌شود.

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Leftist tree». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۱۰ دسامبر ۲۰۱۱.

پیوند به بیرون

• Leftist Trees