تريب

في علم الحاسوب ، تُعدّ شجرة البحث الثنائية العشوائية وشجرة البحث الثنائية المُرتبة شكلين متقاربين من هياكل بيانات شجرة البحث الثنائية ، حيث تحتفظان بمجموعة ديناميكية من المفاتيح المرتبة وتتيحان عمليات بحث ثنائية بين هذه المفاتيح. بعد أي سلسلة من عمليات إدخال وحذف المفاتيح، يصبح شكل الشجرة متغيرًا عشوائيًا له نفس التوزيع الاحتمالي لشجرة ثنائية عشوائية؛ وعلى وجه الخصوص، باحتمالية عالية ، يتناسب ارتفاعها مع لوغاريتم عدد المفاتيح، بحيث تستغرق كل عملية بحث أو إدخال أو حذف وقتًا لوغاريتميًا.

وصف

كومة ذات مفتاح أبجدي وترتيب كومة رقمي أقصى

وُصفت شجرة التريب لأول مرة من قِبل رايموند سايدل وسيسيليا ر. أراغون عام ١٩٨٩؛ ^{[ ١ ]}^{[ ٢ ]} واسمها مُشتق من كلمتي "شجرة" و "كومة" . وهي شجرة ديكارتية يُعطى فيها كل مفتاح أولوية عددية (مُختارة عشوائيًا). وكما هو الحال في أي شجرة بحث ثنائية، فإن ترتيب اجتياز العقد هو نفسه ترتيب المفاتيح. ويُحدد هيكل الشجرة بشرط أن تكون مُرتبة ترتيبًا كوميًا: أي أن رقم أولوية أي عقدة غير طرفية يجب أن يكون أكبر من أو يساوي أولوية أبنائها. وبالتالي، وكما هو الحال في الأشجار الديكارتية بشكل عام، فإن العقدة الجذرية هي العقدة ذات الأولوية القصوى، وتتشكل شجرتاها الفرعيتان اليمنى واليسرى بنفس الطريقة من التسلسلات الفرعية ذات الترتيب المُرتب على يسار ويمين تلك العقدة.

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

يقترح أراغون وسيدل أيضًا إعطاء أولوية أعلى للعُقد التي يتم الوصول إليها بشكل متكرر، وذلك على سبيل المثال من خلال عملية تختار، عند كل وصول، رقمًا عشوائيًا وتستبدل أولوية العقدة بهذا الرقم إذا كانت أعلى من الأولوية السابقة. سيؤدي هذا التعديل إلى فقدان الشجرة لشكلها العشوائي؛ فبدلاً من ذلك، ستكون العُقد التي يتم الوصول إليها بشكل متكرر أكثر احتمالًا أن تكون قريبة من جذر الشجرة، مما يجعل البحث عنها أسرع.

يصف ناور ونسيم ^{[ 3 ]} تطبيقًا في الحفاظ على شهادات التفويض في أنظمة التشفير ذات المفتاح العام .

العمليات

العمليات الأساسية

تدعم Treaps العمليات الأساسية التالية:

للبحث عن قيمة مفتاح معينة، قم بتطبيق خوارزمية بحث ثنائية قياسية في شجرة بحث ثنائية، مع تجاهل الأولويات.
لإدراج مفتاح جديد x في الشجرة، يتم توليد أولوية عشوائية y لـ x . ثم يتم البحث الثنائي عن x في الشجرة، وإنشاء عقدة جديدة في موضع الورقة حيث يحدد البحث الثنائي وجود عقدة لـ x . بعد ذلك، طالما أن x ليس جذر الشجرة وله أولوية أكبر من والده z ، يتم إجراء تدوير للشجرة يعكس علاقة الأب والابن بين x و z .
لحذف عقدة x من الشجرة، إذا كانت x ورقة، فاحذفها ببساطة. إذا كان لـ x ابن واحد z ، فاحذف x من الشجرة واجعل z ابنًا لأب x (أو اجعل z جذر الشجرة إذا لم يكن لـ x أب). أخيرًا، إذا كان لـ x ابنان، فبدّل موقعه في الشجرة مع موقع خليفته المباشر z بالترتيب المُرتّب، ما ينتج عنه إحدى الحالتين السابقتين. في هذه الحالة الأخيرة، قد يُخلّ التبديل بخاصية ترتيب الكومة لـ z ، لذا قد يلزم إجراء عمليات تدوير إضافية لاستعادة هذه الخاصية.

