Графтар мен ағаштар

Ағаштар.

Келесі қасиеттері бар графтарды ағаштар дейді:

- Басқа ешбір  элемент сілтемейтін жалғыз элементі (түйін, төбе) бар болса және ол  түбір деп аталады.

- Түбірден  бастап элементтерде бар белгілі  бір көрсеткіштер тізбегі бойымен  структураның басқа кез келген  элементіне қатынас жасауға болса.

- Түбірден  басқа әрбір элементке тек  бір ғана сілтеме жасалса, яғни  әрбір элементтің жалғыз адресі  болса.

Бағдарлы ағаш деп түбір деп аталатын бір төбесі бар, кіріс жартыдәрежесі нөлге тең, басқа кіріс жартыдәрежелері 1-ге тең болатын циклдік графты айтады. Бұл ағаштардың ең болмағанда бір төбесі бар болады. Аластатылған, дара төбе де бағдарлы ағаш деп аталады.

Шығыс жартыдәрежесі нөлге тең бағдарлы ағаштың төбесі ілінген, соңғы төбе деп аталады. Одан басқа төбелері тармақталу төбелері деп аталады. Түбірден әлдебір төбеге дейінгі жолдың ұзындығы осы төбенің деңгейі - немесе ярус номері деп аталады.  Түбір деңгейі нөлге тең болады, ал басқа төбелердің деңгейлері түбір мен төбелердің арасындағы ұзындықпен анықталады, немесе төбелер деңгейлерінің номерлерінің модулі бойынша айырмасына тең.

Бинарлы ағаштар.

m - арлы ағаштар бар, олар әрбір  төбелердің шығыс жартыдәрежесі m-нен кіші не тең болатын  ағаштар. m=0,1,2,3,... Егер әрбір төбеніңғ  шығыс жартыдәрежесі m-ге немесе  нөлге тең болса, оны толық  ағаш немесе m - арлы ағаш дейді.

m=2 болғанда ағаштарды бинарлы немесе толық бинарлы дейді.

Кез келген ағашты, тоғайларды бинарлы ағашпен көрсету.

1. Әрбір түйінде  үлкен ұлға (вертикальды жалғау) тек бір ғана бұтақ қалдыру.

2. Горизонтальды  қабырғалармен бір әкелі барлық  бауырларды жалғастыру.

3. Сонда мына  ережемен ағаш қайта құрылады: сол жақтағы ұл - берілген төбенің  астында орналасқан төбе, оң жақ  ұл - берілген төбенің оң жағында  орналасқан төбе, яғни яруста  орналасқан төбе.

4. Ағашты  вертикальды бұтақтары сол жақтағы  ұлдарды, горизонтальды бұтақтары  оң жақтағы ұлдарды көрсететіндей  етіп төңкеру.

Нәтижесінде кез келген ағашты бинарлы ағашқа алмастырғанда түбірлі төбеге ілінген сол жақтағы ішкі ағаш түріндегі ағаш алынады.

Балансталған ағаш. Бинарлы ағашта іздеу операциясын жылдамдатуға көмектеседі. Балансты ағаш деп әрбір түйін үшін оның екі ішкі ағашының биіктігінің  айырмашылығы біреу  болса ғана айтады.