#data_structures #computer_science

עצי AVL

עץ $A V L$ הוא אחד המימושים ל self binary tree שנועד לשמור על גובה העץ במספר מסויים כדי לייעל את זמן החיפוש הבינארי של עץ חיפוש בינארי.
(אמרנו שבמקרה הגרוע עץ בינארי יכול להיות פשוט רשימה מקושרת ואז זמן החיפוש יהיה $O (n)$ כי גובה העץ הוא כמספר האיברים, ואומנם הסדר ממויין אבל אי אפשר לעשות חיפוש בינארי על מבני נתונים שמאוכלסים בזכרון בצורה מקושרת ולא רציפה, כפי שדיברנו למעלה, לא ניתן לגשת אליהם בזמן יעיל מספיק).

אנחנו נלמד על סוגים של עצים מאוזנים בהמשך , אבל בגדול מטרתם כמו $A V L$ שתיכף נדבר גם עליו היא לשמור על גובה העץ חסום במספר מסויים על מנת לייעל את החיפוש וההכנסה.

המימוש של $A V L$ ניתן לנו על ידי George adelson-velsky ו evgenii landis ומכאן גם שמו של העץ.

תזכורת : גובה העץ הוא בעצם מספר הרמות בעץ פחות 1 (לכן עבור קודקוד בלי ילדים גובה העץ הוא 0 ולא 1, אפשר להגדיר את זה גם כמרחק הגדול ביותר בין עלה לשורש, מרחק בעץ = מספר הקשתות בין קודקוד מסויים לשורש).

הגדרת עץ AVL - עץ ייקרא עץ AVL אם הוא עץ בינארי ולכל קודקוד בעץ ההפרש בין גובה תת העץ הימני לתת העץ השמאלי בערך מוחלט הוא לכל היותר אחד.

\forall_{v \in T} : | d (T_{L (v)}) - d (T_{R (v)}) | \leq 1

הבחנה אם בעץ $A V L$ יש קודקוד עם ילד אחד, ילד זה הוא עלה בהכרח.

דוגמאות לעץ $A V L$ תקין:
Pasted image 20220625211738.png
דוגמה לעץ לא מאוזן :
Pasted image 20220625211757.png

משפט : העומק של עץ $A V L$ נסמנו $T$ עם $n$ קודקודים חסום בלוג של מספר הקודקודים , ליתר דיוק

d (T) \leq 1.4404 \log (n + 1) - 1.33 \in O (\log (n))

איך בכלל מוכיחים דבר כזה? אולי אינדוקציה על מספר הקודקודים? הבעיה היא שגובה העץ הוא מספר טבעי אבל הפעלת לוג על מספר הקודקודים לא תיתן לנו מספר טבעי ולכן אנחנו עלולים לקבל מספרים לא נכונים על ידי שימוש באינדוקצייה למשל על 1000 ו 1001 קודקודים נקבל את אותו גובה $12$ כשנעגל אותו למרות שבפועל נקבל מספרים שונים.
כשרוצים להוכיח נכונות של פרמטר מסויים הרבה פעמים קל להוכיח את הפונקצייה ההפיכה על הפרמטר הנגדי בוא משתמשים

למת עזר : עץ $A V L$ בעל גובה $k$ ומספר קודקודים $n$ יקיים

n \geq a^{k} w h e r e : a > 1

כלומר יש יחס אקספוננציאלי בין מספר הקודקודים לעומק העץ .
Pasted image 20220625213749.png

כלומר יש פונקצייה הפיכה בין השניים .

בגלל שזאת פונקצייה הפיכה בין תכונות העץ נוכל להסתכל על הבעיה מזווית אחרת ולהוכיח את למת העזר מה שיגרור באופן מיידי את הטענה המרכזית שלנו.

כעת, על הפרמטר הזה כן נוכל להוכיח באינדוקצייה .
נגדיר $N (k)$ שזה מספר הקודקודים בעץ $A V L$ מינימלי בגובה $k$ (מינימלי אומר שיש בו כמה שפחות קודקודים והוא עדיין avl ושומר על התכונות של עץ כזה והוא גם בגובה הדרוש).

