شجرة اليسار

📅 آخر تحديث: ٣ أغسطس ٢٠٢٦
✍️ نُشر في: ٣ أغسطس ٢٠٢٦
📷 يحتوي على 26 صور
الموسوعة الحرة

في علم الحاسوب ، تُعرف الشجرة اليسارية أو الكومة اليسارية بأنها طابور أولوية مُنفذ باستخدام نوع مُعدّل من الكومة الثنائية . لكل عقدة x قيمة s ، وهي المسافة إلى أقرب ورقة في الشجرة الفرعية التي جذرها x. [ 1 ] على عكس الكومة الثنائية ، تسعى الشجرة اليسارية إلى أن تكون غير متوازنة للغاية. فبالإضافة إلى خاصية الكومة ، تُصان الأشجار اليسارية بحيث يكون للفرع الأيمن لكل عقدة أقل قيمة s.

ابتكر كلارك آلان كرين شجرة اليسار المتحيزة للطول . [ 2 ] ويأتي الاسم من حقيقة أن الشجرة الفرعية اليسرى عادة ما تكون أطول من الشجرة الفرعية اليمنى.

الشجرة اليسارية هي كومة قابلة للدمج . عند إدخال عقدة جديدة في شجرة، تُنشأ شجرة جديدة مكونة من عقدة واحدة وتُدمج مع الشجرة الموجودة. لحذف عنصر، يُستبدل بدمج شجرتيه الفرعيتين اليسرى واليمنى. تستغرق كلتا العمليتين زمنًا قدره O(log n ). بالنسبة للإدخال، يُعد هذا أبطأ من أكوام فيبوناتشي ، التي تدعم الإدخال في زمن ثابت قدره O(1) ، وفي أسوأ الحالات O(log n ).

تتميز الأشجار اليسارية بقدرتها على الدمج السريع، مقارنةً بالأكوام الثنائية التي تستغرق Θ( n ). في معظم الحالات، يكون دمج الأكوام المائلة أكثر كفاءة. مع ذلك، فإن دمج الأكوام اليسارية له تعقيد زمني في أسوأ الحالات O(log n )، بينما يبلغ تعقيد دمج الأكوام المائلة O(log n ) فقط بعد الاستهلاك.

تحيز

الشجرة اليسارية المعتادة هي شجرة يسارية منحازة للارتفاع . [ 2 ] ومع ذلك، يمكن أن توجد انحيازات أخرى، كما هو الحال في الشجرة اليسارية المنحازة للوزن . [ 3 ]

يبلغ التعقيد الدقيق في أسوأ الحالات لكلا نوعي الأشجار اليسارية 2 log 2 n ، مع احتساب المقارنات. ومن المعروف أن التعقيد المُستهلك الدقيق للأشجار اليسارية ذات التحيز الوزني يطابق التعقيد المُستهلك الدقيق للأكوام المائلة log φ n (حوالي 1.44 log 2 n )، حيث φ ترمز إلى النسبة الذهبية ؛ وبالمثل، فإن التعقيد المُستهلك للأشجار اليسارية ذات التحيز الارتفاعي محدود من الأسفل بـ log φ n ، ولكن ما إذا كان هذا هو الحد الأعلى أيضًا، فهو مسألة مفتوحة . [ 4 ]

قيمة S

قيم S لشجرة يسارية

قيمة s (أو رتبة ) العقدة هي المسافة من تلك العقدة إلى أقرب موضع فارغ في الشجرة الفرعية التي جذرها تلك العقدة. بعبارة أخرى، قيمة s للفرع nullتساوي صفرًا ضمنيًا. أما العقد الأخرى، فقيمة s لها تساوي واحدًا زائدًا عن الحد الأدنى لقيم s لفروعها. لذا، في المثال على اليمين، جميع العقد التي لديها فرع واحد على الأقل مفقود لها قيمة s تساوي 1، بينما قيمة s للعقدة 4 تساوي 2، لأن قيمة s لفرعها الأيمن (8) تساوي 1. (في بعض الأوصاف، يُفترض أن قيمة s للفروع الفارغة تساوي -1. [ 5 ] )

