יצאתי לטיול על עץ

לפני שבועיים בערך יצא לי להתראיין לפודקאסט של צרות בהייטק (אל דאגה, אני אעדכן כשהפרק יצא). בפודקאסט נשאלתי מה הוא האלגוריתם האהוב עליי ועניתי ש-BFS. בדיעבד יצא לי לחשוב על זה, ולמרות שאני מאוד אוהבת את BFS, האלגוריתם האהוב עליי הוא בעצם סדרת האלגוריתמים של טיול על עצים, הידועים גם כ-Tree Walk או Tree Traversal.

האלגוריתמים של הליכה על עצים הם אלגוריתמים רקורסיביים קצרצרים ואלגנטיים – לא מפתיע שאני אוהבת אותם, נכון?

מה היא הליכה על עץ?

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

למה יש כמה סוגים על הליכה על עצים?

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

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

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

ניקח את העץ הזה לדוגמא – 

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

הסדר שבו היינו רוצות להדפיס את הצמתים הוא הסדר הבא – 

נשים לב שהסדר בו אנחנו מטיילות על הצמתים הוא תמיד – 

1. הצומת הכי שמאלית בתת עץ השמאלי
2. צומת הורה
3. הצומת הכי שמאלית בתת עץ הימני

אנחנו מתחילות מהצומת השמאלית ביותר (1), מדפיסות את ההורה שלה (4) ואחר כך את האח הימני שלה (6). לאחר מכן אנחנו עוברות להורה הבא בתור (8) ומדפיסות את הצומת השמאלית ביותר בצד הימני שלה (9) וכן הלאה…

אם היינו רוצות להדפיס את כל הערכים בסדר יורד, היינו עושות את הטיול ההפוך בדיוק – מהצומת הגדולה ביותר לצומת הקטנה ביותר.

עכשיו, בואו ניכנס לאלגוריתמים עצמם ונראה איך הקסם הזה קורה.

רגע לפני שצוללות לאלגוריתמים…

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

class TreeNode(Object):
	def __init__(self, val, left, right):
		self.val = val
		self.left = left
		self.right = right

צומת -> הורה -> צומת

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

נתחיל מהאלגוריתם – 

def inorder_walk(node: TreeNode):
	if node:
		inorder_walk(node.left)
		print(node.val)
		inorder_walk(node.right)

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

1. קורא קריאות רקורסיביות עד שהוא מגיע לצומת השמאלית ביותר בתת העץ הנוכחי.
2. מדפיס את הערך של הצומת שהוא הגיע אליה
3. ניגש לתת העץ הימני בעץ הנוכחי, וממנו קורא קריאות רקורסיביות עד שהוא מגיע לצומת השמאלית ביותר.

נריץ את האלגוריתם על העץ לדוגמא שלנו ונראה איך הוא פועל – 

inorder_walk(node[8]):
	inorder_walk(node[4])

inorder_walk(node[4]):
	inorder_walk(node[1])

inorder_walk(node[1]):
	inorder_walk(node[None]) 

inorder_walk(node[None]):
	Node == None

inorder_walk(node[1]):
	inorder_walk(node[None]) → return
	print(1)
	inorder_walk(node[None]) → return


inorder_walk(node[4]):
	inorder_walk(node[1])
	print(4)
	inorder_walk(node[6]) → print 6

inorder_walk(node[8]):
	inorder_walk(node[4])
	print(8)
	inorder_walk(node[20])

inorder_walk(node[20]):
	inorder_walk(node[9]):	

inorder_walk(node[9]):
	inorder_walk(node[None]) → return
	print(9)
	inorder_walk(node[None]) → return

inorder_walk(node[20]):
	inorder_walk(node[9])	
	print(20)
	inorder_walk(node[27])	

inorder_walk(node[27]):
	inorder_walk(node[None]) → return
	print(27)
	inorder_walk(node[None]) → return

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

הורה -> צומת -> צומת

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

האלגוריתם – 

