شجرة فان إمده بواس

تُجري العملية FindNext(T, x) التي تبحث عن العنصر التالي للعنصر x في شجرة vEB ما يلي: إذا كان x < T.min ، فإن البحث يكون قد اكتمل، والنتيجة هي T.min . إذا كان x ≥ T.max ، فإن العنصر التالي غير موجود، وتُرجع الدالة M. وإلا، تُترك قيمة فارغة.${\displaystyle i=\lfloor x/{\sqrt {M}}\rfloor }$إذا كانت قيمة x أقل من الحد الأقصى للقيمة في T.children[i] ، فإن القيمة المطلوبة موجودة في T.children[i] ، وبالتالي يستمر البحث بشكل متكرر في T.children[i] . وإلا، نبحث عن العنصر التالي للقيمة i في T.aux . وهذا يعطينا فهرس j لأول شجرة فرعية تحتوي على عنصر أكبر من x . ثم تُرجع الخوارزمية الحد الأدنى للقيمة في T.children[j] . يجب دمج العنصر الموجود في مستوى الأبناء مع البتات العليا لتكوين عنصر تالٍ كامل.

دالة FindNext(T, x) إذا كان x < T.min، فأرجع T.min إذا كان x ≥ T.max ، فلا يوجد عنصر تالٍ، فأرجع M i = الجزء الصحيح من (x/${\displaystyle {\sqrt {M}}}$) lo = x mod${\displaystyle {\sqrt {M}}}$إذا كان lo < T.children[i].max ، فقم بإرجاع (${\displaystyle {\sqrt {M}}}$i) + FindNext(T.children[i], lo) j = FindNext(T.aux, i) يعود (${\displaystyle {\sqrt {M}}}$j) + T.children[j].min end

لاحظ أنه في أي حال، فإن الخوارزمية تؤدي${\displaystyle O(1)}$ثم ربما يتكرر على شجرة فرعية على نطاق واسع بحجم${\displaystyle M^{1/2}}$(أن)${\displaystyle m/2}$(عالم البتات). وهذا يعطي تكرارًا لوقت التشغيل لـ${\displaystyle T(m)=T(m/2)+O(1)}$، والذي يُحل إلى${\displaystyle O(\log m)=O(\log \log M)}$.

يتم استدعاء الدالة insert(T, x) التي تُدرج القيمة x في شجرة vEB T على النحو التالي:

1. إذا كانت T فارغة، فإننا نضبط T.min = T.max = x وبذلك نكون قد انتهينا.
2. وإلا، إذا كان x < T.min، فإننا نُدرج T.min في الشجرة الفرعية i المسؤولة عن T.min ، ثم نُعيّن T.min = x . إذا كانت T.children[i] فارغة سابقًا، فإننا نُدرج i أيضًا في T.aux.
3. وإلا، إذا كان x > T.max، فإننا نُدرج x في الشجرة الفرعية i المسؤولة عن x ، ثم نُعيّن T.max = x . وإذا كانت T.children[i] فارغة سابقًا، فإننا نُدرج i أيضًا في T.aux.
4. وإلا، فإن T.min < x < T.max ، لذا نُدرج x في الشجرة الفرعية i المسؤولة عن x . إذا كانت T.children[i] فارغة سابقًا، فإننا نُدرج i أيضًا في T.aux .

في الكود:

دالة Insert(T, x) إذا كان T.min == x أو T.max == x، فهذا يعني أن x قد تم إدخاله بالفعل، وإلا فإن الدالة تُنهي عملها. إذا كان T.min > T.max، فهذا يعني أن T فارغ. T.min = T.max = x; أعد إذا كانت قيمة x أقل من T.min. تبديل(س، الحد الأدنى لـ ت) إذا كانت x > T.max T.max = x i = الجزء الصحيح من (x /${\displaystyle {\sqrt {M}}}$) lo = x mod${\displaystyle {\sqrt {M}}}$ أدخل (T.children[i]، lo) إذا كان الحد الأدنى لـ T.children[i] يساوي الحد الأقصى لـ T.children[i] ، أدخل (T.aux، i) نهاية