بمعرفة أن أقصر مسار إلى أقرب ورقة مفقودة في الشجرة الفرعية المتجذرة عند x هو بالضبط s ( x )، فإن كل عقدة على عمق s ( x ) - 1 أو أقل لها طفلان بالضبط، لأن s ( x ) كانت ستكون أقل لولا ذلك. وهذا يعني أن حجم الشجرة المتجذرة عند x هو على الأقل2s(x)-1{\displaystyle 2^{s(x)}-1}وبالتالي، فإن قيمة s ( x ) هي على الأكثرسجل⁡(م+1){\displaystyle \log {(m+1)}}، حيث يمثل m عدد العقد في الشجرة الفرعية التي جذرها x . [ 1 ]

العمليات على شجرة يسارية ذات تحيز في الارتفاع

تُجرى معظم العمليات على شجرة اليسار المتحيزة للارتفاع باستخدام عملية الدمج. [ 1 ]

دمج اثنين من أجهزة Min HBLT

تأخذ عملية الدمج اثنين من Min HBLTs كمدخلات وتعيد Min HBLT يحتوي على جميع العقد الموجودة في Min HBLTs الأصلية مجتمعة.

إذا كانت أي من الشجرتين فارغة، فإن الشجرة المدمجة هي الأخرى. وإلا، فقم بتسمية جذريهما A وB بحيث يكون A.key ≤ B.key. وللحفاظ على خاصية الكومة، يجب أن يكون A هو جذر الشجرة المدمجة.

يتم الدمج عن طريق دمج الشجرة B بشكل متكرر مع الشجرة الفرعية اليمنى للشجرة A. قد يؤدي هذا إلى زيادة قيمة s للشجرة الفرعية اليمنى للشجرة A، وبالتالي زيادة قيمة s للشجرة A نفسها. إذا كانت قيمة s للنتيجة أكبر من قيمة s للشجرة الفرعية اليسرى للشجرة A، يتم تبديل الشجرتين الفرعيتين للحفاظ على خاصية الشجرة اليسارية.

خوارزمية زائفة لدمج شجرتين يساريتين متحيزتين للارتفاع الأدنى

ادمج (أ، ب) إذا كانت أ = فارغة، أرجع ب، إذا كانت ب = فارغة، أرجع أ، إذا كان مفتاح أ > مفتاح ب، أرجع ادمج (ب، أ) A.right := MERGE (A.right, B) // لا يمكن أن تكون النتيجة فارغة لأن B غير فارغة إذا كانت A.left = null ثم تبديل (A.يسار، A.يمين) A.s_value := 1 // بما أن الشجرة الفرعية اليمنى فارغة، فإن أقصر مسار إلى ورقة فرعية من العقدة A هو 1. أعد A إذا كانت A.right.s_value > A.left.s_value تبديل (A.يمين، A.يسار) A.s_value := A.right.s_value + 1 إرجاع أ

كود جافا لدمج شجرتين يساريتين متحيزتين للارتفاع الأدنى

دالة دمج العقدة العامة ( العقدة أ ، العقدة ب ) { إذا كانت ( أ == فارغ ) أرجع ب ؛ إذا كانت ( ب == فارغ ) أرجع أ ؛// اعكس اتجاه هذه المقارنة للحصول على كومة قصوى إذا ( a . element . compareTo ( b . element ) > 0 ) { Node temp = a ; a = b ; b = temp ; }إذا كان ( a.leftChild == null ) { تحقق من أن a.rightChild == null ؛ // باستخدام خاصية leftist // لا يوجد أي من الابنين، لذا فإن الدمج في الابن الأيسر أمر بديهي . a.leftChild = b ؛ تحقق من أن a.s == 1 ؛ } else { Node temp = merge ( a.rightChild , b ) ; إذا كان ( a.leftChild.s < temp.s ) { a.rightChild = a.leftChild ؛ a.leftChild = temp ؛ } else { a.rightChild = temp ؛ } // بما أننا نعلم أن الابن الأيمن لديه قيمة s أقل ، // يمكننا ببساطة إضافة واحد إلى قيمة s الخاصة به a.s = a.rightChild.s + 1 ؛ } return a ؛ }

كود هاسكل لدمج شجرتين يساريتين متحيزتين للارتفاع الأدنى

بيانات LHeap a = Leaf | Node a ( LHeap a ) ( LHeap a )rank :: LHeap a -> Integer rank Leaf = 0 rank ( Node _ _ r ) = rank r + 1دمج :: Ord a => LHeap a -> LHeap a -> LHeap a دمج ورقة h = h دمج ورقة h = h دمج h @ ( Node a l r ) h' @ ( Node a' _ _ ) | a > a' = دمج h' h | رتبة r' > رتبة l = Node a r' l | خلاف ذلك = Node a l r' حيث r' = دمج r h'

