Öğr. Gör. Dr. Alper VAHAPLAR
2014 – 2015

Verilerin birbirlerine sanki bir ağaç yapısı
oluşturuyormuş gibi sanal olarak
bağlanmasıyla elde edilen hiyerarşik yapıya
sahip bir veri modelidir.

Bir kök (root) işaretçisi, sonlu sayıda
düğümleri (node) ve onları birbirine bağlayan
dalları (branch) olan veri modelidir.
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
2
1

Yazılım dünyasında birçok yerde
programcının karşısına çıkar. Örneğin:
 İşletim sistemlerinin dosya sistemi.
 Oyunların olası hamleleri.
 Şirketlerdeki organizasyon şeması.
BİL2001-Algoritmalar ve Veri Yapıları
Alper VAHAPLAR
Kök
Derinlik
1
2
3
A
B
C
Ara
Düğüm
Yaprak
Düğüm
3
D
4
E
Yaprak
Düğüm
F
G
7 düğümlü ağaç
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
4
2













Kök (Root): Ağacın başlangıç düğümüdür.
Çocuk-Evlat Düğüm (Child): Bir düğüme doğrudan bağlı
olan düğümlerdir.
Kardeş Düğüm (Sibling): Aynı düğüme bağlı düğümlere
denir.
Aile-Ebeveyn (Parent): Düğümlerin doğrudan bağlı
olduğu düğüme denir.
Yaprak (Leaf): Çocuğu olmayan düğümlere denir.
Ata (Ancestor): Düğümün üstündeki düğümlere ata
denir. (Parent = 1. ancestor, Root=kendi hariç tüm
düğümler için ancestor)
Torun (Descendant): Bir düğüme bağlı alt düğümlerdir.
(Child = 1. Descendant)
5
Derece (Degree): Bir düğümün çocuk veya altağaç
sayısı
Yol (Path): Bir düğümden başka bir düğüme gidebilmek
için üzerinden geçilmesi gereken düğümlerin listesi.
Düzey (Level)/ Derinlik (Depth): Kök ile düğüm
arasındaki yolun üzerinde bulunan düğümlerin sayısıdır.
Bir düğümün köke olan uzaklığıdır. (Kök = Level 1)
Yükseklik (Height): Bir düğümün kendi silsilesindeki en
uzak mesafedeki yaprak düğüme olan düzey sayısı.
Altağaç (Subtree): Ağacın herhangi bir dalı
Orman (Forest): Ağaçlar kümesi
6
3
Kök
A
B
C
D
E
F
G
Tanım
kök
B
D
Çocuk/Derece
2
0
0
Kardeş
1
2
3
Düzey
1
2
3
Aile/Parent (Anne)
yok
A
C
Ata
yok
A
C, A
Yol
A
A, B
A,C,D
Derinlik
1
2
3
Yükseklik
4
3
2
7



Her düğümden en fazla 2 dal çıkabilir.
Bir düğümün derecesi en fazla 2 olabilir.
Bilgisayar bilimlerinde en yaygın olarak
kullanılan ağaç modelidir.
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
8
4
Kök
A
D
C
Z
P
I
K
M
Sağ alt ağaç
Alper VAHAPLAR

BİL2001-Algoritmalar ve Veri Yapıları
9
Full Binary Tree: Yaprak olmayan düğümlerin
tümünün 2 çocuk düğümü olan ikili
ağaçlardır.
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
10
5

Complete Binary Tree: Full binary tree'de
yeni bir derinliğe soldan sağa doğru
düğümler eklendiğinde oluşan ağaçlardır
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
11
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
12
6
Alper VAHAPLAR

BİL2001-Algoritmalar ve Veri Yapıları
13
Binary Search Tree:
 Kökün solundaki alt ağaçlardaki (eğer varsa) tüm
anahtarlar kökteki anahtardan küçüktür.
 Kökün sağındaki alt ağaçlardaki (eğer varsa) tüm
anahtarlar kökteki anahtardan büyüktür.
 Sol ve sağ alt ağaçlar da ikili arama ağaçlarıdır.

Hızlı Arama
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
14
7

Binary Search Tree:
Alper VAHAPLAR

