מצביעים

[~שירה]

מחלקה לייצוג עץ אדום שחור.

בפונקציה לסיבוב ימני ושמאלי, מה צריך לעושת כדי שהשינויים לא ישארו רק בפונקציה אלא ישפיעו על כל העץ???

[בלה]

אני יודע רק בקשר לשיח ירוק וכחול.. אבל אולי זה דומה :-\

כדי שנוכל להבין ולעזור לך את צריכה לנסח את זה בצורה נורמלית..

[~שירה]

עץ אדום שחור הוא סוג של מבנה נתונים (עץ חיפוש בינארי)

יש לי פונקציה בה אני משנה סדר של איברים הקשורים זה בזה, על-מנת לא לאבד קשר עם אף איבר אני מצהירה על משתני עזר <נמחקים ביציאה מהפונקציה>

איך אני גורמת לשמירת השינויים שערכתי?

זה הקוד שכתבתי :

template <class T>
void BRtree<T>::Left(Node<T>*current)
{
	Node<T>* p = current->parent;

	p->right=current->left;
	if(current->parent!=NULL)
	{
		current->parent=current->parent->parent;
	}
	else
	{
		current->parent=NULL;
		root=current;
	}
	current->left=p;
	current->left->right=p->right;
}

[Ghosthunter]

תנסי לשלוח מצביע למצביע.

Node<T>**current

כל פעם תיגשי ל-

(*current)->something

במקום ל-

current->something

[Boomerang]

אין לך שום בעיה (שקשורה להעברת פרמטרים) בפונקציה.

הדבר היחיד שלא נשמר זה הערך של current (כלומר - הכתובת שנמצאת במצביע current), ואת זה את במילא לא עושה בפונקציה.

[Ghosthunter]

כדאי לבדוק אם current->parent!=null לפני שאת עושה

current->parent->right=current->left

[~שירה]

תנסי לשלוח מצביע למצביע.

Node<T>**current

איך אני מצהירה על הפונקציה???

למה הופך:

	void Right(Node<T>*current);

[Ghosthunter]

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

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

ראשית, אני ממליץ לך לבדוק את השורות האלה:

	p->right=current->left;
	if(current->parent!=NULL)

ולראות אם הן בכלל בסדר הנכון.

שנית, תבדקי אם מה שאת עושה בפונ הוא נכון.

לילה טוב אני עייף אין לי כוח לחשוב עכשיו... SRY.

[~שירה]

בלבלת אותי לגמרי!!!!

כרגע לא משנה לי אם הפונקציה פועלת נכון.

השאלה שלי:

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

יש קריאה לפונקציה גלגול לימין על קודקוד בעץ ןלכן הפונקציה תקבל מצביע לקודקוד, איך השינוי שנעשה בפונקציה אכן פועל ומשתנה בעץ עצמו????

[Ghosthunter]

אם אתה משנה את מה שהאבא שלו מצביע עליו, אז זה ישמר.

[~שירה]

הלוואי ותעזרו לי:

רשמתי בתכנית הראשית לולאה להכנסת איברים לעץ:

	BRtree<int> br;

	for(int i=0; i<10; i++)
	{
		br.Add(i+1);
	}

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

מה קןרה פה??? למה הוא לא מכיר את המצביע???????

ככה נראית הפונקציית הוספה:

template <class T>
void BRtree<T>::Add(T val)
{
	Node<T>* current= Insert(val);
	Node<T>* ezer;

	if(current->parent==NULL)
	{
		current=root;
		root->color=1;
		return;
	}
	else
	{
		while((current!=root)&&(current->parent->color==0))
		{
			if(current->parent==current->parent->parent->left)
			{	
				ezer=current->parent->parent->right;
				if(ezer->color==0)
				{
					current->parent->color=1;
					ezer->color=1;
					current->parent->parent->color=0;

					current=current->parent->parent;
				}
				else
				{	
					if(current==current->parent->right)
					{
						current=current->parent;

						Left(current);
					}

					current->parent->color=1;
					current->parent->parent->color=0;

					Left(current->parent->parent);
				}
			}
		}
	root->color=1;
	}
}

[Boomerang]

מה עושה אצלך הפונקציה Insert?

[~שירה]

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

template <class T> 
Node<T>* BRtree<T>::Insert(T val)
{
	if (!root)
	 {
		 root=new Node<T>(val,NULL,NULL,NULL,0);
		 return root;
	 }

	Node<T>*p = root;
	return Insert(root,val,p);
}