בסיס עבור $k = 0$ יש רק עץ אחד בגובה $0$ וזה עץ עם שורש בלי עלים. לכן $1 = N (0)$ .
עבור $k = 1$ צריך קודקוד אחד בעומק 0 ועוד קודקוד נוסף בעומק 1 , $2 = N (1)$ .
עבור $k = 2$ באותו אופן יתקיים $4 = N (2)$

זה נראה כאילו היחס הוא $N (k) = 2^{k}$ אבל זה לא המצב כי ב $k = 3$ נקבל שמספר הקודקודים בעץ המינימלי הוא $7$ .

באופן כללי, עבור עץ $A V L$ עם גובה $k$ גדול מ $2$ לפחות לאחת מתתי העץ שלו הינו בגובה $k - 1$ מהגדרת $A V L$ . אבל בגלל שזה עץ מינימלי עם $N (k - 1)$ קודקודים, הגובה של התת עץ השני חייב להיות בגובה $k - 2$ (אם היה $k - 1$ ) אז העץ לא היה מינימלי ...
סה״כ כעת אנחנו יודעים שלעץ מינימלי מספר הקודקודים יקיים
$N (k) = N (k - 1) + N (k - 2) + 1$ בידיוק. (הוספנו אחד בגלל השורש).

אנדקדוטה נסתכל על סדרת פיבונצי

F (0) = 0, F (1) = 1 F (i) = F (i - 1) + F (i - 2) for: i \geq 2

ישנו מונח הנקרא יחס הזהב שאומר שכל שני איברים עוקבים בסדרה שואפים אליו , יחס זה הוא $1.618$ . יחס הזהב אני מציע לקרוא פה עוד על יחס הזהב אבל בפשוט יתקיים ששני איברים פיבונאצי מקיים את השיוויון המתואר ששיוויון זה הוא שורשי הפולינום , $x^{2} - x - 1$ ולהם שני פתרונות החיובי זה יחס הזהב:

φ = \frac{1 + \sqrt{5}}{2} = 1.618 a n d \hat{φ} = \frac{1 - \sqrt{5}}{2} = - 0.618

ומתקיים

F (i) = \frac{1}{\sqrt{5}} (φ^{i} - {\hat{φ}}^{i})

בגלל שהשורש השלישי קטן מאחד כשנעלה בחזקה גבוהה במיוחד הוא יהיה זניח (חשוב להמשך).

לא אפרט יותר מדי על המשך ההוכחה אך הקשר בין יש יחס בין עץ avl מינימלי בגובה $k$ לסדרת פיבונצי והוא:

Pasted image 20220625222342.png

נשתמש בזה כדי לתאר קשר כללי :

\begin{matrix} N (k) = \\ N (k - 1) + N (k - 2) + 1 = \\ (F (k + 2) - 1) + (F (k + 1) - 1) + 1 = \\ F (k + 3) - 1 \end{matrix}

וכעת מהקירוב הנ״ל

n \geq F (k + 3) - 1 \approx \frac{1}{\sqrt{5}} φ^{k + 3} - 1 $ $ ב ע צ ם פ ה ה ו כ ח נ ו א ת מ ה ש נ י ס י נ ו ל ה ו כ י ח ב ט ע נ ת ע ז ר ו מ ז ה נ ו צ י א א ת ה ו כ ח ת ה ט ע נ ה ה מ ק ו ר י ת ב א ו פ ן ה ב א $ $ k + 3 \leq \log_{φ} (\sqrt{5} (n + 1))

k \leq \log_{φ} (\sqrt{5} (n + 1)) - 3 \approx 1.4404 \log_{2} (n + 1) - 1.33

כאן דיברנו על עץ avl מינימלי ויתקיים שבמקרה הגרוע עומק של עץ סך הכל גדול יותר ב $44 %$ מהעץ במקרה הטוב ביותר. זה מרמז לנו שחיפוש בעץ מסוג זה הוא יעיל במיוחד ביחס לעצי חיפוש בינאריים שאין לנו הבטחה טובה כמו זו.

