Perbedaan antara pohon biner dan pohon pencarian biner

Adakah yang bisa menjelaskan perbedaan antara pohon biner dan pohon pencarian biner dengan sebuah contoh ?

Pohon biner: Pohon di mana setiap node memiliki hingga dua daun

  1
 / \
2   3

Pohon pencarian biner: Digunakan untuk pencarian . Pohon biner di mana anak kiri hanya berisi node dengan nilai lebih kecil dari node induk, dan di mana anak kanan hanya berisi node dengan nilai lebih besar dari atau sama dengan induknya.

  2
 / \
1   3

Binary Tree adalah bentuk pohon khusus dengan dua anak (anak kiri dan Anak kanan). Ini hanyalah representasi data dalam struktur Tree

Binary Search Tree (BST) adalah jenis khusus dari Binary Tree yang mengikuti kondisi berikut:

1. simpul anak kiri lebih kecil dari simpul induknya
2. simpul anak kanan lebih besar dari simpul induknya

Pohon biner terbuat dari node, di mana setiap node berisi "kiri" pointer, "kanan" pointer, dan elemen data. Pointer "root" menunjuk ke simpul paling atas di pohon. Pointer kiri dan kanan secara rekursif menunjuk ke "subtree" yang lebih kecil di kedua sisi. Pointer null menunjukkan pohon biner tanpa elemen - pohon kosong. Definisi rekursif formal adalah: pohon biner baik kosong (diwakili oleh pointer nol), atau terbuat dari satu node, di mana pointer kiri dan kanan (definisi rekursif di depan) setiap titik ke pohon biner.

Pohon pencarian biner (BST) atau "pohon biner berurutan" adalah jenis pohon biner di mana node disusun secara berurutan: untuk setiap node, semua elemen di subtree kirinya kurang dari node (<), dan semua elemen di subtree kanannya lebih besar dari node (>).

    5
   / \
  3   6 
 / \   \
1   4   9    

Pohon yang ditunjukkan di atas adalah pohon pencarian biner - simpul "root" adalah 5, dan simpul subtree kirinya (1, 3, 4) adalah <5, dan simpul subtree kanannya (6, 9) adalah> 5. Secara rekursif, masing-masing subtree juga harus mematuhi batasan pohon pencarian biner: pada subtree (1, 3, 4), 3 adalah root, 1 <3 dan 4> 3.

Perhatikan kata-kata yang tepat dalam masalah - "pohon pencarian biner" berbeda dari "pohon biner".

Seperti semua orang di atas telah menjelaskan tentang perbedaan antara pohon biner dan pohon pencarian biner, saya hanya menambahkan cara untuk menguji apakah pohon biner yang diberikan adalah pohon pencarian biner.

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()<max) && (node.getValue()>=min);

}

Semoga ini bisa membantu Anda. Maaf jika saya mengalihkan dari topik karena saya merasa perlu menyebutkan ini di sini.

Binary Tree adalah singkatan dari struktur data yang terdiri dari node yang hanya dapat memiliki dua referensi anak .

Binary Search Tree ( BST ) di sisi lain, adalah bentuk khusus dari struktur data Binary Tree di mana setiap node memiliki nilai yang sebanding, dan anak-anak bernilai lebih kecil melekat di sebelah kiri dan anak-anak bernilai lebih besar melekat di sebelah kanan.

Dengan demikian, semua BST adalah Pohon Biner tetapi hanya beberapa Pohon Biner mungkin juga BST . Beritahu bahwa BST adalah bagian dari Binary Tree .

Jadi, Binary Tree lebih dari struktur data umum daripada Binary Search Tree . Dan Anda juga harus memberi tahu bahwa Binary Search Tree adalah pohon yang diurutkan sedangkan tidak ada seperangkat aturan untuk Pohon Biner generik .

Pohon Biner

A Binary Treeyang bukan a BST;

         5
       /   \
      /     \
     9       2
    / \     / \
  15   17  19  21

Pohon Pencarian Biner (Pohon diurutkan)

Sebuah Binary Search Tree yang juga merupakan Pohon Binary ;

         50
       /    \
      /      \
     25      75
    /  \    /  \
  20    30 70   80

Properti Pohon Node Pencarian Biner

Juga beri tahu bahwa untuk setiap simpul induk di BST ;

• Semua node kiri memiliki nilai lebih kecil dari nilai node induk. Pada contoh atas, node dengan nilai {20, 25, 30} yang semuanya terletak di kiri ( keturunan kiri ) dari 50, lebih kecil dari 50.

• Semua node yang tepat memiliki nilai lebih besar dari nilai node induk. Dalam contoh atas, node dengan nilai {70, 75, 80} yang semuanya terletak di sebelah kanan ( keturunan kanan ) dari 50, lebih besar dari 50.

Tidak ada aturan seperti itu untuk Binary Tree Node. Satu-satunya aturan untuk Binary Tree Node adalah memiliki dua anak sehingga menjelaskan sendiri mengapa disebut biner .

