Veri Yapıları - Ders Notu - Süper

Week 9: Trees
1. TREE KAVRAMI
2. İKİLİ AĞAÇ VE SUNUMU
3. İKİLİ AĞAÇ DİZİLİMİ
4. İKİLİ ARAMA AĞACI
<
2
1
6
9
>
4 =
8
1. TREES KAVRAMI
Bir ağaç bir veya daha fazla düğümün (T)
bir kümesidir :
–
–
Spesifik olarak tasarlanmış root isimli bir
düğümü vardır
Geriye kalan düğümler her biri bir ağaç olan T1,
T2,…,Tn gibi birbirinden ayrık n adet düğümler
kümesine ayrılır.
1. TREES KAVRAMI
Example
1. TREES KAVRAMI
Bir ağaç değildir
Ağaç
1. TREES KAVRAMI: Biraz terminoloji
Root (kök)
Child (left,right) (evlat)
Parent (ebeveyn)
Leaf node (yaprak)
Subtree (alt ağaç)
Ancestor of a node
(bir düğümün atası)
Descendant of a node
(bir düğümün soyundan)
1. TREES KAVRAMI
Bir ağacın bir düğümünün derecesi
–
Bir ağacın bir düğümünün derecesi, kökü bu düğüm olan alt
ağaçların sayısıdır.
Bir ağacın derecesi
–
Bir ağacın derecesi ağacın
derecesi olarak tanımlanır.
düğümlerinin
maksimum
Bir düğümün seviyesi
–
Kök düğüm 1 olmak üzere, kökten aşağı doğru 1’er artar.
2. İKİLİ AĞAÇ VE SUNUMU
İKİLİ AĞAÇ
–
Hiçbir düğümün derecesi ikiden fazla değildir.
–
i. Seviye için maksimum düğüm sayısı 2i−1’dir.
–
Eğer ağacın derinliği k ise o zaman ağaçtaki
bütün düğümlerin sayısı
–
2k − 1 = 2k−1 + 2k−2 + … + 20 olacaktır.
2. İKİLİ AĞAÇ VE SUNUMU
İKİLİ AĞAÇ
–
Tam dolu bir ikili ağaç 2k − 1 düğümü olan bir
ikilidir.
–
Eğer düğüm sayısı < 2k − 1 ise, o tam dolu bir
ikili ağaç değildir.
N düğümü olan bir tam ağacın
yüksekliği (h) nedir?
2 −1 = N
h
⇒ 2 = N +1
h
⇒ h = log( N + 1) → O(log N )
N düğümlü bir ağacın maksimum yüksekliği
N (bağlı liste gibi)
N düğümlü bir ağacın minimum yüksekliği
log(N+1)
2. İKİLİ AĞAÇ VE SUNUMU
Tam ikili ağaç
3=22-1
7=23-1
15=24-1
2. İKİLİ AĞAÇ VE SUNUMU
struct node
{ int data;
node *left;
node *right;
};
Ağaç dizilimi
Bir ağaçta belirli bir sırada veri yazdırmak için
kullanılır.
–
–
–
inorder (LDR )
Postorder (LRD )
preorder (DLR )
Pre-order dizilimi
–
–
–
Kökteki veriyi yazdır
Yinelemeli olarak sol alt ağaçtaki bütün verileri yazdır.
Yinelemeli olarak sağ alt ağaçtaki bütün verileri yazdır.
Preorder, Postorder and Inorder
Preorder dizilimi
–
–
düğüm, sol, sağ
Ön ek ifadesi
++a*bc*+*defg
Preorder, Postorder and Inorder
Postorder dizilimi
–
–
sol, sağ, düğüm
Son ek ifadesi
abc*+de*f+g*+
İçinde dizilimi
–
–
sol, düğüm, sağ.
Orta ek ifadesi
a+b*c+d*e+f*g
Preorder, Postorder and Inorder
3. İKİLİ AĞAÇ DİZİLİMİ
3. İKİLİ AĞAÇ DİZİLİMİ
Inorder = DBEAC
Aynı sonucu veren
birden çok ağaç olabilir.
4. İKİLİ ARAMA AĞACI
Bir ikili arama ağacı
–
–
–
–
–
İkili bir ağaçtır (boş olabilir)
Her düğüm bir tanımlayıcı içermelidir.
Sol alt ağaçtaki bir düğümün tanımlayıcısı kök
düğümdeki tanımlayıcıdan daha küçüktür.
Sağ alt ağaçtaki herhangi bir düğümün
tanımlayıcısı kök düğümdeki tanımlayıcıdan
büyüktür.
Hem sol alt ağaç hem de sağ alt ağaç ikili bir
arama ağacıdır.
4. İKİLİ ARAMA AĞACI
İkili arama ağacı.
İkili arama ağaçları
İkili arama ağacı
İkili arama ağacı değil
İkili arama ağacı
Aynı kümeyi sunan iki ikili arama ağacı : neden
farklı?
Performans
N elemanı olan bir sözlüğün
h yüksekliğine sahip bir ikili
ağaç ile sunulduğunu var
sayalım.
–
–
Kullanılan bellek uzayı O(n)
find, insert ve remove
metotları O(h) zamanda
yapılır.
h yüksekliği için worst case
O(n) ve best case O(log n)
olarak ölçülür.
4. İKİLİ ARAMA AĞACI
Neden ikili arama ağacı kullanırız
–
–
inorder dizilimi: sıralı liste
arama daha hızlı gerçekleşir
Fakat..
–
Ekleme, silme: yavaştır
Önemli konu: Veritabanı sistemindeki Index
mekanizması
–
Index özelliğinin doğru şekli kullanarak sorun
çözülür.
Arama
Algorithm TreeSearch(k, v)
if (v ==NULL)
return v
Bir k değerini aramak için,
if k < key(v)
kökten başlayarak aşağı
return TreeSearch(k, T.left(v))
doğru tararız.
else if k = key(v)
Bir sonraki düğümün ne
return v
olacağı karşılaştırma
else { k > key(v) }
sonrasına bağlı olarak
değişir.
return TreeSearch(k, T.right(v))
Eğer bir yaprağa
6
ulaştığımız halde aranan
<
eleman bulunamadıysa
2
9
null döndürürüz.
>
Örnek: find(4):
8
1
4 =
– TreeSearch(4,root)
Ekleme
inser(k, o) işlemini yerine
getirmek
için,
biz
önce
anahtar değerini (k) ararız
(TreeSearch kullanarak)
Varsayalım ki son yaprağa
vardığımız halde k hala
bulunamadı
Anahtar
(k)
değeri
w
düğümüne ekleriz ve ağacı bir
düğüm genişletiriz.
Örnek: insert 5
6
<
2
9
>
1
4
8
>
w
6
2
1
9
4
8
w
5
4. İKİLİ ARAMA AĞACI
Yeni düğüm ekle
4. İKİLİ ARAMA AĞACI
Yeni düğüm ekle
void InsertNode(node* &root, node *newnode)
{
if (root==NULL)
root=newnode;
else
if ((root->data)>(newnode->data))
InsertNode(root->l,newnode);
else
if (root->data<newnode->data)
InsertNode(root->r,newnode);
}
Insert node
Insert node
Insert Order