הכנסה

עכשיו כשאנחנו יודע שההגבלות על עץ $A V L$ תורמות לנו מבחינת יעילות . אנחנו נרצה לדאוג מבחינת אלגוריתם ההכנסה שלנו לשמר את התכונות של עץ כזה כך שאם נרצה להכניס ערך חדש לעץ , כעת אין לנו חופש בחירה, נצטרך לעבוד טיפה כדי לאזן את העץ ולמקם את הקודקוד בידיוק במקום המתאים ככה שהעץ לא יאבד מאיזונו.

אנחנו נרצה לדעת יותר מידע על כל קודקוד בעץ ולשם כך נגדיר פרמטר חדש לקודקוד . נקרא לו $B F (v) \to Balance Factor of Node v$ והוא יהיה שווה ל

B F (v) = d (T_{R (v)}) - d (T_{L (v)})

במילים זה ההפרש בין גובה תת העץ הימני לגובה תת העץ השמאלי ואנחנו יודעים

B F (v) \in {- 1, 0, 1}

מהגדרת עץ $A V L$ , כל קודקוד יקבל מאזן חיובי אם תת העץ הימני גבוה יותר , 0 אם הם שווים ומינוס אם תת העץ השמאלי גבוה יותר. בצורה ויזואלית זה ייראה כך

Pasted image 20220625232929.png

נגדיר שאם המאזן הוא $0$ אז העץ מאוזן, אחרת הוא לא מאוזן עם נטייה בהתאם לסימן.

כמו כן נניח שעצי $A V L$ נבנים מ $0$ ולא ניתנת מהמרה מעץ שאינו $A V L$ לעץ כזה.

כיוון שעץ $A V L$ יורש מעץ בינארי הליך ההכנסה יתחיל זהה, אם נרצה להכניס ערך נתבונן במסלול שהוא היה אמור לעבור בהליך ההכנסה של עץ בינארי רגיל . למשל עבור העץ הנ״ל עם המספר 31, המסלול יהיה : 51 , 39 , 27 . כעת אנחנו יודעים שעבור קודקוד שלא שייך למסלול הזה כל תתי העץ שלו לא ישנו את המאזן כתוצאה מההכנסה.
במילים אחרות , נרצה לבדוק את המאזן על הקודקודים שבמסלול ההכנסה.
נשאלת השאלה איך אנחנו נסרוק שגיאות לאחר שהגענו לקודקוד האחרון לפני הכנסה בעץ בינארי? הרי לקודקוד אין רפרנס לאביו בעץ... והתשובה פשוטה, נכניס את הקודקודים במסלול ההכנסה ל מחסנית $S$ . כמו כן, על כל איבר שנשמור במחסנית נשמור גם לאיזה כיוון אנחנו ממשיכים במסלול מהנקודה בה אנחנו נמצאים, למשל עבור המסלול דוגמה שלנו : $S = [(v_{20}, R), (v_{52}, L), (v_{39}, L), (v_{27}, R)]$

(נשים לב, מבחינת מימוש בקוד לא בהכרח חייב להשתמש במחסנית, ניתן לממש את הקוד באופן ריקורסיבי כך שברגע שהכנסה מסתיימת נעלה למעלה בהירכייה ונקבל בחינם את המצביעים שעברנו במעלה הדרך , הכל תלוי באיך מימשנו הכנסה של עץ חיפוש בינארי) .

משיטת ההכנסה של #עץ חיפוש בינארי אנחנו יודעים שהקודקוד שייכנס תמיד יהיה עלה. יתרה מכך, אם המאזן של קודקוד האבא שלו הוא 0 סימן שלפני ההכנסה אותו קודקוד אב היה עלה בעצמו.
נסמן את קודקוד האב כ $z$ , אנחנו היודעים שהכנסת קודקוד $v_{x}$ תשנה את מאזר העץ $T_{z}$ (תת העץ ששורשו הוא $z$ ). (למשל הכנסת הערך 15 לעץ שבתמונה למעלה תשנה את המעץ של $T_{17}$ וגם של $T_{12}$ ).