BİL2001-Algoritmalar ve Veri Yapıları
15
Binary Search Tree İşlemler:
 Ağaç Oluşturma (Construct)
 Yeni düğüm ekleme (Add new node)
 Ağaçta Dolaşma (Traversal)
 Düğüm Arama
 Düğüm Silme
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
16
8

Binary Search Tree İşlemler:
 Ağaç Oluşturma (Construct)
typedef struct tree
{
int
deger;
struct tree *sol;
struct tree *sag;
} agac;
Alper VAHAPLAR

BİL2001-Algoritmalar ve Veri Yapıları
17
Binary Search Tree İşlemler:
 Kök Oluşturma
if (kok==NULL) {
kok=(agac *)malloc(sizeof(agac));
kokdeger=gelen;
koksol=NULL;
koksag=NULL;
}
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
18
9

Binary Search Tree İşlemler:
 Yeni düğüm ekleme
while (dugum!=NULL) {
anne=dugum;
if (gelen<=dugumdeger) dugum=dugumsol;
else dugum=dugumsag;
}
if (gelen<=annedeger) annesol=yeni;
else annesag=yeni;
Alper VAHAPLAR


BİL2001-Algoritmalar ve Veri Yapıları
19
kök
Binary Search Tree İşlemler:
Ağaçta Dolaşma (Traversal)
 PreOrder (Depth-First)
4
 InOrder (Symmetric)
 PostOrder
45
Alper VAHAPLAR
12
6
BİL2001-Algoritmalar ve Veri Yapıları
7
1
20
10

PreOrder (Depth-First)
 Önce Kök
 Sol
 Sağ
A-D-B-G-C-E-H-I-F
Alper VAHAPLAR

BİL2001-Algoritmalar ve Veri Yapıları
21
InOrder (Symmetric)
 Sol
 Ortada Kök
 Sağ
D-G-B-A-H-E-I-C-F
 Binary Search Treenin
Sıralı halini oluşturur…
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
22
11

PostOrder
 Sol
 Sağ
 Sonra Kök
G-D-B-H-I-E-F-C-A
Alper VAHAPLAR


BİL2001-Algoritmalar ve Veri Yapıları
23
Traversal Alıştırma
Pre Order (Kök – Sol – Sağ)
d
b
a
c
e
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
24
12


Traversal Alıştırma
In Order (Sol – Kök – Sağ)
a
b
c
d
e
Alper VAHAPLAR


BİL2001-Algoritmalar ve Veri Yapıları
25
Traversal Alıştırma
Post Order (Sol – Sağ – Kök)
a
c
b
e
d
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
26
13
Kök
Önce-kök
ACPDZMIK
A
Ortada-kök
PCAMZDIK
D
C
Sonra-kök
PCMZKIDA
Z
P
M
I
K
27

PreOrder Traversal Uygulaması
void dolas(agac *dugum)
{
if (dugum!=NULL) {
printf(" %d ",dugum->deger);
dolas(dugum->sol);
dolas(dugum->sag);
}
}
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
28
14

InOrder Traversal Uygulaması
void dolas(agac *dugum)
{
if (dugum!=NULL) {
dolas(dugum->sol);
printf(" %d ",dugum->deger);
dolas(dugum->sag);
}
}
Alper VAHAPLAR

BİL2001-Algoritmalar ve Veri Yapıları
29
PostOrder Traversal Uygulaması
void dolas(agac *dugum)
{
if (dugum!=NULL) {
dolas(dugum->sol);
dolas(dugum->sag);
printf(" %d ",dugum->deger);
}
}
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
30
15


Pre Order:
7,4,2,3,6,5,12,9,8,11,19,15,20
Alper VAHAPLAR


BİL2001-Algoritmalar ve Veri Yapıları
31
In Order:
2,3,4,5,6,7,8,9,11,12,15,19,20
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
32
16


Post Order:
3,2,5,6,4,8,11,9,15,20,19,12,7
Alper VAHAPLAR


BİL2001-Algoritmalar ve Veri Yapıları
33
Balanced – Unbalanced Trees
Dengeli – Dengesiz ağaçlar
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
34
17

