شجرة كبش الفداء

تتميز أشجار كبش الفداء بتوازن غير دقيق في الارتفاع، حيث يبلغ ارتفاعها على الأكثر${\displaystyle \lfloor \log _{1/\alpha }n\rfloor }$، وهو${\displaystyle O(\log n)}$بشرط أن تكون قيمة α بين 0.5 و 1. تكون تكلفة إيجاد نقطة الإدخال ووضع العقدة محدودة بالارتفاع، وهو${\displaystyle O(\log n)}$بعد عملية الإضافة، قد تتم إعادة التوازن، وقد تصل التكلفة إلى${\displaystyle O(n)}$سنوضح الآن أن تكلفة إعادة التوازن يتم استهلاكها${\displaystyle O(\log n)}$لكل عملية إدخال.

يُعرَّف عدم توازن العقدة v بأنه القيمة المطلقة للفرق في الحجم بين عقدتها اليسرى وعقدتها اليمنى ناقص 1، أو 0، أيهما أكبر. بعبارة أخرى:

${\displaystyle I(v)=\operatorname {max} (|\operatorname {left} (v)-\operatorname {right} (v)|-1,0)}$

بالإضافة إلى ذلك، نُعرّف عدم توازن الشجرة الفرعية بأنه مجموع عدم توازن العقد في الشجرة الفرعية.

اللمة 1: مباشرة قبل إعادة بناء الشجرة الفرعية المتجذرة في${\displaystyle v}$، ${\displaystyle I(v)\in \Omega (|v|)}$ ($أوميغا$( تدوين أوميغا الكبيرة .)

دليل:

بحسب التعريف، فإن عقدة كبش الفداء ليست متوازنة الوزن ألفا، وبالتالي فإن حجم الشجرة الفرعية التابعة لها لا يقل عن${\displaystyle \alpha |v|}$ويكون حجم الشجرة الفرعية الشقيقة على الأكثر${\displaystyle (1-\alpha )|v|}$عدم توازن العقدة${\displaystyle v}$ثم${\displaystyle I(v)\geq |\alpha |v|-(1-\alpha )|v||-1=|2\alpha -1||v|-1}$و${\displaystyle \alpha >0.5}$ثابت ثابت،${\displaystyle I(V)=\Omega (|V|)}$وبالتالي، فإن عدم توازن الشجرة الفرعية المتجذرة في${\displaystyle v}$وهو أيضًا${\displaystyle \Omega (|V|)}$.

اللمة 2: مباشرة بعد إعادة بناء شجرة فرعية متجذرة في${\displaystyle v}$،${\displaystyle I(v)=0}$.

دليل:

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

النظرية 3: التكلفة المستهلكة للإدراج هي${\displaystyle O(\log n)}$.

دليل:

مثل أي${\displaystyle O(|v|)}$إعادة البناء تقلل${\displaystyle I(v)}$بواسطة${\displaystyle \Omega (|v|)-0=\Omega (|v|)}$بحسب اللمتين 1 و2، فإن تكلفة إصلاح كل وحدة من وحدات عدم التوازن هي

${\displaystyle {O(|v|) \over \Omega (|v|)}=O(1)}$.

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

${\displaystyle O(\log n)O(1)=O(\log n)}$.

وبإضافة تكاليف مرحلة البحث الأولية وإعادة التوازن، تصبح التكلفة المستهلكة للإدراج هي

${\displaystyle O(\log n)+O(\log n)=O(\log n)}$.

ينطبق هذا الحد على جميع القيم 0.5 < α < 1.

لنفترض أن شجرة كبش الفداء تحتوي على${\displaystyle n}$تم إعادة بناء العناصر للتو (بمعنى آخر، إنها شجرة ثنائية كاملة). على الأكثر${\displaystyle n/2-1}$يمكن إجراء عمليات الحذف قبل إعادة بناء الشجرة. تستغرق كل عملية حذف من هذه العمليات وقتًا.${\displaystyle O(\log n)}$الوقت (مقدار الوقت اللازم للبحث عن العنصر ووضع علامة عليه كمحذوف).${\displaystyle n/2}$يؤدي الحذف إلى إعادة بناء الشجرة ويأخذ${\displaystyle O(\log n)+O(n)}$(أو فقط)${\displaystyle O(n)}$) الوقت. باستخدام التحليل الإجمالي، يتضح أن التكلفة المستهلكة للحذف هي${\displaystyle O(\log n)}$:

${\displaystyle {\sum _{1}^{n/2}O(\log n)+O(n) \over n/2}={{n \over 2}O(\log n)+O(n) \over n/2}=O(\log n)\ }$