مثال

يوضح الشكل مثالاً لكيفية عمل عملية الدمج في شجرة يسارية. تمثل المربعات كل استدعاء للدمج.

عندما يتم فك التكرار، نقوم بتبديل الأبناء الأيسر والأيمن إذا كانت قيمة x.right.s_value أكبر من قيمة x.left.s_value لكل عقدة x. في هذه الحالة قمنا بتبديل الأشجار الفرعية المتجذرة في العقد ذات المفاتيح 7 و 10.

إدخال في جهاز استئصال الكبد الجزئي المصغر

تتم عملية الإضافة باستخدام عملية الدمج. عند إضافة عقدة إلى شجرة HBLT مصغرة موجودة مسبقًا، يتم إنشاء شجرة HBLT بحجم واحد تحتوي على تلك العقدة، ثم يتم دمجها مع الشجرة الموجودة.

INSERT ( A , x ) B := CREATE_TREE( x ) return MERGE( A , B )

حذف عنصر Min من Min HBLT

العنصر الأدنى في شجرة شجرة فرعية مصغر هو الجذر. لذا، لحذف العنصر الأدنى، يُحذف الجذر وتُدمج أشجاره الفرعية لتشكيل شجرة شجرة فرعية مصغر جديدة.

DELETE_MIN( A ) x := A .key A := MERGE ( A .right, A .left) return x

تهيئة شجرة يسارية ذات تحيز في الارتفاع

تهيئة نظام HBLT مصغر - الجزء 1

تتم تهيئة شجرة يسارية ذات تحيز ارتفاعي بإحدى طريقتين رئيسيتين. الأولى هي دمج كل عقدة على حدة في شجرة يسارية ذات تحيز ارتفاعي واحدة. هذه العملية غير فعالة وتستغرق وقتًا قدره O( nlogn ). أما الطريقة الأخرى فهي استخدام طابور لتخزين كل عقدة والشجرة الناتجة. يتم إزالة أول عنصرين من الطابور، ثم دمجهما، وإعادتهما إلى الطابور. يمكن لهذه الطريقة تهيئة شجرة يسارية ذات تحيز ارتفاعي في وقت قدره O( n ). هذه الطريقة موضحة بالتفصيل في الرسوم البيانية الثلاثة المرفقة. كما هو موضح، توجد شجرة يسارية ذات تحيز ارتفاعي أدنى.

لإنشاء شجرة HBLT مصغرة، ضع كل عنصر يُراد إضافته إلى الشجرة في قائمة انتظار. في المثال (انظر الجزء 1 إلى اليسار)، تم تهيئة مجموعة الأرقام [4، 8، 10، 9، 1، 3، 5، 6، 11]. يُمثل كل سطر في الرسم التخطيطي دورة أخرى من الخوارزمية، موضحًا محتويات قائمة الانتظار. الخطوات الخمس الأولى سهلة المتابعة. لاحظ أن شجرة HBLT المُنشأة حديثًا تُضاف إلى نهاية قائمة الانتظار. في الخطوة الخامسة، يظهر أول ظهور لقيمة s أكبر من 1. تُظهر الخطوة السادسة شجرتين مدمجتين مع بعضهما البعض، بنتائج متوقعة.

تهيئة نظام HBLT مصغر - الجزء الثاني

