Genel kavramlar:

Yaprak (leaf)

Ağacın en uçta bulunan düğümleridir. Çocuğu olmayan kendisine bağlı eleman olmayan elemanlara denilir.

Düğüm (node)

Ağacın içinde bulunan her elemana verilen isimdir. Kendisi bir başka elemanı gösterebileceği gibi, kendisini de başka elemanlar gösterebilir. Ağacın yapısına göre içinde veri olabilir veya olmayabilir. Ağaçların kökleri ve yaprakları da birer düğüm kabul edilebilir.

Kök (root)

Ağacın en tepesindeki başlangıç düğümüdür. Ağaca erişildiğinde ilk okunan veridir. Ağacın içindeki hareketlilik bu kökten başlar.

Ağacın Derinlik (derecesi):

Bir ağacın derinliği, o ağacın köküne en uzak olan yaprağının uzaklığı ile ölçülür. Örneğin derinliği (yada derecesi) 3 olan bir ağacın, kökten (root) başlayarak en uç elemana (düğüm) uzaklığı 3 olmalıdır.

Ağacın Dengeli olması

Bir ağacın dengeli olması, ağacın kollarının azami (maximum) derinliği arasındaki farkın en fazla 1 olmasını gerektirir.

Çocuk düğümler

Bir düğümün altında bulunan düğümlere verilen addır.

Anahtar (veri)

Ağacın içinde saklanılan ve daha sonra erişilmek istenilen verilerdir.

Ağaçlar:

(a,b)-tree (a,b) ağacı

Bütün kollarının aynı derinlikte olması ve bütün düğümlerinin (node) 2 ≤ a ≤ (b+1)/2 şartını sağlayan a ve b sayıları arasında olması zorunluluğu bulunan ağaçtır. Kökün (root) en az 2 çocuğu (children) olabilir.

Adaptive k-d tree

Başarılı seviyleerin farklı boyutlara bölünebildiği çok boyutlu (multidimensional) ağaç (Tree)dir

AVL tree

Dengeli ikili arama ağacıdır. (balanced binary search tree).İki çocuğun (child) derinlikleri (depth) arasındaki azami (maximum) fark 1 olabilir. Algoritmanın karmaşıklığı (complexity), arama, ekleme ve silme (look-up, insertion, deletion) işlemleri için O(log n)’dir. (n ağaçta bulunan düğüm (node) sayısısıdır).

Balanced binary search tree (dengeli ikili arama ağacı)

İkili ağacın (binary tree) bütün çocuklarının (child) aynı derinliğe sahip olması veya derinlikleri arasında en fazla 1 fark bulunmasıdır. (bkz. “Balanced tree” veya “dengeli ağaç”)

Balanced binary tree (dengeli ikili ağaç)

İkili ağacın (binary tree) bütün çocuklarının (child) aynı derinliğe sahip olması veya derinlikleri arasında en fazla 1 fark bulunmasıdır. Dengenin sağlanması için ekleme ve silme işlemlerinden sonra dengeleme (rotation) gerekebilir (bkz. “Balanced tree” veya “dengeli ağaç”)

B-tree (b-ağacı, balanced multiway tree, dengeli çok yollu ağaç)

Her düğümü (node) m/2 ile m arasında çocuk içeren dengeli arama ağacıdır(balanced search tree). Burada m>1 olmalıdır ve m sayısı ağacın derecesini (order) belirtir. Kökte (root) en az 2 çocuk bulunmalıdır. Ağacın en güzel özelliği, ağacın büyük bölümünün yavaş bir hafıza alanında (disk gibi) bulunuyor olması durumunda, ağacın yüksekliği (ve dolayısıyla ağaca erişim sayısı) küçük tutulabilmektedir. Dikkat edilirse m sayısı büyüdükçe ağacın derinliği azalmakta ve dolayısıyla ağaca erişim azalmaktadır.

Balanced tree (dengeli ağaç)

Bir ağacın bütün çocuklarının (child) aynı derinliğe sahip olması veya derinlikleri arasında en fazla belirtilen miktarda fark bulunmasıdır. Dengenin sağlanması için ekleme ve silme işlemlerinden sonra dengeleme (rotation) gerekebilir. Denge miktarı (çocukların azami (maxiumum) derinlikleri arasındaki fark) ağaç tanımlanırken tanımlanır ve ağaç bu miktarı korur.

BB(α) tree (dengeli alfa ikili ağacı, balanced binary alfa tree)

Dengeli bir ikili ağaçtır. Her alt ağaç (subtree) ρ(T'), için α ≤ ρ(T') ≤ 1-α. Koşulu aranmaktadır.

BD-tree (Bounded Deformation Tree, Sınırlı bozulma (Deformasyon) ağacı)

Normal alt aralıklarını çok boyutlu noktalara parçalayan ikili ağaçtır. BD-ağacı, ürettiği sonuçlar için çevreleyen küre hiyerarşisi kullanır ve çakışma (collision) önleyici özelliği vardır.

binary search tree (BST, İkili arama ağacı)

Her düğümün (node), solundaki anahtarların, sağındaki anahtarlardan küçük olduğu ağaçtır. Bir düğümün en fazla iki çocuğu olabilir.

Binary tree (ikili ağaç, dyadic tree)

Her düğümünde en fazla iki çocuk bulunan ağaçtır. Bir ikili ağaç ya boştur, ya da bir kök düğümü bulunur ve solunda ve sağındaki çocukları da yine bir ikili ağaçtır.

Binomial tree (binom ağacı)

Derecesi k ≥ 0 olan, dereceli ağaçtır. Buna göre B_k ağacı k çocuğu olan bir köke sahiptir ve binom ağacının i. çocuğu k-i derecesine sahiptir. Bir B_k ağacının 2^k çocuğu varıdır.

B_k tree (bk ağacı)

Derinliği k olan binomial ağaçtır.

B+-tree

B-tree’nin (B- ağacının ) özel bir halidir. Veriler sadece yapraklarda saklanır. Bütün ağaç verilere erişmek için indeks bilgisi ile doludur. En son yapraklara erişildiğinde verilere erişilmiş olunur.

BSP-tree (Binary space partitioning , İkili parçalı ağaç)

Bir çeşit ikili ağaçtır (binary tree). Birden fazla erişim yapılabilmesi için, istenilen noktalara dışarıdan erişilebilen ve bu erişimleri ağacın içinde parçalara bölen hiperplatformları (ayıraçları (hyperplane)) bulunan ağaçtır.

B*-tree

B-tree’nin (B- ağacının ) özel bir halidir. Normal b-ağacında düğümlerin yarısı doluyken bu ağaçta kök olmayan düğümlerin 2/3’ü dolu tutulmaktadır. Dolayısıyla bir düğüm doluluğa eriştiğinde hemen bölünmemekte, yeni gelen anahtar, iki komşu düğüm arasında paylaşılmaktadır. 2/3 oranı aşılınca bu iki komşu düğüm 3. bir düğüm üreterek yüklerini azaltmaktadırlar.

B#-tree (B sharp tree)

B*-ağacının neredeyse aynısıdır. Tek farklı kardeş düğümler arasında rotasyona izin verilmesidir.