درخت چپ‌گرا

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

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

با دانستن این نکته که فاصله‌ی یک گره تا نزدیک‌ترین برگ نواده‌اش دقیقا اندازه‌ی s است، می‌توان دریافت که هر گره در سطح s-value - 1دقیقا دارای دو فرزند‌ است. بنابراین زیردرخت نواده‌ی گره x حداقل از اندازه‌ی ${\displaystyle 2^{S-value(x)}-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 <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 Trees