يكمن سر كفاءة هذه العملية في أن إدخال عنصر في شجرة vEB فارغة يستغرق وقتًا ثابتًا O (1) . لذا، على الرغم من أن الخوارزمية قد تُجري استدعاءين متكررين في بعض الأحيان، إلا أن هذا يحدث فقط عندما يكون الاستدعاء المتكرر الأول في شجرة فرعية فارغة. وهذا يُعطي نفس زمن التشغيل التكراري لـ ⁠${\displaystyle T(m)=T(m/2)+O(1)}$كما كان من قبل.

يُعدّ حذف البيانات من أشجار vEB من أصعب العمليات. يتم استدعاء الدالة Delete(T, x) لحذف القيمة x من شجرة vEB T على النحو التالي:

1. إذا كان T.min = T.max = x فإن x هو العنصر الوحيد المخزن في الشجرة ونقوم بتعيين T.min = M و T.max = −1 للإشارة إلى أن الشجرة فارغة.
2. وإلا، إذا كانت x تساوي T.min، فسنحتاج إلى إيجاد ثاني أصغر قيمة y في شجرة vEB، وحذفها من موقعها الحالي، وتعيين T.min=y . ثاني أصغر قيمة y هي T.children[T.aux.min].min ، لذا يمكن إيجادها في زمن O (1) . نحذف y من الشجرة الفرعية التي تحتويها.
3. إذا كان x≠T.min و x≠T.max ، فإننا نحذف x من الشجرة الفرعية T.children[i] التي تحتوي على x .
4. إذا كانت x تساوي T.max، فسنحتاج إلى إيجاد ثاني أكبر قيمة y في شجرة vEB وتعيين T.max=y . نبدأ بحذف x كما في الحالة السابقة. عندئذٍ تكون القيمة y إما T.min أو T.children[T.aux.max].max ، لذا يمكن إيجادها في زمن ثابت O (1) .
5. في أي من الحالات المذكورة أعلاه، إذا قمنا بحذف العنصر الأخير x أو y من أي شجرة فرعية T.children[i]، فإننا نحذف أيضًا i من T.aux .

في الكود:

دالة الحذف (T، x) إذا كان T.min == T.max == x ثم T.min = M T.max = −1 إذا كانت x تساوي T.min، فإن hi = T.aux.min *${\displaystyle {\sqrt {M}}}$ j = T.aux.min T.min = x = hi + T.children[j].min i = الجزء الصحيح من (x /${\displaystyle {\sqrt {M}}}$) lo = x mod${\displaystyle {\sqrt {M}}}$ حذف(T.children[i], lo) إذا كانت T.children[i] فارغة ، حذف (T.aux، i) إذا كانت x تساوي T.max، وإذا كانت T.aux فارغة ، T.max = T.min وإلا فإن hi = T.aux.max *${\displaystyle {\sqrt {M}}}$ j = T.aux.max T.max = hi + T.children[j].max نهاية

مرة أخرى، تعتمد كفاءة هذه العملية على حقيقة أن حذف عنصر من شجرة vEB تحتوي على عنصر واحد فقط يستغرق وقتًا ثابتًا. وبالتحديد، لا يتم تنفيذ استدعاء الحذف الثاني إلا إذا كان x هو العنصر الوحيد في T.children[i] قبل الحذف.

إن افتراض أن لوغاريتم m عدد صحيح غير ضروري. العمليات${\displaystyle x{\sqrt {M}}}$و${\displaystyle x{\bmod {\sqrt {M}}}}$يمكن استبدال ذلك بأخذ البتات ذات الرتبة الأعلى ⌈ m /2⌉ والبتات ذات الرتبة الأدنى ⌊ m /2⌋ من x ، على التوالي. على أي جهاز موجود، يكون هذا أكثر كفاءة من عمليات القسمة أو حساب الباقي.

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

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

يستخدم التنفيذ الموصوف أعلاه المؤشرات ويشغل مساحة إجمالية قدرها O ( M ) = O (2m ⁾ ، وهي مساحة تتناسب مع حجم مجموعة المفاتيح. ويمكن توضيح ذلك كما يلي. العلاقة التكرارية هي${\displaystyle S(M)=O({\sqrt {M}})+({\sqrt {M}}+1)\cdot S({\sqrt {M}})}$يمكن إثبات أن S ( M ) = O ( M ) بالاستقراء. ^{[ 4 ]}