בעברית' פרק 1 דף2 C++ ללמוד'

דף הבית >>רקורסיות>>תכונות הרקורסיה>>עץ בינארי

עץ בינארי הוא מבנה נתונים אשר החיפוש בו מתבצע בצורה הרבה יותר מהירה. בכדי להבין מהוא עץ בינארי נבצע הדגמה של הכנסת נתונים . לפי הסדר הבא מימין לשמאל: 76,20,6,81,19,21,65,32,72,25.

בהתחלה מכניסים 25 הנקרא שורש מכיוון שהוא הראשון.לאחר מכן באים להכניס את המספר 72 ,בודקים את גודלו .אם הוא גדול מן השורש ,הוא נכנס מימינו;אם הןא קטן ממנו ,הוא נכנס משמאלו . מכוון ש72 גדול מ25 הוא נכנס מימינו.

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

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

חיפוש בעץ בינארי

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

סיבוכיות

מהירות החיפוש במבני נתונים נקראת סיבוכיות והיא נמדדת בכמות ההשוואות שיש לבצע עבור פעולה מסויימת במבנה נתונים. הסיבוכיות של חיפוש ברשימה מקושרת היא (O(n ;כלומר:יחסית למספר נתונים ,ואילו סיבוכיות של עץ בינארי היא (O(log n ,כלומר כמות ההשוואות שיש לבצע כדי להגיע לנתון היא יחסית (log(n . בדוגמא שראינו לא מבחינים בקלות בהשפעת הבדלי החיפוש ,אך לו היו כ1,000,000 נתונים; ברשימה מקושרת במקרה הגרוע ביותר היינו צריכים לעבור על 10000000 נתונים לעומת כ 20 נתונים בעץ בינארי.

שדה מפתח

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

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

ניגש לתוכנית עצמה ונגדיר מחלקה בשם block המייצגת צומת בעץ.

 #define SIZE 15
  struct block{
    int num;
  char name[SIZE];
  int height;
  block *right;
  block *left;
  block(int Inum,const char *Iname )
    {
	num=Inum;
	right=NULL;
	left=NULL;
	height=0;
	if (strlen(Iname)<SIZE)
	     strcpy(name,Iname);
	else
	 {
	    cout<<"error inputting name\n";
	    exit(1);
	  }
     }
   void print(){cout<<"num="<<num<<"  name="<<name<<
   "  height="<<height<<'\n';}
   };
class tree{
  public:
  block *r;
  tree(){r=NULL;}
  void insert(block *root,block *bnew);
  void print(block *root);
  } ;

המחלקה מכילה שדה מפתח מסוג int בשם num .ישנם שני מחווניםלאובייקט מסוג block והם:right ו left ,וכן height המגדיר את עומק הצומת בעץ . למחלקה פונקציה בונה ,המאתחלת את המשתנים לערכים הבאים: גובה הצומת 0 והמחוונים right ו left מקבלים NULL.הפונקציה ( )block::print מוציאה את האובייקט כפלט למסך. לאחר מכן מוגדרת מחלקה בשם tree ,היא תייצג את מבנה הנתונים.למחלקה משתנה אחד r מסוג:public המצביע לשורש העץ. הפונקציה הבונה של העץ מאתחלת את שורש העץ ל NULL,כך שבתחילה העץ ריק.

#include <iostream.h>
#include <string.h> 
#include <process.h> 
#include "tree.h"
void tree::print(block *root)
   {
    if (root==NULL) return;
	print(root->left);
	root->print();
	print(root->right);
    }
void tree::insert(block *root,block *bnew)
  {
    if (r==NULL)
	{
	r=bnew;
	bnew->height=0;
	return;
       }
    if (root==NULL)
	{
	root=bnew;
	return;
	}
   if (bnew->num >= root->num)
	{
	 if (root->right==NULL)
	    {
	     bnew->height++;
	     root->right=bnew;
	    }
	 else
	    {
	    bnew->height++;
	    insert(root->right,bnew);
	    return;
	    }

	 }
    if (bnew->num < root->num)
	{
	    if (root->left==NULL)
		{
		bnew->height++;
		root->left=bnew;
		}
	    else
		{
		bnew->height++;
		insert(root->left,bnew);
		return;
		}

	}
   }

main()
{
    int i;
    block *tmp;
    tree t;
    int num;
    char name[SIZE];
    cout<<"input number than name\n";
    for(i=0;i<5;i++)
      {
	cin>>num>>name;
	tmp=new block(num,name);
	t.insert(t.r,tmp);
      }
    t.print(t.r);
  return 0;
  }