بناء حصن

لبناء شجرة ثلاثية، يمكننا ببساطة إدخال n قيمة في الشجرة الثلاثية حيث تأخذ كل قيمة منها $O(\log n)$ مع مرور الوقت. لذلك يمكن بناء ملجأ في $O(n\log n)$ الوقت من قائمة القيم.

عمليات بالجملة

بالإضافة إلى عمليات الإدراج والحذف والبحث لعنصر واحد، تم تعريف العديد من العمليات السريعة "الجماعية" على جداول البيانات: الاتحاد والتقاطع وفرق المجموعات . وتعتمد هذه العمليات على عمليتين مساعدتين، وهما التقسيم والضم .

لتقسيم شجرة ثلاثية إلى شجرتين أصغر، إحداهما أصغر من المفتاح x والأخرى أكبر منه ، أدخل x في الشجرة ذات الأولوية القصوى - أي ذات أولوية أعلى من أي عقدة في الشجرة. بعد هذا الإدخال، ستكون x هي العقدة الجذرية للشجرة، وستُوجد جميع القيم الأصغر من x في الشجرة الفرعية اليسرى، وجميع القيم الأكبر من x في الشجرة الفرعية اليمنى. تُكلّف هذه العملية نفس تكلفة إدخال واحد في الشجرة.
بدمج مجموعتين من الكومات ناتجتين عن انقسام سابق، يمكننا افتراض أن أكبر قيمة في المجموعة الأولى أقل من أصغر قيمة في المجموعة الثانية. أنشئ عقدة جديدة بقيمة x ، بحيث تكون x أكبر من أكبر قيمة في المجموعة الأولى وأصغر من أصغر قيمة في المجموعة الثانية، ثم امنحها أقل أولوية، واجعل ابنها الأيسر مرتبطًا بالمجموعة الأولى وابنها الأيمن مرتبطًا بالمجموعة الثانية. قم بتدوير العقد حسب الحاجة لتصحيح ترتيب المجموعات. بعد ذلك، ستصبح عقدة طرفية، ويمكن حذفها بسهولة. والنتيجة هي دمج مجموعتين من الكومات الأصلية. هذا يُعدّ فعليًا "إلغاءً" للانقسام، وتكلفته هي نفسها. بشكل عام، يمكن تطبيق عملية الدمج على مجموعتين من الكومات ومفتاح ذي أولوية عشوائية (أي ليس بالضرورة أن تكون الأعلى).

{\displaystyle T_{1}} — تم أداء الانضمام على الترامبولين $T_{1}$ و $T_{2}$ الابن الشرعي لـ $T_{1}$ بعد تعريف عملية الربط على أنها ربط لابنها الأيمن السابق و $T_{2}$ .

خوارزمية الربط هي كالتالي:

دالة join(L, k, R) إذا كان prior(k, k(L)) و prior(k, k(R)) تُرجع Node(L, k, R) إذا كان prior(k(L), k(R)) تُرجع Node(left(L), k(L), join(right(L), k, R)) تُرجع Node(join(L, k, left(R)), k(R), right(R))

{\displaystyle T} — للتقسيم $T$ بواسطة $x$ ، يتم إجراء استدعاء التقسيم المتكرر إما إلى الابن الأيسر أو الأيمن لـ $T$ .

خوارزمية التقسيم هي كالتالي:

دالة split(T, k) إذا كان (T = nil) تُرجع (nil, false, nil) (L, (m, c), R) = expose(T) إذا كان (k = m) فأرجع (L، صحيح، R) إذا كان (k < m) (L', b, R') = split(L, k) أرجع (L', b, join(R', m, R)) إذا كان (k > m) (L', b, R') = split(R, k) return (join(L, m, L'), b, R'))

اتحاد مجموعتين من نوع treap $، t1$ $و$ t2 $، تمثلان$ المجموعتين $A$ و $B،$ هو مجموعة treap $t$ تمثل $A \cup B.$ وتحسب الخوارزمية التكرارية التالية هذا الاتحاد:

دالة الاتحاد (t1 _، t2 ₎ : إذا كان _t1 = nil: أرجع t2 _.إذا كان _t2 = nil: أرجع t1 _.إذا كانت أولوية (t1 ₎ < أولوية (t2 ₎ : بدّل t1 و _t2. t _<_، t _> ← قسّم t2 _على المفتاح (t1 ₎ . أرجع دالة الاتحاد (الاتحاد (يسار (t1 ₎ ، t _< )، المفتاح (t1 ₎ ). اتحاد (يمين (t ₁ ), t _> ))

هنا، يُفترض أن تُعيد دالة split شجرتين: إحداهما تحتوي على المفاتيح الأقل من مفتاح الإدخال، والأخرى تحتوي على المفاتيح الأكبر. (الخوارزمية غير مُتلفة ، ولكن توجد نسخة مُتلفة في مكانها أيضًا).

خوارزمية التقاطع مشابهة، لكنها تتطلب روتين المساعدة للضم . تعقيد كل من الاتحاد والتقاطع والفرق هو $O (m log(n / m + 1))$ لمجموعات من الأحجام $m$ و $n$ ، حيث $m \leq n . علاوة على ذلك$ $،$ بما أن الاستدعاءات المتكررة للاتحاد مستقلة عن بعضها البعض، فيمكن تنفيذها بالتوازي . ^{[ 4 ]}

تقوم الدالتان Split و Union باستدعاء Join ولكنهما لا تتعاملان مع معايير موازنة treaps بشكل مباشر، وعادة ما يطلق على هذا النوع من التنفيذ اسم التنفيذ "القائم على join" .

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

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

لنفترض أن $d$ هو حجم الفرق المتناظر. عندئذٍ، ستكون خوارزميات الدمج المعدلة محدودة أيضًا بـ $O (d log ⁠ n / d ⁠)$ . ^{[ 5 ]}^{[ 6 ]}

شجرة البحث الثنائية العشوائية

شجرة البحث الثنائية العشوائية، التي قدمها مارتينيز وروورا لاحقًا لعمل أراغون وسيدل على الأشجار، ^{[ 7 ]} تخزن نفس العقد بنفس التوزيع العشوائي لشكل الشجرة، ولكنها تحتفظ بمعلومات مختلفة داخل عقد الشجرة من أجل الحفاظ على بنيتها العشوائية.

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

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

مقارنة

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

على الرغم من أن كلاً من شجرة البحث الثنائية العشوائية وشجرة البحث الثنائية المتسلسلة (treap) تشتركان في نفس التوزيع العشوائي لأشكال الأشجار بعد كل تحديث، إلا أن تاريخ التعديلات التي تُجرى على الأشجار بواسطة هاتين البنيتين البيانيتين خلال سلسلة من عمليات الإضافة والحذف قد يختلف. على سبيل المثال، في شجرة البحث الثنائية المتسلسلة، إذا أُضيفت الأرقام 1 و2 و3 بالترتيب 1 و3 و2، ثم حُذف الرقم 2، فإن العقدتين المتبقيتين ستحتفظان بنفس علاقة الأب والابن التي كانت بينهما قبل إضافة الرقم الأوسط. أما في شجرة البحث الثنائية العشوائية، فإن احتمالية أن تكون الشجرة بعد الحذف إحدى الشجرتين المحتملتين على عقدتيها متساوية، بغض النظر عن شكل الشجرة قبل إضافة الرقم الأوسط.

خيانة ضمنية

التريب الضمني ^{[ 8 ]} هو شكل بسيط من أشكال التريب العادي، ويمكن اعتباره مصفوفة ديناميكية تدعم العمليات التالية في $O(\log n)$ :

إدراج عنصر في أي موضع
إزالة عنصر من أي موضع
إيجاد مجموع أو أصغر أو أكبر عنصر في نطاق معين.
بالإضافة إلى ذلك، الرسم في نطاق معين
عكس العناصر في نطاق معين

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

القيمة الرئيسية ( المفتاح الضمني) للعقدة T هي عدد العقد الأقل منها زائد واحد. لاحظ أن هذه العقد قد توجد ليس فقط في شجرتها الفرعية اليسرى، بل أيضًا في الأشجار الفرعية اليسرى لأسلافها P، إذا كانت T موجودة في الشجرة الفرعية اليمنى لـ P.

لذلك، يمكننا حساب المفتاح الضمني للعقدة الحالية بسرعة أثناء تنفيذ عملية ما، وذلك بتجميع مجموع جميع العقد أثناء نزولنا في الشجرة. لاحظ أن هذا المجموع لا يتغير عند زيارة الشجرة الفرعية اليسرى، ولكنه سيزداد بمقدار $cnt(T\rightarrow L)+1$ عندما نزور الشجرة الفرعية الصحيحة.

ضع في اعتبارك التعريف التالي:

استيراد std ؛class ImplicitTreap { private : int key ; int prior ; ImplicitTreap * left ; ImplicitTreap * right ; public : explicit ImplicitTreap ( int key = 0 , int prior = std :: rand ()) : key { key }, prior { std :: rand () }, left { nullptr }, right { nullptr } {}// دوال الوصولint count () const ; void updateCount (); void join ( ImplicitTreap * left , ImplicitTreap * right ); void split ( ImplicitTreap *& left , ImplicitTreap *& right ; int key , int add = 0 ); };

خوارزمية الربط لـ treap الضمني هي كما يلي: ^{[ 8 ]}

void ImplicitTreap::join ( ImplicitTreap * left , ImplicitTreap * right ) { if ( ! left || ! right ) { this = left ? left : right ; } else if ( left -> getPrior () > right -> getPrior ()) { left -> getRight (). join ( left -> getRight , right ); this = left ; } else { right -> getLeft (). join ( left , right -> getLeft ()); this = right ; } updateCount (); }

خوارزمية التقسيم لعملية التريب الضمنية هي كما يلي: ^{[ 8 ]}

void ImplicitTreap::split ( ImplicitTreap *& left , ImplicitTreap * & right , int key , int add = 0 ) { int currentKey = add + this- > left.count (); // مفتاح ضمني if ( key <= currentKey ) { this- > left.split ( left , this- > left , key , add ) ; right = this ; } else { this- > right.split ( this- > right , right , key , add + 1 + this- > left.count ( ) ) ; left = this ; } updateCount ( ) ; }

العمليات

إدراج عنصر

لإدراج عنصر في الموضع pos، نقسم المصفوفة إلى قسمين فرعيين [0...pos-1] و [pos..sz] عن طريق استدعاء دالة split ، فنحصل على شجرتين. $T1$ و $T2$ ثم نقوم بالدمج $T1$ مع العقدة الجديدة عن طريق استدعاء دالة الربط . وأخيرًا، نستدعي دالة الربط لدمج العقدة الجديدة. $T1$ و $T2$ .

حذف العنصر

نجد العنصر المراد حذفه ونقوم بعملية ربط على أبنائه L و R. ثم نستبدل العنصر المراد حذفه بالشجرة الناتجة عن عملية الربط.

أوجد المجموع أو القيمة الصغرى أو القيمة العظمى في نطاق معين

لإجراء هذه العملية الحسابية، سنتبع الخطوات التالية:

سننشئ أولًا حقلًا إضافيًا F لتخزين قيمة الدالة المستهدفة للنطاق الذي تمثله تلك العقدة. سننشئ دالة تحسب القيمة F بناءً على قيم الأبناء L و R للعقدة. سنستدعي هذه الدالة المستهدفة في نهاية جميع الدوال التي تُعدّل الشجرة، أي دالتي split و join.
ثانيًا، نحتاج إلى معالجة استعلام لنطاق معين [A..B]: سنستدعي دالة split مرتين ونقسم treap إلى $T1$ والذي يحتوي $\{1..A-1\}$ ، $T2$ والذي يحتوي $\{A..B\}$ ، و $T3$ والذي يحتوي $\{B+1..n\}$ بعد الإجابة على الاستعلام، سنقوم باستدعاء دالة الربط مرتين لاستعادة الشجرة الأصلية.

الإضافة/الرسم في نطاق معين

لإجراء هذه العملية، سنتبع الخطوات التالية:

سننشئ حقلاً إضافياً D يحتوي على القيمة المضافة للشجرة الفرعية. سننشئ دالة push لنقل هذا التغيير من عقدة إلى أبنائها. سنستدعي هذه الدالة في بداية جميع الدوال التي تُعدّل الشجرة، مثل split و join، لضمان عدم فقدان المعلومات بعد أي تغييرات تُجرى على الشجرة.

عكس في نطاق معين

لإثبات أن الشجرة الفرعية لعقدة معينة تحتاج إلى عكس لكل عقدة، سننشئ حقلاً منطقياً إضافياً R ونضبط قيمته على "صحيح". ولنشر هذا التغيير، سنبدل أبناء العقدة ونضبط قيمة R على "صحيح" لجميعهم.

انظر أيضاً

مراجع

↑ أراغون، سيسيليا ر.؛ سيدل، رايموند (1989)، "أشجار البحث العشوائية" (ملف PDF) ، الندوة السنوية الثلاثون حول أسس علوم الحاسوب ، واشنطن العاصمة: مطبعة جمعية مهندسي الكهرباء والإلكترونيات، الصفحات 540-545 ، doi : 10.1109/SFCS.1989.63531 ، ISBN 0-8186-1982-1
↑ سيدل، رايموند؛ أراغون، سيسيليا ر. (1996)، "أشجار البحث العشوائية" ، Algorithmica ، 16 (4/5): 464–497 ، doi : 10.1007/BF01940876
↑ ناور، م .؛ نسيم، ك. (أبريل 2000)، "إلغاء الشهادة وتحديثها" (ملف PDF) ، مجلة IEEE للمجالات المختارة في الاتصالات ، 18 (4): 561-570 ، doi : 10.1109/49.839932 ، S2CID 13833836 .
↑ بليلوخ، جاي إي؛ ريد-ميلر، مارغريت (1998)، "عمليات سريعة على المجموعات باستخدام الخوارزميات المتوازية"، وقائع الندوة السنوية العاشرة لجمعية ACM حول الخوارزميات والهياكل المتوازية - SPAA '98 ، نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM، الصفحات 16-26 ، doi : 10.1145/277651.277660 ، ISBN 0-89791-989-0، S2CID 7342709 .
↑ ليليينزين، أولي (2013). "المجموعات والخرائط المستمرة بشكل متداخل". arXiv : 1301.3388 . Bibcode : 2013arXiv1301.3388L .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=
↑ مجموعات وخرائط Confluent على GitHub
↑ مارتينيز، كونرادو؛ رورا، سلفادور (1997)، "أشجار البحث الثنائية العشوائية" ، مجلة ACM ، 45 (2): 288-323 ، doi : 10.1145/274787.274812 ، S2CID 714621
1 2 3 "Treap - خوارزميات البرمجة التنافسية" . cp-algorithms.com . تم الاطلاع عليه بتاريخ 21-11-2021 .

روابط خارجية

مجموعة من المراجع والمعلومات حول treap من إعداد سيسيليا أراغون
هياكل البيانات المفتوحة - القسم 7.2 - Treap: شجرة بحث ثنائية عشوائية ، بات مورين
ترنيمة متحركة مؤرشفة بتاريخ 15 مارس 2005 على موقع Wayback Machine
أشجار البحث الثنائية العشوائية . ملاحظات محاضرة من دورة يقدمها جيف إريكسون في جامعة إلينوي في أوربانا-شامبين. على الرغم من العنوان، فإن هذه المحاضرة تتناول بشكل أساسي أشجار البحث الثنائية العشوائية وقوائم التخطي ؛ أما أشجار البحث الثنائية العشوائية فتُذكر بإيجاز شديد.
مخزن قيم مفتاحية عالي الأداء يعتمد على treap من تصميم جوني صن
تنفيذ خوارزمية Treaps باستخدام VB6 . تنفيذ خوارزمية Treaps باستخدام Visual Basic 6 ككائن COM.
تطبيق ActionScript3 لـ treap
treap و duptreap في الذاكرة باستخدام لغة بايثون وسيثون فقط
Treaps في لغة C# . بقلم روي كليمونز
خوارزميات Go خالصة في الذاكرة، غير قابلة للتغيير
مكتبة تخزين القيم المفتاحية الدائمة treap بلغة Go النقية

[paper89-1] أراغون، سيسيليا ر.؛ سيدل، رايموند (1989)، "أشجار البحث العشوائية" (ملف PDF) ، الندوة السنوية الثلاثون حول أسس علوم الحاسوب ، واشنطن العاصمة: مطبعة جمعية مهندسي الكهرباء والإلكترونيات، الصفحات 540-545 ، doi : 10.1109/SFCS.1989.63531 ، ISBN 0-8186-1982-1

[paper96-2] سيدل، رايموند؛ أراغون، سيسيليا ر. (1996)، "أشجار البحث العشوائية" ، Algorithmica ، 16 (4/5): 464–497 ، doi : 10.1007/BF01940876

[3] ناور، م .؛ نسيم، ك. (أبريل 2000)، "إلغاء الشهادة وتحديثها" (ملف PDF) ، مجلة IEEE للمجالات المختارة في الاتصالات ، 18 (4): 561-570 ، doi : 10.1109/49.839932 ، S2CID 13833836 .

[4] بليلوخ، جاي إي؛ ريد-ميلر، مارغريت (1998)، "عمليات سريعة على المجموعات باستخدام الخوارزميات المتوازية"، وقائع الندوة السنوية العاشرة لجمعية ACM حول الخوارزميات والهياكل المتوازية - SPAA '98 ، نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM، الصفحات 16-26 ، doi : 10.1145/277651.277660 ، ISBN 0-89791-989-0، S2CID 7342709 .

[5] ليليينزين، أولي (2013). "المجموعات والخرائط المستمرة بشكل متداخل". arXiv : 1301.3388 . Bibcode : 2013arXiv1301.3388L .{{cite journal}}يتطلب الاستشهاد بالمجلة ( مساعدة )|journal=

[Confluent_Sets_and_Maps-6] مجموعات وخرائط Confluent على GitHub

[7] مارتينيز، كونرادو؛ رورا، سلفادور (1997)، "أشجار البحث الثنائية العشوائية" ، مجلة ACM ، 45 (2): 288-323 ، doi : 10.1145/274787.274812 ، S2CID 714621

[:0-8] 1 2 3 "Treap - خوارزميات البرمجة التنافسية" . cp-algorithms.com . تم الاطلاع عليه بتاريخ 21-11-2021 .

[ ١ ]

[ ٢ ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]