template <class T> 
Node<T>* BRtree<T>::Insert(Node<T>*current, T val, Node<T>*p)
{
  if (current->value < val)
    // Add to right subtree
    if (!current->right)
    {
      current->right=new Node<T>(val,NULL,NULL,current,0);
			return current->right;
    }
		else Insert(current->right,val,current);
  else
    // Add to left subtree
    if (!current->left)
    {
      current->left=new Node<T>(val,NULL,NULL,current,0);
      return current->left;
    }
		else Insert(current->left,val,current);
}

כשאני מסתכלת בפונקציה ADD אחרי הוספת האיבר השלישי הוא אכן מחובר לעץ ROOT מצביע אליו, רק CURRENT שאמור להצביע לאיבר החדש לא מצביע.

????????????????????????????

[Ghosthunter]

לא נכנסתי לקוד שלך לעומק, אבל שמתי לב שהגדרת שם Node<T> *p, ואת לא משתמשת בו.

בקשר להוספה:

 
	if(current->parent==NULL)
	{
		current=root;

למה את עושה current = root? מובטח לך שהוא יהייה השורש, מכיוון שהאבא שלו הוא NULL(ככה עשית את זה בפונ Insert).

ולבסוף:

			if(current->parent==current->parent->parent->left)

מה קורה אם current->parent->parent הוא NULL?(אם current הוא הבן של השורש).

[~שירה]

1. לא משתמשת במצביע Node<T> *p בטעות.

2. נכון, שיניתי, זה הקוד המתוקן:

template <class T>
void BRtree<T>::Add(T val)
{
	Node<T>* current;
	Insert(val);
	current=includes(root,val);
	Node<T>*ezer;

	if(current->parent==NULL)
	{
		current=root;
		root->color=1;
		return;
	}
	else
	{
		while((current!=root)&&(current->parent->color==0))
		{
			if(current->parent==current->parent->parent->left)
			{
				ezer=current->parent->parent->right;
				if((ezer!=NULL)&&(ezer->color==0))
				{
					current->parent->color=1;
					ezer->color=1;
					current->parent->parent->color=0;

					current=current->parent->parent;
				}
				else
				{	
					if(current==current->parent->right)
					{
						current=current->parent;

						Left(current);
					}

					else
					{
						current->parent->color=1;
						current->parent->parent->color=0;

						Right(current->parent);
					}
				}
			}
			else
			{
				ezer=current->parent->parent->left;
				if((ezer!=NULL)&&(ezer->color==0))
				{
					current->parent->color=1;
					ezer->color=1;
					current->parent->parent->color=0;

					current=current->parent->parent;
				}
				else
				{	
					if(current==current->parent->left)
					{
						current=current->parent;

						Right(current);
					}
					else
					{
						current->parent->color=1;
						current->parent->parent->color=0;

						Left(current->parent);
					}
				}
			}
		}	root->color=1;
	}

}

ואלו הפוונקציות גלגול:

template <class T>
void BRtree<T>::Right(Node<T>*current)
{//current->x
	Node<T>*ezer=current->parent;

	if(current->right!=NULL)
	{
		ezer->left=current->right;
	}
	else
	{
		ezer->left=NULL;
	}

	current->right= ezer;

	if(ezer->parent==NULL)
	{
		current->parent=NULL;
	}
	else
	{
		current->parent=ezer->parent;
		if(ezer->parent->right==ezer)
		{
			ezer->parent->right=current;
		}
		else
		{
			ezer->parent->left=current;
		}
	}

	ezer->parent=current;

	if(current->parent==NULL)
	{
		root=current;
	}
}

template <class T>
void BRtree<T>::Left(Node<T>*current)
{//current=y
	Node<T>*ezer=current->parent;

	if(current->left!=NULL)
	{
		ezer->right=current->left;
	}
	else
	{
		ezer->right=NULL;
	}

	current->left= ezer;

	if(ezer->parent==NULL)
	{
		current->parent=NULL;
	}
	else
	{
		current->parent=ezer->parent;
		if(ezer->parent->right==ezer)
		{
			ezer->parent->right=current;
		}
		else
		{
			ezer->parent->left=current;
		}
	}

	ezer->parent=current;

	if(current->parent==NULL)
	{
		root=current;
	}
}