כעת נמשיך לעלות במחסנית ששם נשמר הנתיב שממנו באנו ,

נרוץ על המחסנית ונעדכן את פרמטר המאזן של כל קודקוד במחסנית כל עוד המאזן לפני עדכון הוא $0$ היא תעדכן לפי הפרמטר הנוסף שנמצא במחסנית שמודיע על כיוון ההגעה. אחרי עדכון נוציא מהמחסנית את הקודקוד ונמשיך לקודקוד הבא עד ש:

הגענו לשורש- זה אומר שמאזן כל העץ תקין נעדכן את המאזן של $T$ והוא עדיין שומר על התנאים של עץ $A V L$ .
כשהגענו לעץ לא מאוזן מהצד שמתקן את האיזון, נסביר באמצעות דוגמה ,
נניח שאנחנו מגיעים ל קודקוד $w$ שמאזנו יהיה $B F_{(w)} = -$ ואנחנו מגיעים לקודקוד מצד ימין שלו. במקרה זה (וגם במקרה ההפוך) המאזן של העץ חוזר להיות $0$ שזה מצב תקין . האיטרציה בשלב זה יכולה לעצור ולא צריכה להמשיך לבדוק את שאר הקודקודים במחסנית כיוון שאם המאזן נהיה $0$ לא שינינו את הגובה של תת העץ $T_{w}$ ולכן כל מי שמעליו לא צריך לעבור איזון כי הוא עדיין עומד בתקן $A V L$ כמו מלפני.
כשהגענו לשורש לא מאוזן מהצד ה״כבד יותר״ כלומר, הצד שאם נכניס אליו עוד איבר האיזון יישבר עוד יותר. (למשל בדוגמה למעלה המאזן היה - לפני הכנסה לכן אם נכניס עוד קודקוד לתת העץ השמאלי, המאזן יהיה $- 2$ , מצב שלא תואם את הגדרת העץ.). מבחינה ויזואלית זה ייראה משהו כזה

$T_{δ}$ הינו תת העץ שאליו נכנס הקודקוד, ובקודקוד האבא שלו למעשה, נשבר האיזון.
מסתבר, שהפעולות איזון שצריך לבצע שונות בהתאם לאיזה מתתי העץ של $δ$ מכיל את הקודקוד החדש .
לצערנו הרב, נצטרך לעשות zoom-in פנימה לתוך העץ $T_{δ}$ כדי להבין מה נשבר.

__לפני שנחלק למקרים, אנחנו יודעים להגיב בוודאות ש המאזן לפני הכנסה של $δ$ הוא 0, אם זה לא היה המצב היינו מבצעים את האיזון עוד לפני שהגענו ל $a$ ויוצאים בשלב הזה.

על מנת לסדר את האיזון נצטרך להבין עם איזה מקרה של ״שבירה״ אנחנו מתמודדים, היוצרים של $A V L$ , הציעו אלגוריתם הכולל 4 אפשרויות. :

RRrotarion - זה קיצור של right-right והמשמעות היא שנוצר חוסר איזון משום שתת העץ הימני $T_{δ}$ של השורש $a$ גדול מתת העץ השמאלי של השורש $a$ , ובנוסף תת העץ הימני של $T_{δ}$ נסמנו $T_{r δ}$ גדול מתת העץ השמאלי $T_{l δ}$ .

Pasted image 20220626115449.png

LLrotarion - זה קיצור של left-left והמשמעות היא שנוצר חוסר איזון משום שתת העץ השמאלי $T_{δ}$ של השורש $a$ גדול מתת העץ הימני של השורש $a$ , ובנוסף תת העץ השמאלי של $T_{δ}$ נסמנו $T_{l δ}$ גדול מתת העץ הימני $T_{r δ}$ .

Pasted image 20220626115749.png|350

__את שני המקרים האלו ניתן לפתור על ידי רוטציה בין השורש לבין בנו הימני אם אנחנו ב RR , או בנו השמאלי במקרה שאנחנו ב LL באופן הבא:

