Binary Search Tree (BST) Yapısı & Java’da Uygulanışı

İkili arama ağacı ( Binary Search Tree ) ‘yi özellikle Data structures ( veri yapıları ) ile uğraşıyorsanız duymuşsunuzdur. Sıralama ağaçlarının temelini oluşturuyor diyebiliriz.

Kısaca çalışma şeklini anlatayım; sıfırdan sayıları ağaç’a ekliyorsanız, ilk eklenen ağacın root’ elemanı olacaktır. Bir sonraki eklenen elemanlar ise bu ağaçtaki rootlara göre sağa ve sola eklenecektir. Diğer eklenen elemanlarda sağ sol kayarak doldurabileceği boş alana eklenir.

Örnekleyelim; sayıları sırayla ekleyelim : 10, 6, 11, 15, 13

ilk eklenen sayımız 10 ; root’u muzu belirledik.

ikinci sayımız 6; 10dan küçük, ağacın sol tarafına ekleniyor.

üçüncü sayımız 11; 10dan büyük, ağacın sağ tarafına ekleniyor.

dördüncü sayımız 15;  10dan büyük, daha sonra 11 var; 11 den büyük 11in sağına eklenir.

beşinci sayımız 13 ;  10dan büyük, daha sonra 11 var; 11 den büyük 11in sağına kayar, 15 var, 15 ten küçük onun soluna eklenir.

Bu şekilde devam ederek ikili arama ağacımız şekillenir.

BST Ağacın en küçük elemanını bulmak için; sürekli sol tarafa giderek gezersek ağacı hızlı bir şekilde en küçük elamanı elde ederiz.

BST Aynı şekilde ağacın en büyük elemanını bulmak için; sürekli sağ tarafa giderek ağacı gezersek en büyük elemanı buluruz.

Binary Search Tree Running Time ( Çalışma süresi )

Worst case : O(n)
Binary Search Tree Java kodları ( Java implementatiton )

BST.java

// Binary Search Tree
public class BST {
private Node root;
private class Node
{
private Node parent;
private Node left;
private Node right;
private int data;

Node(int k)
{
left = right = null;
data = k;
}
}

public void insert(int k)
{
Node n = new Node(k);
insert(root,n);
}

private void insert(Node r, Node n)
{
if(root == null) root = n;
else{
if(r.data > n.data) // sola
{
if(r.left == null) // en sola geldik
{
r.left = n;
n.parent = r.left;
}
else insert(r.left,n); // en sola gitmek için fonksiyonumuzu recursive olarak çağırıyoruz
}
else
{ // sağa
if(r.right == null) // en sağa geldik
{
r.right = n;
n.parent = r.right;
}
else insert(r.right,n); // en sağa gitmek için fonksiyonumuzu recursive olarak çağırıyoruz
}
}
}

public void search(int k)
{
boolean control = search(root, k);
if(control) System.out.println("Bulundu");
else System.out.println("Bulunamadı");
}

private boolean search(Node r, int k)
{
if( r != null)
{
if(r.data == k) return true;
else if(r.data > k) search(r.left,k);
else if(r.data < k) search(r.right,k);
}
return false;
}

public void max()
{
System.out.println(max(root));
}
// en büyük değer için ağacın en sağına gideriz
private int max(Node r)
{
if(r!=null)
{
max(r.right);
}
return r.data;
}

public void min()
{
System.out.println(min(root));
}
// en küçük değer için ağacın en soluna gideriz
private int min(Node r)
{
if(r!=null)
{
min(r.left);
}
return r.data;
}

public void print(Node r)
{
if( r != null )
{
print(r.left);
System.out.print(r.data + " ");
print(r.right);
}
}
}

main.java

class main{

public static void main (String[] args)
{
BST tree = new BST();
tree.insert(10);
tree.insert(11);
tree.insert(7);
tree.insert(5);
tree.print(tree.root);
tree.search(11);

}

}