Analisis contoh pokok carian binari Java

Konsep

Pokok carian binari juga dipanggil pokok pengisihan binari Ia sama ada pokok kosong atau mempunyai ciri-ciri berikut Pokok binari:
1. Jika subpokok kirinya tidak kosong, maka nilai semua nod pada subpokok kiri adalah kurang daripada nilai nod akar.
2. Jika subpokok kanannya tidak kosong, maka nilai semua nod pada subpokok kanan adalah lebih besar daripada nilai nod akar.
3. Subpohon kiri dan kanannya juga merupakan pepohon carian binari masing-masing

Amalan langsung

Penyediaan: tentukan kelas nod pokok dan perduaan kelas pokok carian.

Fungsi carian untuk pokok binari

Andaikan kita telah membina pokok binari seperti yang ditunjukkan di bawah

Persoalan pertama yang perlu kita fikirkan ialah bagaimana untuk mencari sama ada nilai tertentu berada dalam pokok binari?

Mengikut logik di atas, mari kita cari kaedah Buat penambahbaikan.

Operasi sisipan mencari pokok binari

Berdasarkan logik di atas, mari tulis kod untuk memasukkan nod .

Operasi mencari pepohon binari untuk memadam nod - kesukaran

Mari kita analisis semula: bagaimana curDummy dan parentDummy mencari "kambing hitam" "daripada.

Program Keseluruhan - Simulasikan pelaksanaan pepohon carian binari

class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}


public class BinarySearchTree {
    TreeNode root;

    //在二叉树中 寻找指定 val 值的节点
    // 找到了，返回其节点地址；没找到返回 null
    public TreeNode search(int key){
        TreeNode cur = this.root;
        while(cur != null){
            if(cur.val == key){
                return cur;
            }else if(cur.val < key){
                cur = cur.right;
            }else{
                cur = cur.left;
            }
        }
        return null;
    }
    // 插入操作
    public boolean insert(int key){
        if(this.root == null){
            this.root = new TreeNode(key);
            return true;
        }
        TreeNode cur = this.root;
        TreeNode parent = null;
        while(cur!=null){
            if(key > cur.val){
                parent  = cur;
                cur = cur.right;
            }else if(cur.val == key){
                return false;
            }else{
                parent  = cur;
                cur = cur.left;
            }
        }
        TreeNode node = new TreeNode(key);
        if(parent .val > key){
            parent.left = node;
        }else{
            parent.right = node;
        }
        return true;
    }
    // 删除操作
    public void remove(int key){
        TreeNode cur = root;
        TreeNode parent = null;
        // 寻找 删除节点位置。
        while(cur!=null){
            if(cur.val == key){
                removeNode(cur,parent);// 真正删除节点的代码
                break;
            }else if(cur.val < key){
                parent = cur;
                cur = cur.right;
            }else{
                parent = cur;
                cur = cur.left;
            }
        }
    }
    // 辅助删除方法：真正删除节点的代码
    private void removeNode(TreeNode cur,TreeNode parent){
        // 情况一
        if(cur.left == null){
            if(cur == this.root){
                this.root = this.root.right;
            }else if( cur == parent.left){
                parent.left = cur.right;
            }else{
                parent.right = cur.right;
            }
            // 情况二
        }else if(cur.right == null){
            if(cur == this.root){
                this.root = root.left;
            }else if(cur == parent.left){
                parent.left = cur.left;
            }else{
                parent.right = cur.left;
            }
            // 情况三
        }else{
            // 第二种方法：在删除节点的右子树中寻找最小值，
            TreeNode parentDummy = cur;
            TreeNode curDummy = cur.right;
            while(curDummy.left != null){
                parentDummy = curDummy;
                curDummy = curDummy.left;
            }
            // 此时 curDummy 指向的 cur 右子树
            cur.val = curDummy.val;
            if(parentDummy.left != curDummy){
                parentDummy.right = curDummy.right;
            }else{
                parentDummy.left = curDummy.right;
            }

        }
    }
   // 中序遍历
    public void inorder(TreeNode root){
        if(root == null){
            return;
        }
        inorder(root.left);
        System.out.print(root.val+" ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        int[] array = {10,8,19,3,9,4,7};
        BinarySearchTree binarySearchTree = new BinarySearchTree();
        for (int i = 0; i < array.length; i++) {
            binarySearchTree.insert(array[i]);
        }
        binarySearchTree.inorder(binarySearchTree.root);
        System.out.println();// 换行
        System.out.print("插入重复的数据 9：" + binarySearchTree.insert(9));
        System.out.println();// 换行
        System.out.print("插入不重复的数据 1：" + binarySearchTree.insert(1));
        System.out.println();// 换行
        binarySearchTree.inorder(binarySearchTree.root);
        System.out.println();// 换行
        binarySearchTree.remove(19);
        System.out.print("删除元素 19 ：");
        binarySearchTree.inorder(binarySearchTree.root);
        System.out.println();// 换行
        System.out.print("查找不存在的数据50 ：");
        System.out.println(binarySearchTree.search(50));
        System.out.print("查找存在的数据 7：");
        System.out.println(binarySearchTree.search(7));
    }
}

Analisis Prestasi

  Kedua-dua operasi sisipan dan pemadaman mesti dicari terlebih dahulu Kecekapan carian mewakili prestasi setiap operasi dalam pepohon carian binari.
 
  Untuk pepohon carian binari dengan n nod, jika kebarangkalian mencari setiap elemen adalah sama, maka purata panjang carian bagi pepohon carian binari ialah bilangan nod dalam perduaan pokok carian Fungsi kedalaman, iaitu, lebih dalam nod, lebih banyak perbandingan yang diperlukan.
 
  Tetapi untuk set kod kunci yang sama, jika susunan pemasukan setiap kod kunci berbeza, pepohon carian binari dengan struktur berbeza boleh diperolehi:

Jika kita boleh memastikan bahawa perbezaan ketinggian antara subpokok kiri dan kanan pepohon carian binari tidak melebihi 1. Cuba memenuhi syarat keseimbangan tinggi.
Ini menjadi pokok AVL (pokok carian binari seimbang ketinggian). Pokok AVL juga mempunyai kelemahan: ia memerlukan putaran yang kerap. Banyak kecekapan yang sia-sia.
Pada ketika ini, pokok merah-hitam dilahirkan untuk mengelakkan lebih banyak putaran.

Hubungan antara set kelas java

TreeMap dan TreeSet ialah Peta dan Set yang dilaksanakan menggunakan pepohon carian dalam java sebenarnya, pokok merah-hitam digunakan, dan merah Pokok hitam adalah pokok carian binari yang lebih kurang seimbang, iaitu berdasarkan penentusahan harta pokok carian binari + warna dan merah-hitam berkenaan kandungan pokok merah-hitam, blogger akan menulis blog selepas mempelajarinya.

Atas ialah kandungan terperinci Analisis contoh pokok carian binari Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!