Javascript Cartesian Tree Sort Algoritması

Herkese merhaba, Javascript yazılarımıza kaldığımız yerden devam ediyoruz. Bu yazımızda sıralama algoritmalarından biri olan cartesian tree sort algoritmasını anlatacağım. Hadi başlayalım !

Cartesian Tree Nedir?

Cartesian Tree, bir dizi verisi verildiğinde, her bir öğenin (elemanın) bir düğüme (node) ve her bir düğümün iki çocuk düğümü (left ve right) olduğu bir ağaç yapısı oluşturur. Bu ağaç yapısı, dizi verisindeki öğelerin sıralı olarak bulunduğu şekilde düzenlenir.

Cartesian Tree algoritması, öncelikle iki adımdan oluşur:

1. Cartesian Tree yapısını oluşturma
2. Cartesian Tree üzerinde gezinme

Bu iki adımın her biri, bir dizi üzerinde birkaç farklı yöntemle gerçekleştirilebilir. Şimdi, JavaScript ile Cartesian Tree oluşturma örneğine geçelim.

Cartesian Tree Oluşturma

JavaScript ile Cartesian Tree yapısını oluşturmanın birkaç farklı yolu vardır. İlk olarak, aşağıdaki kod bloğunda verilen örnek bir dizi üzerinde çalışacağız:

const arr = [4, 8, 3, 7, 2, 6, 1, 5];

Yöntem 1: Stack Kullanarak

Bu yöntem, bir stack kullanarak ve her bir elemanın ait olduğu alt diziyi (subarray) tutarak gerçekleştirilir. Her yeni eleman stack’e eklenirken, önceki elemanların alt dizileri kontrol edilir ve yeni elemanın alt dizisine ait düğüm oluşturulur. Aşağıdaki kod bloğu, bu yöntemi göstermektedir:

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function buildCartesianTree(arr) {
  const stack = [];
  for (let i = 0; i < arr.length; i++) {
    const node = new TreeNode(arr[i]);
    while (stack.length && stack[stack.length - 1].val > arr[i]) {
      node.left = stack.pop();
    }
    if (stack.length) {
      stack[stack.length - 1].right = node;
    }
    stack.push(node);
  }
  return stack[0];
}

const arr = [4, 8, 3, 7, 2, 6, 1, 5];
const tree = buildCartesianTree(arr);
console.log(tree);

Yukarıdaki kod bloğunda, önce TreeNode adlı bir sınıf tanımlanır. Daha sonra, arr dizisi üzerinde for döngüsü oluşturulur ve her eleman için yeni bir TreeNode oluşturulur. Ardından, while döngüsü, stack içindeki önceki elemanların alt dizilerinin kontrol edilmesi için kullanılır. Eğer bir önceki elemanın değeri, şu anki elemanın değerinden büyükse, önceki elemanın sol düğümü olarak atanır. Daha sonra, şu anki elemanın sağ düğümü olarak bir sonraki öğe atanır. Son olarak, stack’e yeni eleman eklenir.

Yöntem 2: Divide and Conquer Yöntemi

Bu yöntem, bir recursive fonksiyon kullanarak gerçekleştirilir. İlk olarak, dizinin en küçük elemanı bulunur ve bu elemanın index’i hesaplanır. Daha sonra, sol ve sağ alt diziler recursive olarak çağrılır ve sol ve sağ düğümler oluşturulur. Aşağıdaki kod bloğu, bu yöntemi göstermektedir:

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function buildCartesianTree(arr) {
  if (!arr.length) {
    return null;
  }
  const min = Math.min(...arr);
  const index = arr.indexOf(min);
  const node = new TreeNode(min);
  node.left = buildCartesianTree(arr.slice(0, index));
  node.right = buildCartesianTree(arr.slice(index + 1));
  return node;
}

const arr = [4, 8, 3, 7, 2, 6, 1, 5];
const tree = buildCartesianTree(arr);
console.log(tree);

Yukarıdaki kod bloğunda, önce TreeNode adlı bir sınıf tanımlanır. Daha sonra, buildCartesianTree adlı bir recursive fonksiyon tanımlanır. İlk olarak, arr dizisi boşsa null döndürülür. Daha sonra, en küçük eleman bulunur ve bu elemanın index’i hesaplanır. TreeNode oluşturulur ve sol ve sağ alt diziler recursive olarak çağrılır. Son olarak, TreeNode döndürülür.

Sonuç

Cartesian Tree algoritması, bir dizi verisi üzerinde sıralama yapmak için kullanışlı bir algoritmadır. Bu algoritma, JavaScript gibi dillerde birkaç farklı yöntemle uygulanabilir. Yukarıdaki örnekler, Cartesian Tree algoritmasının nasıl uygulanabileceği hakkında bir fikir vermek için kullanılabilir.

Evet Javascript ile cartesian tree sort algoritması bu şekilde idi. Tüm Javascript yazılarımıza buraya, diğer sıralama algoritmaları yazılarımıza buraya tıklayarak ulaşabilirsiniz. Herkese hayırlı günler.