|
==מציאת הצומת הבא והקודם==
{{:מבני נתונים ואלגוריתמים - מחברת קורס/מבני נתונים/עצי חיפוש בינריים/מציאת הצומת הבא והקודם}}
===הצמתים ה"חשודים"===
{{להשלים}}
[[תמונה:Dsa binary search tree succ 1.png|מרכז|100%|]]
[[תמונה:Dsa binary search tree succ path up 1.png|מרכז|100%|]]
[[תמונה:Dsa binary search tree succ path up 2.png|מרכז|100%|]]
[[תמונה:Dsa binary search tree succ path up 3.png|מרכז|100%|]]
[[תמונה:Dsa binary search tree succ path up 4.png|מרכז|100%|]]
[[תמונה:Dsa binary search tree succ path up 5.png|מרכז|100%|]]
[[תמונה:Dsa binary search tree succ path up 6.png|מרכז|100%|]]
===היחס בין הצמתים ה"חשודים"===
{{להשלים}}
===פסוודו-קוד===
הפסוודו-קוד הבא מראה כיצד למצוא את הצומת הבא (successor
באנגלית) והקודם (predecessor באנגלית).
<source lang = "python">
# Takes a (pointer to a) node (nd).
# Retuns (a pointer to) the "next" node.
Successor(nd)
1 if nd.r-child != Nil
2 return Min(nd.r_child)
3 parent = nd.parent
4 while parent != Nil and nd == parent.r-child
5 nd = parent
6 parent = parent.parent
7 return parent
# Takes a (pointer to a) node (nd).
# Retuns (a pointer to) the "previous" node.
Predecessor(nd)
1 if nd.l-child != Nil
2 return Max(nd.l_child)
3 parent = nd.parent
4 while parent != Nil and nd == parent.l-child
5 nd = parent
6 parent = parent.parent
7 return parent</source>
{{משפט|תוכן =
סיבוכיות הפעולה היא <math dir = "ltr">\displaystyle \Theta(h)</math> במקרה הגרוע, כאשר <math dir = "ltr">\displaystyle h</math> הוא גובה העץ.}}
==מחיקה==
| 