Menü

Java'da İkili Arama Ağacı - Uygulama ve Kod Örnekleri

  • Ana
  • Diğer
  • Java'da İkili Arama Ağacı - Uygulama ve Kod Örnekleri

binary search tree java implementation code examples

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

Bu Eğitim Java'da İkili Arama Ağacını Kapsar. Java'da BST Oluşturmayı, Bir Öğeyi Eklemeyi, Kaldırmayı ve Aramayı, Geçiş Yapmayı ve BST Uygulamayı Öğreneceksiniz:

İkili arama ağacı (bundan sonra BST olarak anılacaktır) bir tür ikili ağaçtır. Düğüm tabanlı ikili ağaç olarak da tanımlanabilir. BST, 'Sıralı İkili Ağaç' olarak da adlandırılır. BST'de, sol alt ağaçtaki tüm düğümler, kök düğümün değerinden daha düşük değerlere sahiptir.

Benzer şekilde, BST'nin sağ alt ağacının tüm düğümleri, kök düğümün değerinden daha büyük değerlere sahiptir. Düğümlerin bu sıralaması, ilgili alt ağaçlar için de doğru olmalıdır.

=> Özel Java Eğitimi Eğitim Dizisi İçin Burayı Ziyaret Edin.

Java

Ne öğreneceksin:

Java'da İkili Arama Ağacı

BST, yinelenen düğümlere izin vermez.

Aşağıdaki diyagram bir BST Temsili gösterir:

BST Temsilciliği

Yukarıda örnek bir BST gösterilmektedir. 20'nin bu ağacın kök düğümü olduğunu görüyoruz. Soldaki alt ağaç, 20'den küçük tüm düğüm değerlerine sahiptir. Sağ alt ağaç, 20'den büyük tüm düğümlere sahiptir. Yukarıdaki ağacın BST özelliklerini karşıladığını söyleyebiliriz.

BST veri yapısının, öğelerin eklenmesi / silinmesi ve aranması söz konusu olduğunda Diziler ve Bağlantılı listeye kıyasla çok verimli olduğu düşünülmektedir.

BST bir elemanı aramak için O (log n) süresi alır. Öğeler sıralandıkça, bir öğe ararken her adımda alt ağacın yarısı atılır. Bu mümkün olur çünkü aranacak elemanın kaba konumunu kolayca belirleyebiliriz.

Benzer şekilde, ekleme ve silme işlemleri BST'de daha verimlidir. Yeni bir eleman eklemek istediğimizde, elemanı hangi alt ağaca (sol veya sağ) ekleyeceğimizi kabaca biliyoruz.

İkili Arama Ağacı (BST) Oluşturma

Bir dizi öğe verildiğinde, bir BST oluşturmamız gerekir.

Bunu aşağıda gösterildiği gibi yapalım:

Verilen dizi: 45, 10, 7, 90, 12, 50, 13, 39, 57

İlk önce en üstteki öğeyi, yani 45'i kök düğüm olarak ele alalım. Buradan, daha önce tartışılan özellikleri göz önünde bulundurarak BST'yi oluşturmaya devam edeceğiz.

Bir ağaç oluşturmak için dizideki her bir elemanı kök ile karşılaştıracağız. Ardından elementi ağaçta uygun bir konuma yerleştireceğiz.

BST için tüm oluşturma süreci aşağıda gösterilmektedir.

İkili Arama Ağacı - Oluşturma Süreci 1

bst inşaat

tamamlandı BST
BST tamamlandı

İkili Arama Ağacı İşlemleri

BST, çeşitli işlemleri destekler. Aşağıdaki tablo Java'da BST tarafından desteklenen yöntemleri göstermektedir. Bu yöntemlerin her birini ayrı ayrı tartışacağız.

Yöntem / operasyonAçıklama
EkleBST özelliklerini ihlal etmeyerek BST'ye bir öğe ekleyin.
SilBelirli bir düğümü BST'den kaldırın. Düğüm, kök düğüm, yaprak olmayan veya yaprak düğüm olabilir.
AramaBST'de verilen elemanın konumunu arayın. Bu işlem, ağacın belirtilen anahtarı içerip içermediğini kontrol eder.

