Binary Tree Veri Yapısında Depth First Search Mantığı
Veri yapılarının en karmaşıklaşmaya başladığı Tree (Ağaç) ve Graph veri yapıları ve bununla birlikte hayatımıza daha da karmaşık algoritmaların girmeye başladığı algoritmalardan biri de Depth First Search yani Derinlik öncelikli arama algoritmasıdır.
Binary Tree (İkili Ağaç) Nedir?
Algoritmaya geçmeden önce Binary Tree tanımını yapmakta fayda var sanırım. Binary Tree node’lardan oluşan ve her birinin en fazla 2 node’a sahip olduğu özel bir veri yapısıdır.,
Binary Tree veri yapısında erişilmek istenilen node’a ulaşmak için kullanılan iki farklı search (arama) algoritması bulunur. Breadth First Search (BFS) yani Genişlik Öncelikli Arama ve Depth First Search (DFS) yani Derinlik Öncelikli Arama.
Bu yazımızda Depth First Search (DFS) algoritmalarını inceleyeceğiz.
Depth First Search (DFS)
Neden DFS ve Ne zaman?
DFS algoritması, BFS’ye göre daha az memory kullandığı için büyük verilerde daha efektif çalışmaktadır. Ayrıca DFS algoritması backtracking (geri dönüş) sağladığı için ziyaret edilen node’ların ayrıca listesini tutmaya ihtiyaç duyulmaz. DFS, BFS algoritmasına göre daha hızlı çalışmaktadır.
Büyük veri setlerinde DFS kullanılması önerilirken, hedeflenen node eğer root’a yakın ise BFS kullanımı önerilmektedir.En kısa mesafe gibi problemlerde BFS kullanımı önerilmektedir. Tüm olasılıkları çıkartıp birbirleriyle karşılaştırma yapılması gereken problemlerde ise DFS kullanılması önerilmektedir.
DFS algoritmasında esas olan root (kök) elementinden başlayarak önce erişilebilen en alt child elemente erişip, sonrasında bir üst parent elementine geçmektir. Bunu yaparken de genelde önce sol (left sub tree) taraftaki elementlere sonra ise sağ (right sub tree) elementlerine erişilir.
DFS algoritmasını uygulamak için, Recursive ve Non-Recursive olmak üzere iki yöntemi vardır.
Recursive yöntem, adından da anlaşılacağı gibi, bir recursive metod geliştirilmelidir. Ancak bu yöntemin time complexity değeri O(1) ile O(n²) arasında değişebilir.
Non-Recursive ya da Iterative yöntemi ise, Last In First Out (LIFO ya da FILO) yaklaşımından yararlanabilmek için Stack veri yapısı ile geliştirilir. Iterasyon söz konusu olduğu için time complexity değeri sabit O(n) şeklindedir. Ancak kod kompleksliği kullanılacak yaklaşıma bağlı olarak artmaktadır.
DFS algoritmasını uygulayan 3 farklı yaklaşım bulunmaktadır.
Aşağıdaki kod örneklerinde, bir binary tree veri setini List verisine çevirilmektedir.
Aşağıdaki tüm örnek kodları https://github.com/folksdev/binary-tree-dfs adresindeki repository’de bulabilirsiniz.
1. Pre-Order Traversal (Ön Sıralı Geçiş)
Pre-Order Traversal mantığı, önce root elementi ziyaret edip sonrasında left sub-tree ve right sub-tree ziyaret edilecek şeklindedir.
/*
root
left sub-tree
right sub-tree
*/
Yukarıdaki resimden de görüleceği üzere, eğer elimizdeki ağacı Pre-Order Traversal algoritması ile çalıştıracak olursak, algoritma root’tan başlayarak, önce root elementini ziyaret edip, left sub-tree ile “1–2–3–4–5–6–7” sıralaması ile ziyaret edecektir.
Recursive Pre-Order Traversal Kod Örneği
public List<Integer> preOrderTraversal(TreeNode root) {
if (root == null) {
return List.of();
}
List<Integer> result = new ArrayList<>();
result.add(root.val);
result.addAll(preOrderTraversal(root.left));
result.addAll(preOrderTraversal(root.right)); return result;
}
//[1, 2, 3, 4, 4, 3, 2]
Non-recursive — Iterative Pre-Order Traversal Kod Örneği
public List<Integer> preOrderTraversalNonRecursive(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
TreeNode current;
stack.push(root);
while (!stack.isEmpty()) {
current = stack.pop();
result.add(current.val);
if (current.right != null) { //LIFO - Last In First Out
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
return result;
} //[1, 2, 3, 4, 4, 3, 2]2. In-Order Traversal (Sıralı Geçiş)
In-Order Traversal mantığı, önce left sub-tree elementlerinin sonuna kadar ziyaret edip sonrasında root elementi ve son olarak da right sub-tree ziyaret edilecek şeklindedir.
/*
left sub-tree
root
right sub-tree
*/
Yukarıdaki resimden de görüleceği üzere, eğer elimizdeki ağacı In-Order Traversal algoritması ile çalıştıracak olursak, algoritma root’tan başlayarak, önce lef sub-tree elementlerinin sonuncusuna kadar ilerleyip, son elementi ziyaret ettikten sonra, root ve right sub-tree elementlerini, “1–2–3–4–5–6–7” sıralaması ile ziyaret edecektir.
Recursive In-Order Traversal Kod Örneği
public List<Integer> inOrderTraversal(TreeNode root) {
if (root == null) {
return List.of();
}
List<Integer> result = new ArrayList<>();
result.addAll(inOrderTraversal(root.left));
result.add(root.val);
result.addAll(inOrderTraversal(root.right));
return result;
} //[4, 3, 4, 2, 3, 1, 2]Non-recursive — Iterative Pre-Order Traversal Kod Örneği
public List<Integer> inOrderTraversalNonRecursive(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
//Visit all left sub-tree and add to stack
stack.push(current);
current = current.left;
}
current = stack.pop();
result.add(current.val);
current = current.right;
}
return result;
} //[4, 3, 4, 2, 3, 1, 2]3. Post-Order Traversal (Sonradan Sıralı Geçiş)
Post-Order Traversal mantığı, önce left sub-tree elementlerinin sonuna kadar ziyaret edip sonrasında right sub-tree ve son olarak da root element ziyaret edilecek şeklindedir.
/*
left sub-tree
right sub-tree
root
*/
Yukarıdaki resimden de görüleceği üzere, eğer elimizdeki ağacı Post-Order Traversal algoritması ile çalıştıracak olursak, algoritma root’tan başlayarak, önce lef sub-tree elementlerinin sonuncusuna kadar ilerleyip, son elementi ziyaret ettikten sonra, right sub-tree elementlerini ve root elementini, “1–2–3–4–5–6–7” sıralaması ile ziyaret edecektir.
Recursive Post-Order Traversal Kod Örneği
public List<Integer> postOrderTraversal(TreeNode root) {
if (root == null) {
return List.of();
}
List<Integer> result = new ArrayList<>();
result.addAll(postOrderTraversal(root.left));
result.addAll(postOrderTraversal(root.right));
result.add(root.val);
return result;
} //[4, 4, 3, 3, 2, 2, 1]Non-recursive — Iterative Post-Order Traversal Kod Örneği
Post Order Traversal algoritması diğer 2 yaklaşıma göre, bulunan node ve önceki node kontrollerinin olmasından dolayı biraz daha karmaşık bir algoritmadır.
Pseudo Code olarak ifade etmek gerekirse
/*
Pseudocode:
Boş bir stack oluştur
Root elementini stack'e ekle
Stack boş olana kadar:
1. Şuanki element son element ise ya da bir önceki element son element ise
1.1 stack'teki son elemanı current'a eşitle
1.2 listeye current elementinin değeri ekle
1.3 prev değerini current'a eşitle
2. Değilse
2.1 right sub-tree boş değilse stack'e ekle
2.2 left sub-tree boş değilse, stack'e ekle
Not:
Son element (hasChild):
- current node'un sağ ve sol değerleri null ise, current son elementtir.
Önceki elementin son element olması(isPrevLastChild):
- Eğer prev değeri ile şuanki elemanın sağına eşitse ya da
- Eğer prev değeri ile şuanki elemanın soluna eşitse ve şuanki elementin sağı boş ise
*/public static List<Integer> postOrderTraversalNonRecursive(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
List<Integer> result = new ArrayList<>();
TreeNode prev = root;
stack.push(root);
while (!stack.isEmpty()) {
TreeNode current = stack.peek();
boolean hasChild = (current.left != null || current.right != null);
boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null));
if (!hasChild || isPrevLastChild) {
current = stack.pop();
result.add(current.val);
prev = current;
} else {
if (current.right != null) {
stack.push(current.right);
}
if (current.left != null) {
stack.push(current.left);
}
}
}
return result;
} //[4, 3, 4, 2, 3, 1, 2]
Folksdev Youtube kanalımıza abone olmayı, beğeni ve yorum bırakmayı ve yeni video ve yayınlardan haberdar olmak için bildirimleri açmayı unutmayınız.