לדוגמה , אם $a$ הוא השורש ו $b$ הוא תת העץ השמאלי ויש הפרה מסוג $L L$ אז $b$ יהפוך להיות השורש, $a$ יהפוך להיות תת העץ הימני של $b$ , תת העץ הימני של $b$ יהפוך להיות תת העץ השמאלי של $a$ ,באופן דומה על הצד הימני.
נשמע קצת מבלבל, נדגים ויזואלית
LL :
Pasted image 20220626120750.png

RR :
Pasted image 20220626122849.png

נשים לב שתמיד אנחנו נרצה לאזן את העץ ולשחק עם המשקלים, כלומר תמיד תהיה החלפה של השורש באיזשהו אופן .

LRrotation- זה קיצור של left-right ומצב זה נוצר בגלל ש תת העץ השמאלי של השורש גדול מהימני, ובתוך תת העץ השמאלי עצמו, תת העץ הימני שלו גדול מתת העץ השמאלי שלו, לדוגמה :

Pasted image 20220626123721.png

1. RLrotation- זה קיצור של right-left ומצב זה נוצר בגלל ש תת העץ הימני של השורש גדול מהשמאלי, ובתוך תת העץ הימני עצמו, תת העץ השמאלי שלו גדול מתת העץ הימני שלו, לדוגמה :

שימו לב שזה לא משנה איפה בתת עץ של תת העץ הגדול יותר מכניסים את האיבר כי אין שם שבירה בשני המקרים

את שני המקרים הללו ניתן לפתור על ידי רוטציה כפולה. הרוטצייה תעבוד ככה :

RL - נבצע רוטציית $L L$ בתוך תת העץ הפנימי ולאחר מכן $R R$ על השורש עם בנו הימני.
LR- נבצע רוטציית $R R$ בתוך תת העץ הפנימי ולאחר מכן $L R$ על השורש עם בנו השמאלי

לדוגמא :
Pasted image 20220626130121.png

__באופן דומה עושים על $R L$

ולסיכום
ברגע שהכנסו קודקוד חדש בהכנסה כמו בעץ חיפוש רגיל, עולה במסלול שלנו ובודקים את המאזן , אם הוא $0$ משנים בהתאם למאיפה באנו וממשיכים, אם הוא שונה מ $0$ ובאנו מהמקום שמאזן את זה בחזרה, משנים ל $0$ וממשיכים, אם באנו ממקום שממשיך לשבור את האיזון, מבצעים את אחד האיזונים הנ״ל ויוצאים מהלולאה.


// An AVL tree node
class Node
{
	public:
	int key;
	Node *left;
	Node *right;
	int height;
};

// A utility function to get the
// height of the tree
int height(Node *N)
{
	if (N == NULL)
		return 0;
	return N->height;
}

/* Helper function that allocates a
new node with the given key and
NULL left and right pointers. */
Node* newNode(int key)
{
	Node* node = new Node();
	node->key = key;
	node->left = NULL;
	node->right = NULL;
	node->height = 1; // new node is initially
					// added at leaf
	return(node);
}

// A utility function to right
// rotate subtree rooted with y
Node *rightRotate(Node *y)
{
	Node *x = y->left;
	Node *T2 = x->right;

	// Perform rotation
	x->right = y;
	y->left = T2;

	// Update heights
	y->height = max(height(y->left),
					height(y->right)) + 1;
	x->height = max(height(x->left),
					height(x->right)) + 1;

	// Return new root
	return x;
}

// A utility function to left
// rotate subtree rooted with x
Node *leftRotate(Node *x)
{
	Node *y = x->right;
	Node *T2 = y->left;

	// Perform rotation
	y->left = x;
	x->right = T2;

	// Update heights
	x->height = max(height(x->left),
					height(x->right)) + 1;
	y->height = max(height(y->left),
					height(y->right)) + 1;

	// Return new root
	return y;
}

// Get Balance factor of node N
int getBalance(Node *N)
{
	if (N == NULL)
		return 0;
	return height(N->left) - height(N->right);
}