BST'ye Bir Öğe Ekleme

BST'ye her zaman bir yaprak düğüm olarak bir öğe eklenir.

Aşağıda, bir eleman eklemek için adımlar verilmiştir.

  1. Kökten başlayın.
  2. Eklenecek öğeyi kök düğümle karşılaştırın. Kökten küçükse, soldaki alt ağaçtan veya sağ alt ağaçtan çapraz geçiş yapın.
  3. Alt ağacı istenen alt ağacın sonuna kadar çaprazlayın. Düğümü uygun alt ağaca yaprak düğüm olarak ekleyin.

BST'nin ekleme işleminin bir resmine bakalım.

Aşağıdaki BST'yi düşünün ve ağaca öğe 2'yi ekleyelim.

BST - İşlem Ekle
Şekil 1
BST
şekil 2

BST için ekleme işlemi yukarıda gösterilmiştir. Şekil (1) 'de, BST'ye eleman 2'yi eklemek için geçtiğimiz yolu gösteriyoruz. Ayrıca her düğümde kontrol edilen koşulları da gösterdik. Özyinelemeli karşılaştırmanın bir sonucu olarak, şekil (2) 'de gösterildiği gibi öğe 2, 1'in sağ çocuğu olarak eklenir.

BST'de Arama İşlemi

BST'de bir eleman olup olmadığını aramak için, tekrar kökten başlayıp, aranacak elemanın kökten küçük veya büyük olmasına bağlı olarak sol veya sağ alt ağaca geçiyoruz.

Aşağıda, izlememiz gereken adımlar listelenmiştir.

  1. Aranacak öğeyi kök düğümle karşılaştırın.
  2. Anahtar (aranacak öğe) = kök ise, kök düğüme dönün.
  3. Aksi takdirde anahtar
  4. Başka bir sağ alt ağacı çaprazlayın.
  5. Anahtar bulunana veya ağacın sonuna ulaşılana kadar alt ağaç öğelerini tekrar tekrar karşılaştırın.

Arama işlemini bir örnekle gösterelim. Anahtar = 12'yi aramamız gerektiğini düşünün.

Aşağıdaki şekilde, bu elemanı aramak için izlediğimiz yolu izleyeceğiz.

BST

Yukarıdaki şekilde gösterildiği gibi, önce anahtarı kök ile karşılaştırıyoruz. Anahtar daha büyük olduğu için, sağ alt ağaçtan geçiyoruz. Sağ alt ağaçta, anahtarı yine sağ alt ağaçtaki ilk düğümle karşılaştırıyoruz.

Anahtarın 15'ten küçük olduğunu bulduk. Dolayısıyla, düğüm 15'in sol alt ağacına geçiyoruz. 15'in hemen sol düğümü, anahtarla eşleşen 12'dir. Bu noktada, aramayı durdurur ve sonucu döndürürüz.

Öğeyi BST'den Kaldır

BST'den bir düğümü sildiğimizde, aşağıda tartışıldığı gibi üç olasılık vardır:

Düğüm Bir Yaprak Düğümüdür

Silinecek düğüm bir yaprak düğüm ise, bu düğümü doğrudan alt düğümü olmadığı için silebiliriz. Bu, aşağıdaki resimde gösterilmektedir.

Düğüm bir yaprak düğümdür

Yukarıda gösterildiği gibi, düğüm (12) bir yaprak düğümdür ve hemen silinebilir.

Düğümün Yalnızca Bir Çocuğu Var

Bir çocuğu olan düğümü silmemiz gerektiğinde, düğümdeki çocuğun değerini kopyalıyor ve ardından çocuğu siliyoruz.

Düğümün Yalnızca Bir Çocuğu Var

Yukarıdaki diyagramda, bir çocuk 50'ye sahip olan 90 düğümünü silmek istiyoruz. Bu yüzden 50 değerini 90 ile değiştiriyoruz ve sonra şimdi bir alt düğüm olan 90 düğümünü siliyoruz.

Düğümün İki Çocuğu Var