Alıştırma
 Ağacın En Küçük elemanını bulunuz.
 Ağacın En Büyük elemanını bulunuz.
 Verilen bir değeri ağaçta arayan algoritmayı
yazınız.
 Ağacın yüksekliğini ölçen algoritmayı yazınız.
 Ağaçta arama işleminin karmaşıklığını
hesaplayınız.
Alper VAHAPLAR

BİL2001-Algoritmalar ve Veri Yapıları
35
Ağaçtan düğüm silme
 Yaprak düğüm silme
 Tek çocuklu düğüm silme
 2 çocuklu düğüm silme
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
36
18

Ağaçtan düğüm silme
 Yaprak düğüm silme
Alper VAHAPLAR

BİL2001-Algoritmalar ve Veri Yapıları
37
Ağaçtan düğüm silme
 Tek çocuklu düğüm silme
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
38
19

Ağaçtan düğüm silme
 İki çocuklu düğüm silme
Alper VAHAPLAR

BİL2001-Algoritmalar ve Veri Yapıları
39
Ağaçtan düğüm silme
 İki çocuklu düğüm silme
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
40
20
agac * sil(agac *dugum, int data)
{
if(dugum==NULL) printf("Bulamadım");
else if(data < dugum->deger) dugum->sol = sil(dugum->sol, data);
else if(data > dugum->deger) dugum->sag = sil(dugum->sag, data);
else {
/* Silinecek düğüm bulundu. Bu düğümü sağ alt ağacın en küçük elemanı ile
değiştirelim... */
if(dugum->sag!=NULL && dugum->sol!=NULL){
agac *temp;
temp = minbul(dugum->sag);
dugum -> deger = temp->deger;
/* Sag alt ağacın en küçük düğümü siliniyor... */
dugum -> sag = sil(dugum->sag,temp->deger);
}
else {
/* Yaprak ya da tek çocuklu düğüm ise annesini çocuğa bağla*/
if(dugum->sol == NULL)
dugum = dugum->sag;
else if(dugum->sag == NULL)
dugum = dugum->sol;
}
}
return dugum;
}
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
41
Özel bir çeşit ikili ağaç (binary tree)
1. Her yaprak bir işlenen (operand) içerir.
2. Her ara düğüm bir ikili işlemci (binary operator)
içerir.
3. İfadede parantez kullanımını kaldırır.
4. Bir işlemcinin sol ve sağ alt ağaçları kökteki
işlemciden önce değerlendirilmesi gereken ifadeleri
içerir.
5. Ağacın seviyeleri (level) ifadedeki öncelikleri
belirler.
6. Ağacın inorder traversal’i ifadenin parantezsiz
gösterimini verir.
42
21
Expression
Expression Tree
+
a+3
a
3
+
3
3+4*5-9+6
-
*
4
+
9
5
6
log
log(x)
x
!
n!
n
BİL2001-Algoritmalar ve Veri Yapıları
Alper VAHAPLAR
43
‘*’
‘/’
‘-’
‘8’
‘5’
‘3’
‘+’
‘4’
Infix:
((8-5)*((4+2)/3))
Prefix:
*-85 /+423
Postfix:
85- 42+3/*
‘2’
44
22
Expression
Expression Tree
Infix form
+
-
2-3*4+5
5
2
2-3*4+5
*
3
4
*
(2 - 3) * (4 + 5)
2
2-3*4+5
+
3
4
5
2
2 - (3 * 4 + 5)
2-3*4+5
+
*
3
5
4
BİL2001-Algoritmalar ve Veri Yapıları
Alper VAHAPLAR
45
‘/’
‘-’
‘+’
‘A’
‘H’
‘M’
Infix:
(A + H) / (M - Y)
Prefix:
/+AH -MY
Postfix:
‘Y’
AH +MY- /
46
23

Diğer Ağaç Yapıları
 AVL (Adelson-Velskii-Landis) Ağaçları
 2-3 Ağaçları
 2-3-4 Ağaçları
 B-Trees
 Red-Black Trees
 Heap Trees
Alper VAHAPLAR
BİL2001-Algoritmalar ve Veri Yapıları
47
24
Download

Sunum