// Recursive function to insert a key
// in the subtree rooted with node and
// returns the new root of the subtree.
Node* insert(Node* node, int key)
{
	/* 1. Perform the normal BST insertion */
	if (node == NULL)
		return(newNode(key));

	if (key < node->key)
		node->left = insert(node->left, key);
	else if (key > node->key)
		node->right = insert(node->right, key);
	else // Equal keys are not allowed in BST
		return node;

	/* 2. Update height of this ancestor node */
	node->height = 1 + max(height(node->left),
						height(node->right));

	/* 3. Get the balance factor of this ancestor
		node to check whether this node became
		unbalanced */
	int balance = getBalance(node);

	// If this node becomes unbalanced, then
	// there are 4 cases

	// Left Left Case
	if (balance > 1 && key < node->left->key)
		return rightRotate(node);

	// Right Right Case
	if (balance < -1 && key > node->right->key)
		return leftRotate(node);

	// Left Right Case
	if (balance > 1 && key > node->left->key)
	{
		node->left = leftRotate(node->left);
		return rightRotate(node);
	}

	// Right Left Case
	if (balance < -1 && key < node->right->key)
	{
		node->right = rightRotate(node->right);
		return leftRotate(node);
	}

	/* return the (unchanged) node pointer */
	return node;
}

סיבוכיות הכנסה חסומה בגובה העץ שבמקרה הזה הוא חסום בלוג של מספר האיברים, כמו כן הפעולות היו נשמעות מורכבות אבל אפשר לראות בקוד שאלו פעולות הנעשות בזמן ריצה קבוע . לכן סך הכל פעולת ההכנסה חסומה ב $O (l o g n)$ (גם אם נעשה את כל המסלול פעמיים זה עדיין יהיה פעמיים $l o g n$ .)

מחיקה

כמו שדיברנו על #מחיקה בעץ חיפוש, זאת לא בהכרח פעולה סימטרית להכנסה כשמדובר בעץ. הכנסה תמיד מכניסה עלה אבל לא תמיד נרצה למחוק עלה.
נניח שנרצה למחוק קודקוד $v_{x}$ . נמחק אותו כפי שהיינו מוחקים אותו אם היינו עובדים בעץ חיפוש בינארי.
כעת צריך לבדוק את המאזן בכל קודקוד במסלול ממנו באנו ולעדכן בהתאם, לא אפרט פה את הליך הבדיקה כי הוא זהה לנ״ל. ההבדל הוא שיש מקרים שמחיקת איברים תשנה את תהפוך עץ ממצב לא מאוזן תקין למצב מאוזן תקין , דבר שיגרום לגובה העץ לקטון ב 1 ולכן במצב זה צריך לבדוק גם את הקודקוד הבא ולא לעצור כמו שהיינו עושים בהכנסה.

זה סך הכל ההבדל אך בדיקת מקדם האיזון וביצוע הרוטציות יהיה בידיוק אותו דבר. מבחינת פתרון ריקורסיבי זה סך הכל להוסיף עוד 2 שורות לאחר פעולת המחיקה .

לסיכום קצר, העקרון של הוצאה דומה להכנסה במקרה הזה, בדיקה המסלול מלמטה למעלה, אך תנאי העצירה מעט שונים , אם הקטנו את גובה העץ ב $1$ כתוצאה מהמחיקה מה שגרם לעץ במצב לא מאוזן להיות מאוזן יש צורך להמשיך לעלות בעץ עד למצב שבו , בכל מצב אחר כלומר מצב שבו מחקנו והפכנו עץ מאוזן לעץ לא מאוזן תקין או מצב שהעץ לא מאוזן ודורש תיקונים, ניתן לעצור את העלייה בעץ.

Screen Shot 2022-06-26 at 14.14.23.png

הפתרון הריקורסיבי קצת פחות יעיל , למרות שחסומים באותו דבר, נבצע עוד פעולות במצב הריקורסיבי כי אין את תנאי העצירה שדיברתי עליהם, עם זאת, לפעמים עדיף קוד קריא מאשר קוד יעיל, בטח ובטח כשהפעולות חסומות באותו big O .

__גם זמן הריצה של מחיקה הוא $O (l o g n)$