Silinecek bir düğümün iki çocuğu olduğunda, düğümün sıralı (sol-kök-sağ) halefiyle düğümü değiştiririz veya düğümün sağ alt ağacı boş değilse basitçe sağ alt ağaçtaki minimum düğümü söyleriz. Düğümü bu minimum düğümle değiştiriyoruz ve düğümü siliyoruz.

Düğümün iki çocuğu var

Yukarıdaki diyagramda, BST'nin kök düğümü olan 45 düğümünü silmek istiyoruz. Bu düğümün doğru alt ağacının boş olmadığını görüyoruz. Sonra sağ alt ağaçtan geçip 50 düğümünün buradaki minimum düğüm olduğunu bulduk. Yani bu değeri 45'in yerine değiştiriyoruz ve sonra 45'i siliyoruz.

Ağacı kontrol edersek, bir BST'nin özelliklerini yerine getirdiğini görürüz. Böylece düğüm değişimi doğruydu.

Java'da İkili Arama Ağacı (BST) Uygulaması

Aşağıdaki Java programı, örnek olarak resimde kullanılan aynı ağacı kullanarak yukarıdaki tüm BST işlemlerinin bir gösterimini sağlar.

Java mülakat soruları ve yanıtlarında web hizmetleri
class BST_class { //node class that defines BST node class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } // BST root node Node root; // Constructor for BST =>initial empty tree BST_class(){ root = null; } //delete a node from BST void deleteKey(int key) { root = delete_Recursive(root, key); } //recursive delete function Node delete_Recursive(Node root, int key) { //tree is empty if (root == null) return root; //traverse the tree if (key root.key) //traverse right subtree root.right = delete_Recursive(root.right, key); else { // node contains only one child if (root.left == null) return root.right; else if (root.right == null) return root.left; // node has two children; //get inorder successor (min value in the right subtree) root.key = minValue(root.right); // Delete the inorder successor root.right = delete_Recursive(root.right, root.key); } return root; } int minValue(Node root) { //initially minval = root int minval = root.key; //find minval while (root.left != null) { minval = root.left.key; root = root.left; } return minval; } // insert a node in BST void insert(int key) { root = insert_Recursive(root, key); } //recursive insert function Node insert_Recursive(Node root, int key) { //tree is empty if (root == null) { root = new Node(key); return root; } //traverse the tree if (key root.key) //insert in the right subtree root.right = insert_Recursive(root.right, key); // return pointer return root; } // method for inorder traversal of BST void inorder() { inorder_Recursive(root); } // recursively traverse the BST void inorder_Recursive(Node root) { if (root != null) { inorder_Recursive(root.left); System.out.print(root.key + ' '); inorder_Recursive(root.right); } } boolean search(int key) { root = search_Recursive(root, key); if (root!= null) return true; else return false; } //recursive insert function Node search_Recursive(Node root, int key) // Base Cases: root is null or key is present at root if (root==null } class Main{ public static void main(String() args) { //create a BST object BST_class bst = new BST_class(); /* BST tree example 45 / 10 90 / / 7 12 50 */ //insert data into BST bst.insert(45); bst.insert(10); bst.insert(7); bst.insert(12); bst.insert(90); bst.insert(50); //print the BST System.out.println('The BST Created with input data(Left-root-right):'); bst.inorder(); //delete leaf node System.out.println(' The BST after Delete 12(leaf node):'); bst.deleteKey(12); bst.inorder(); //delete the node with one child System.out.println(' The BST after Delete 90 (node with 1 child):'); bst.deleteKey(90); bst.inorder(); //delete node with two children System.out.println(' The BST after Delete 45 (Node with two children):'); bst.deleteKey(45); bst.inorder(); //search a key in the BST boolean ret_val = bst.search (50); System.out.println(' Key 50 found in BST:' + ret_val ); ret_val = bst.search (12); System.out.println(' Key 12 found in BST:' + ret_val ); } }

Çıktı:

BST Uygulaması - Çıktı

Java'da İkili Arama Ağacı (BST) Geçişi

Bir ağaç hiyerarşik bir yapıdır, bu nedenle onu diziler gibi diğer veri yapıları gibi doğrusal olarak hareket ettiremeyiz. Tüm alt ağaçlarının ve düğümlerinin en az bir kez ziyaret edilebilmesi için her tür ağacın özel bir şekilde geçilmesi gerekir.

Kök düğümün, sol alt ağacın ve sağ alt ağacın bir ağaçta geçiş sırasına bağlı olarak, aşağıda gösterildiği gibi belirli geçişler vardır:

  • Sıralı Geçiş
  • Ön Sipariş Geçişi
  • Sipariş Sonrası Geçiş

Yukarıdaki tüm çapraz geçişler önce derinlik tekniğini kullanır, yani ağaç derinlemesine hareket ettirilir.

Ağaçlar ayrıca geçiş için en önce tekniğini kullanır. Bu tekniği kullanan yaklaşım denir 'Seviye Sırası' geçiş.

Bu bölümde, aşağıdaki BST'yi örnek olarak kullanarak her bir geçişi göstereceğiz.

Java

Yukarıdaki diyagramda gösterildiği gibi BST ile, yukarıdaki ağaç için seviye sırası geçişi:

Seviye Sırası Geçişi: 10 6 12 4 8

Sıralı Geçiş

Sıralı geçiş yaklaşımı sırayla BST'yi geçti, Sol alt ağaç => RootNode => Sağ alt ağaç . Sıralı geçiş, bir BST'nin azalan düğüm dizisini sağlar.

InOrder Traversal için InOrder (bstTree) algoritması aşağıda verilmiştir.

  1. InOrder (left_subtree) kullanarak sol alt ağacı çaprazlayın
  2. Kök düğümü ziyaret edin.
  3. InOrder (sağ_altağaç) kullanarak sağ alt ağacı çaprazlayın

Yukarıdaki ağacın sıralı geçişi:

4 6 8 10 12

Görüldüğü gibi, sıralı geçişin bir sonucu olarak düğümlerin sırası azalan sıradadır.

Ön Sipariş Geçişi

Ön sipariş geçişinde, önce kök, ardından sol alt ağaç ve sağ alt ağaç ziyaret edilir. Ön sipariş geçişi, ağacın bir kopyasını oluşturur. Önek ifadesi elde etmek için ifade ağaçlarında da kullanılabilir.

PreOrder (bst_tree) geçiş algoritması aşağıda verilmiştir:

  1. Kök düğümü ziyaret edin
  2. PreOrder (left_subtree) ile sol alt ağacı çaprazlayın.
  3. PreOrder (right_subtree) ile sağ alt ağacı çaprazlayın.

Yukarıda verilen BST için ön sipariş geçişi şöyledir:

10 6 4 8 12

Sipariş Sonrası Geçiş

PostOrder geçişi, BST'yi şu sırayla dolaşır: Sol alt ağaç-> Sağ alt ağaç-> Kök düğüm . PostOrder geçişi, ağacı silmek veya ifade ağaçları olması durumunda sonek ifadesini elde etmek için kullanılır.

PostOrder (bst_tree) geçiş algoritması aşağıdaki gibidir:

  1. PostOrder (left_subtree) ile sol alt ağacı çaprazlayın.
  2. PostOrder (right_subtree) ile sağ alt ağacı çaprazlayın.
  3. Kök düğümü ziyaret edin

Yukarıdaki örnek BST için postOrder geçişi:

4 8 6 12 10

Daha sonra, bu geçişleri bir Java uygulamasında önce derinlik tekniğini kullanarak uygulayacağız.

//define node of the BST class Node { int key; Node left, right; public Node(int data){ key = data; left = right = null; } } //BST class class BST_class { // BST root node Node root; BST_class(){ root = null; } //PostOrder Traversal - Left:Right:rootNode (LRn) void postOrder(Node node) { if (node == null) return; // first traverse left subtree recursively postOrder(node.left); // then traverse right subtree recursively postOrder(node.right); // now process root node System.out.print(node.key + ' '); } // InOrder Traversal - Left:rootNode:Right (LnR) void inOrder(Node node) { if (node == null) return; //first traverse left subtree recursively inOrder(node.left); //then go for root node System.out.print(node.key + ' '); //next traverse right subtree recursively inOrder(node.right); } //PreOrder Traversal - rootNode:Left:Right (nLR) void preOrder(Node node) { if (node == null) return; //first print root node first System.out.print(node.key + ' '); // then traverse left subtree recursively preOrder(node.left); // next traverse right subtree recursively preOrder(node.right); } // Wrappers for recursive functions void postOrder_traversal() { postOrder(root); } void inOrder_traversal() { inOrder(root); } void preOrder_traversal() { preOrder(root); } } class Main{ public static void main(String() args) { //construct a BST BST_class tree = new BST_class(); /* 45 // \ 10 90 // \ 7 12 */ tree.root = new Node(45); tree.root.left = new Node(10); tree.root.right = new Node(90); tree.root.left.left = new Node(7); tree.root.left.right = new Node(12); //PreOrder Traversal System.out.println('BST => PreOrder Traversal:'); tree.preOrder_traversal(); //InOrder Traversal System.out.println(' BST => InOrder Traversal:'); tree.inOrder_traversal(); //PostOrder Traversal System.out.println(' BST => PostOrder Traversal:'); tree.postOrder_traversal(); } }

Çıktı:

BST Transversal Uygulaması - Çıktı

Sıkça Sorulan Sorular

S # 1) Neden bir İkili Arama Ağacına ihtiyacımız var?

Cevap : Doğrusal veri yapısında ikili arama tekniğini kullanan diziler gibi öğeleri arama şeklimizde, ağaç hiyerarşik bir yapıdır, bir ağaçtaki öğeleri bulmak için kullanılabilecek bir yapıya ihtiyacımız var.

Bu, resimdeki öğelerin verimli bir şekilde aranmasında bize yardımcı olan İkili arama ağacının geldiği yerdir.

S # 2) Bir İkili Arama Ağacının özellikleri nelerdir?

Cevap : İkili ağaç kategorisine ait bir İkili Arama Ağacı aşağıdaki özelliklere sahiptir:

  • İkili arama ağacında depolanan veriler benzersizdir. Yinelenen değerlere izin vermez.
  • Sol alt ağacın düğümleri, kök düğümden daha küçüktür.
  • Sağ alt ağacın düğümleri, kök düğümden daha büyüktür.

S # 3) İkili Arama Ağacının uygulamaları nelerdir?

Cevap : Matematikteki bazı sürekli fonksiyonları çözmek için İkili Arama Ağaçlarını kullanabiliriz. Verilerin hiyerarşik yapılarda aranması İkili Arama Ağaçları ile daha verimli hale gelir. Her adımda aramayı yarı alt ağaç azaltıyoruz.

S # 4) İkili Ağaç ile İkili Arama Ağacı arasındaki fark nedir?

Cevap: İkili ağaç, ebeveyn olarak bilinen her düğümün en fazla iki çocuğa sahip olabileceği hiyerarşik bir ağaç yapısıdır. Bir ikili arama ağacı, ikili ağacın tüm özelliklerini yerine getirir ve aynı zamanda kendine özgü özelliklerine sahiptir.

İkili bir arama ağacında, sol alt ağaçlar kök düğümden daha küçük veya ona eşit düğümler içerir ve sağ alt ağaç, kök düğümden daha büyük düğümlere sahiptir.

S # 5) İkili Arama Ağacı Benzersiz mi?

Cevap : Bir ikili arama ağacı, bir ikili ağaç kategorisine aittir. Yinelenen değerlere izin vermemesi açısından benzersizdir ve ayrıca tüm öğeleri belirli bir sıralamaya göre sıralanır.

Sonuç

İkili Arama ağaçları, ikili ağaç kategorisinin bir parçasıdır ve esas olarak hiyerarşik verileri aramak için kullanılır. Ayrıca bazı matematik problemlerini çözmek için de kullanılır.

Bu eğiticide, İkili Arama Ağacının uygulanmasını gördük. Ayrıca BST üzerinde yapılan çeşitli operasyonları çizimleriyle gördük ve ayrıca BST için geçişleri araştırdık.

=> Basit Java Eğitim Serisine Buradan Dikkat Edin.

Önerilen Kaynaklar

^