def preorder_walk(node: TreeNode):
	if node:
		print(node.val)
		preorder_walk(node.left)
		preorder_walk(node.right)

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

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

אחד השימושים הנפוצים לאלגוריתם Preorder הוא להעתקה של עץ. כשאנחנו רוצות ליצור שכפול של העץ שקיבלנו עם כל הערכים שלו, נצטרך לייצר Nodes חדשים. כשאנחנו יוצרות Node חדש אנחנו ניתן לו ערך, תת עץ ימני ותת עץ שמאלי – בדיוק הסדר של האלגוריתם.

בואו נראה איך יראה האלגוריתם שכפול שלנו, שמתבסס על ה-preorder_walk –

def deep_copy_tree(node: TreeNode):
	if node:
		val = node.val
		left_sub_tree = deep_copy_tree(node.left)
		right_sub_tree = deep_copy_tree(node.right)
		return TreeNode(val, left_sub_tree, right_sub_tree)

צומת -> צומת -> הורה

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

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

האלגוריתם – 

def postorder_walk(node: TreeNode):
	if node:
		postorder_walk(node.left)
		postorder_walk(node.right)
		print(node.val)

כל האלגוריתמים שציינתי עד כה הם מקרים פרטיים של אלגוריתם DFS – חיפוש עומק.
האלגוריתם האחרון שאני רוצה לדבר עליו הוא אלגוריתם מבוסס BFS. BFS הוא אלגוריתם שלא נחשב באופן רשמי ל-Tree Walk. עם זאת, הוא מאוד שימושי בשאלות אלגוריתמים, אז היה לי חשוב להכניס אותו.

הליכה בשכבות

כל האלגוריתמים ההולכים ה”רשמיים” שדיברנו עליהם עד כה – inorder, postorder, preorder, מטיילים על העץ מלמעלה למטה או מלמטה למעלה. אבל לעצים יש עוד מימד מאוד חשוב שהרבה פעמים נרצה להשתמש בו – השכבות שלו.

הליכה על השכבות של עץ היא הליכה לרוחב – Breadth first. זאת בניגוד להליכה מלמעלה למטה שהיא הליכה לעומק – Depth first.
אנחנו נרצה ללכת על השכבות של העץ במקרים בהם אנחנו מתבקשות לחשב מרחקים מהשורש, לחפש שכבות לא שלמות, או בכל שאלה אחרת שבה אנחנו נשאלות על השכבות של העץ. מניסיוני, יש יותר כאלה מאשר הסוג ההפוך.

אז איך הולכות על השכבות של העץ?

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

האלגוריתם – 

def levels_walk(node: TreeNode):
	nodesQueue = list()
	nodesQueue.append(node)

	while len(nodesQueue) > 0:
		node = nodesQueue.pop(0)
		print(node)
		for child in [node.left, node.right]
				if child:
						nodesQueue.append(child)

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

בואו נריץ דוגמא ונראה איך האלגוריתם עובד.

levels_walk(node[8])
	nodesQueue = [8]
	len(nodesQueue) > 0 → True
	Node = node[8]
	print(8)
	nodesQueue = (node[4], node[20])
	len(nodesQueue) > 0 → True
	node = node[4]
	print(4)
	nodesQueue = (node[20], node[1], node[6])
	len(nodesQueue) > 0 → True
	node = node[20]
	print(20)
	nodesQueue = (node[1], node[6], node[9], node[27])
	len(nodesQueue) > 0 → True
	node = node[1]
	print(1)
	len(nodesQueue) > 0 → True
	node = node[6]
	print(6)
	len(nodesQueue) > 0 → True
	node = node[9]
	print(9)
	len(nodesQueue) > 0 → True
	node = node[27]
	print(27)
	len(nodesQueue) > 0 → False

ההדפסה שקיבלנו היא בדיוק של כל הצמתים בכל שכבה לפי הסדר – 8,4,20,1,6,9,27

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

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

יש עוד אלגוריתמים או סדרות אלגוריתמים מגניבות שהייתן רוצות שאני אעשה עליהן פוסט? תכתבו לי!