في الجزء الثاني، تحدث عملية دمج أكثر تعقيدًا بعض الشيء. الشجرة ذات القيمة الأدنى (الشجرة س) لها ابن أيمن، لذا يجب استدعاء دالة الدمج مرة أخرى على الشجرة الفرعية التي جذرها الابن الأيمن للشجرة س والشجرة الأخرى. بعد الدمج مع الشجرة الفرعية، تُعاد الشجرة الناتجة إلى الشجرة س. قيمة s للابن الأيمن (s=2) الآن أكبر من قيمة s للابن الأيسر (s=1)، لذا يجب تبديلهما. قيمة s للعقدة الجذرية 4 أصبحت الآن 2 أيضًا.

تهيئة نظام HBLT مصغر - الجزء 3

الجزء الثالث هو الأكثر تعقيدًا. هنا، نستدعي دالة الدمج مرتين بشكل متكرر (في كل مرة مع الشجرة الفرعية للابن الأيمن غير المظللة). يستخدم هذا نفس العملية الموضحة في الجزء الثاني.

حذف عنصر عشوائي من Min HBLT

إذا كان لدينا مؤشر إلى عقدة x في Min HBLT، فيمكننا حذفها على النحو التالي: استبدال العقدة x بنتيجة دمج شجرتيها الفرعيتين وتحديث قيم s للعقد الموجودة على المسار من x إلى الجذر، وتبديل الشجرتين الفرعيتين اليمنى واليسرى إذا لزم الأمر للحفاظ على خاصية الشجرة اليسارية.

يستمر التصفح التصاعدي حتى نصل إلى الجذر أو حتى لا تتغير قيمة s. وبما أننا نحذف عنصرًا، فلا يمكن زيادة قيم s على المسار الذي تم اجتيازه. كل عقدة هي بالفعل الابن الأيمن لعقدة الأب وتتسبب في انخفاض قيمة s لعقدة الأب، ستبقى على اليمين. أما كل عقدة هي الابن الأيسر لعقدة الأب وتتسبب في انخفاض قيمة s لعقدة الأب، فيجب تبديلها مع شقيقها الأيمن إذا أصبحت قيمة s أقل من قيمة s الحالية للابن الأيمن.

يجب أن تحتوي كل عقدة على مؤشر إلى العقدة الأصلية، حتى نتمكن من اجتياز المسار إلى الجذر وتحديث قيم s.

عندما ينتهي مسار التتبع عند العقدة y، تقع جميع العقد التي تم اجتيازها على المسار الأيمن الذي يبدأ من العقدة y. يوضح المثال أدناه ذلك. وبناءً على ذلك، فإن عدد العقد التي تم اجتيازها لا يتجاوز log(m)، حيث m هو حجم الشجرة الفرعية التي تبدأ من y. وبالتالي، تستغرق هذه العملية أيضًا O(lg m) للتنفيذ.

شجرة يسارية متحيزة للوزن

يمكن أن تكون الأشجار اليسارية متحيزة الوزن أيضًا. [ 6 ] في هذه الحالة، بدلاً من تخزين قيم s في العقدة x، نقوم بتخزين سمة w( x ) تشير إلى عدد العقد في الشجرة الفرعية التي جذرها x :

w( x ) = w( x.right ) + w( x.left ) + 1

تضمن عمليات WBLT أن يكون w(x.left) ≥ w(x.right) لجميع العقد الداخلية x. تضمن عمليات WBLT هذا الثابت عن طريق تبديل أبناء العقدة عندما يتجاوز حجم الشجرة الفرعية اليمنى حجم الشجرة الفرعية اليسرى، تمامًا كما هو الحال في عمليات HBLT.

دمج اثنين من أجهزة WBLT

تُبسط عملية الدمج في خوارزميات WBLT، إذ يُمكن حساب وزن الشجرة الفرعية المدمجة، وبالتالي قرار تبديل الأبناء، قبل إجراء الدمج. وبذلك، يُمكن تنفيذ الدمج في عملية اجتياز واحدة من أعلى الشجرة إلى أسفلها، دون الحاجة إلى التكرار. وهذا يُحسّن التعقيد الزمني للدمج بمعامل ثابت.