Pohon pencarian biner adalah jenis khusus dari pohon biner yang memperlihatkan properti berikut: untuk setiap simpul n, setiap nilai simpul turunan di subtree kiri n lebih kecil dari nilai n, dan setiap nilai simpul turunan di subtree kanan adalah lebih besar dari nilai n.

Pohon biner

Pohon biner dapat berupa apa saja yang memiliki 2 anak dan 1 orang tua. Ini dapat diimplementasikan sebagai daftar atau array yang ditautkan, atau dengan API khusus Anda. Setelah Anda mulai menambahkan aturan yang lebih spesifik ke dalamnya, itu menjadi pohon yang lebih terspesialisasi . Implementasi yang paling umum diketahui adalah bahwa, tambahkan node yang lebih kecil di sebelah kiri dan yang lebih besar di sebelah kanan.

Misalnya, pohon biner berlabel ukuran 9 dan tinggi 3, dengan simpul akar yang nilainya 2. Pohon tidak seimbang dan tidak diurutkan . https://en.wikipedia.org/wiki/Binary_tree

Misalnya, di pohon di sebelah kiri, A memiliki 6 anak {B, C, D, E, F, G}. Itu dapat dikonversi menjadi pohon biner di sebelah kanan.

Pencarian Biner

Binary Search adalah teknik / algoritma yang digunakan untuk menemukan item spesifik pada rantai simpul. Pencarian biner bekerja pada array yang diurutkan .

Pencarian biner membandingkan nilai target dengan elemen tengah array; jika mereka tidak setara, setengah di mana target tidak bisa berbohong dihilangkan dan pencarian berlanjut pada setengah sisanya sampai berhasil atau setengah sisanya kosong. https://en.wikipedia.org/wiki/Binary_search_algorithm

Sebuah pohon yang mewakili pencarian biner . Array yang dicari di sini adalah [20, 30, 40, 50, 90, 100], dan nilai targetnya adalah 40.

Pohon pencarian biner

Ini adalah salah satu implementasi dari pohon biner. Ini khusus untuk pencarian .

Struktur pencarian biner dan struktur data B-tree didasarkan pada pencarian biner .

Pohon pencarian biner (BST), kadang-kadang disebut pohon biner yang dipesan atau disortir, adalah jenis wadah tertentu : struktur data yang menyimpan "item" (seperti angka, nama, dll.) Dalam memori. https://en.wikipedia.org/wiki/Binary_search_tree

Pohon pencarian biner ukuran 9 dan kedalaman 3, dengan 8 di root. Daunnya tidak ditarik.

Dan akhirnya skema yang bagus untuk perbandingan kinerja struktur data dan algoritma terkenal yang diterapkan:

Gambar diambil dari Algoritma (Edisi ke-4)

Pohon biner adalah pohon yang anak-anaknya tidak pernah lebih dari dua. Pohon pencarian biner mengikuti invarian bahwa anak kiri harus memiliki nilai lebih kecil dari kunci simpul akar, sedangkan anak kanan harus memiliki nilai lebih besar dari kunci simpul akar.

• Pohon pencarian biner: ketika inorder traversal dibuat pada pohon biner, Anda mendapatkan nilai yang diurutkan dari item yang dimasukkan
• Pohon biner: tidak ada urutan diurutkan ditemukan dalam semua jenis traversal

Untuk memeriksa apakah Pohon Biner yang diberikan adalah Pohon Pencarian Biner, berikut adalah Pendekatan Alternatif.

Traverse Tree Dalam Mode Inorder (mis. Anak Kiri -> Induk -> Anak Kanan), Simpan Data Node yang Dilalui dalam Variabel sementara katakanlah temp , sesaat sebelum menyimpan ke temp , Periksa apakah saat ini data Node lebih tinggi daripada yang sebelumnya atau tidak . Maka istirahat saja keluar, Pohon tidak Binary Search Tree lain melintasi sampai akhir.

Di bawah ini adalah contoh dengan Java:

public static boolean isBinarySearchTree(Tree root)
{
    if(root==null)
        return false;

    isBinarySearchTree(root.left);
    if(tree.data<temp)
        return false;
    else
        temp=tree.data;
    isBinarySearchTree(root.right);
    return true;
}

Pertahankan variabel temp di luar

Dalam pohon pencarian Biner, semua node diatur dalam urutan tertentu - node di sebelah kiri simpul root memiliki nilai lebih kecil dari root, dan semua node di sebelah kanan node memiliki nilai lebih besar dari nilai akar.

Sebuah pohon dapat disebut sebagai pohon biner jika dan hanya jika jumlah maksimum anak-anak dari salah satu node adalah dua.

Sebuah pohon dapat disebut sebagai pohon pencarian biner jika dan hanya jika jumlah maksimum anak dari salah satu node adalah dua dan anak kiri selalu lebih kecil dari anak kanan.