يوضح الرسم البياني أدناه عملية الدمج في Min WBLT.

عمليات أخرى على متن WBLT

يتم إدخال وحذف العنصر الأدنى بنفس الطريقة المتبعة في HBLTs، ويستفيد من عملية الدمج الأسرع.

ومع ذلك، فإن الحد O (log n ) غير مضمون عند حذف عنصر عشوائي من WBLT، حيث قد يتعين تحديث أوزان θ( n ).

إذا كان هذا HBLT، فإن حذف عقدة الورقة اليسرى ذات المفتاح 60 سيستغرق وقتًا O (1) ولن يتطلب أي تغيير في أي قيمة s، نظرًا لأن طول المسار الأيمن للأصل (وبالتالي جميع أسلافه) لا يتغير.

لكن في شجرة WBLT، يتعين علينا تحديث وزن كل سلف إلى الجذر، وهو ما يستغرق O ( n ) في أسوأ الحالات.

المتغيرات

توجد عدة اختلافات في شجرة اليسار الأساسية، والتي تُجري تغييرات طفيفة فقط على الخوارزمية الأساسية:

  • إن اختيار الطفل الأيسر باعتباره الأطول هو اختيار اعتباطي؛ فـ"شجرة اليمين" ستفي بالغرض تمامًا.
  • من الممكن تجنب تبديل الأبناء، ولكن بدلاً من ذلك يتم تسجيل أي ابن هو الأطول (على سبيل المثال، في أقل بت أهمية من قيمة s) واستخدام ذلك في عملية الدمج.
  • يمكن استخدام مقياس آخر غير الارتفاع لتحديد قيمة s التي تُستخدم لتحديد الجانب المراد دمجه معه. على سبيل المثال، يمكن استخدام الوزن (عدد العقد).

مراجع

  1. 1 2 3 "أشجار اليسار" (ملف PDF) . www.google.com . تاريخ الاسترجاع: 31 مايو 2019 .
  2. 1 2 كرين، كلارك أ. (1972)، القوائم الخطية وقوائم الانتظار ذات الأولوية كأشجار ثنائية متوازنة (أطروحة دكتوراه)، قسم علوم الحاسوب، جامعة ستانفورد، ISBN 0-8240-4407-XSTAN - CS-72-259
  3. ↑ سيونغ هون تشو؛ سرتاج ساهني (1996)، "أشجار اليسار المتحيزة الوزنية وقوائم التخطي المعدلة" (ملف PDF) ، مجلة الخوارزميات التجريبية ، 3 : 2، CiteSeerX 10.1.1.13.2962 ، doi : 10.1145/297096.297111 ، S2CID 17789668  
  4. ↑ شونماكرز، بيري (2024). "التحليل المُستهلك للأكوام اليسارية". مبادئ التحقق: تدوير المشهد الاحتمالي . سلسلة محاضرات في علوم الحاسوب. المجلد 15260. سبرينغر. الصفحات 73-84 . arXiv : 2411.11051 . doi : 10.1007/978-3-031-75783-9_3 . ISBN   978-3-031-75782-2.
  5. ↑ ستيوارت، جيمس (25 سبتمبر 1988). "أشجار اليسار" . مشروع الرسومات الديناميكية بجامعة تورنتو . تم الاسترجاع في 31 مايو 2019 .
  6. ↑ تشو، سيونغهون؛ ساهني، سرتاج (سبتمبر 1998). "أشجار اليسار المتحيزة للأوزان وقوائم التخطي المعدلة" . مجلة ACM للخوارزميات التجريبية . 3 2. doi : 10.1145/297096.297111 . ISSN 1084-6654 . S2CID 17789668 .  

للمزيد من القراءة

  • روبرت إي تارجان (1983). هياكل البيانات وخوارزميات الشبكة . سيام. ص 38 – 42. ISBN  978-0-89871-187-5.
  • دينش ب. ميهتا؛ سرتاج ساهني (28 أكتوبر 2004). "الفصل 5: الأشجار اليسارية" . دليل هياكل البيانات وتطبيقاتها . مطبعة سي آر سي. رقم ISBN 978-1-4200-3517-9.