Partage de code d'exemple d'algorithme Java-Binary Search Tree (BST)

黄舟

Libérer： 2017-05-07 09:37:43

original

1973 Les gens l'ont consulté

Binary Search Tree est un algorithme qui combine la flexibilité de l'insertion de listes chaînées avec l'efficacité de la recherche ordonnée de tableaux. Ce qui suit est le code pur pour implémenter diverses méthodes de BST.

Définition de l'arbre de recherche binaire (BST)

L'arbre de tri binaire est soit un arbre vide, soit c'est un arbre binaire avec les propriétés suivantes :

Si le sous-arbre de gauche n'est pas vide, alors les valeurs de tous les nœuds du sous-arbre de gauche are est inférieur ou égal à la valeur de son nœud racine

Si le sous-arbre de droite n'est pas vide, alors sous-arbre droit Les valeurs de tous les nœuds sur sont supérieures ou égales à la valeur de son nœud racine

et les sous-arbres gauche et droit sont également Implémenter

clé de recherche pour obtenir la valeur du nœud de base de l'arbre de tri binaire

public class BST<K extends Comparable<K>, V> {

    private Node root;

    private class Node {

        private K key;
        private V value;
        private Node left;
        private Node right;
        private int N;

        public Node(K key, V value, int N) {
            this.key = key;
            this.value = value;
            this.N = N;
        }
    }

    public int size() {
        return size(root);
    }

    private int size(Node x) {
        if (x == null)
            return 0;
        else
            return x.N;
    }
}

Copier après la connexion

respectivement ——get

public V get(K key) {
    return get(root, key);
}

private V get(Node root, K key) {

    if (root == null)
        return null;

    int comp = key.compareTo(root.key);

    if (comp == 0)
        return root.value;
    else if (comp < 0)
        return get(root.left, key);
    else
        return get(root.right, key);

}

Copier après la connexion

Modifier la valeur/insérer une nouvelle valeur——put

  public void put(K key, V value) {
        root = put(root, key, value);
    }

    private Node put(Node root, K key, V value) {

        if (root == null)
            return new Node(key, value, 1);

        int comp = key.compareTo(root.key);
        if (comp == 0)
            root.value = value;
        else if (comp < 0)
            root.left = put(root.left, key, value);
        else
            root.right = put(root.right, key, value);

        root.N = size(root.left) + size(root.right) + 1;

        return root;
    }

Copier après la connexion

valeur maximale/valeur minimale ——min /max

  public K min() {
        return min(root).key;
    }

    private Node min(Node root) {

        if (root.left == null)
            return root;

        return min(root.left);

    }

Copier après la connexion

    public K max() {
        return max(root).key;
    }

    private Node max(Node root2) {

        if (root.right == null)
            return root;

        return max(root.right);

    }

Copier après la connexion

Arrondi vers le haut/vers le bas - sol/plafond

  public K floor(K key) {
        Node x = floor(root, key);
        if (x == null)
            return null;
        return x.key;
    }

    private Node floor(Node root, K key) {

        if (root == null)
            return null;

        int comp = key.compareTo(root.key);

        if (comp < 0)
            return floor(root.left, key);
        else if (comp > 0 && root.right != null
                && key.compareTo(min(root.right).key) >= 0)
            return floor(root.right, key);
        else
            return root;

    }

Copier après la connexion

    public K ceiling(K key) {
        Node x = ceiling(root, key);
        if (x == null)
            return null;
        return x.key;
    }

    private Node ceiling(Node root, K key) {

        if (root == null)
            return null;

        int comp = key.compareTo(root.key);

        if (comp > 0)
            return ceiling(root.right, key);
        else if (comp < 0 && root.left != null
                && key.compareTo(max(root.left).key) >= 0)
            return ceiling(root.left, key);
        else
            return root;

    }

Copier après la connexion

sélection --select

  public K select(int k) {
        //找出BST中序号为k的键
        return select(root, k);
    }

    private K select(Node root, int k) {

        if (root == null)
            return null;

        int comp = k - size(root.left);

        if (comp < 0)
            return select(root.left, k);
        else if (comp > 0)
            return select(root.right, k - (size(root.left) + 1));
        else
            return root.key;

    }

Copier après la connexion

rank --rank

  public int rank(K key) {
        //找出BST中键为key的序号是多少
        return rank(root, key);
    }

    private int rank(Node root, K key) {

        if (root == null)
            return 0;

        int comp = key.compareTo(root.key);

        if (comp == 0)
            return size(root.left);
        else if (comp < 0)
            return rank(root.left, key);
        else
            return 1 + size(root.left) + rank(root.right, key);

    }

Copier après la connexion

supprimer min /max touches --deleteMin/deleteMax

  public void deleteMin() {
        root = deleteMin(root);
    }

    private Node deleteMin(Node root) {

        if (root.left == null)
            return root.right;

        root.left = deleteMin(root.left);
        root.N = size(root.left) + size(root.right) + 1;
        return root;

    }

Copier après la connexion

    public void deleteMax() {
        root = deleteMax(root);
    }

    private Node deleteMax(Node root) {

        if (root.right == null)
            return root.left;

        root.right = deleteMax(root.right);
        root.N = size(root.left) + size(root.right) + 1;
        return root;

    }

Copier après la connexion

Supprimer n'importe quelle clé——supprimer

  public void delete(K key) {
        root = delete(root, key);
    }

    private Node delete(Node root, K key) {

        if (root == null)
            return null;

        int comp = key.compareTo(root.key);

        if (comp == 0) {

            if (root.right == null)
                return root = root.left;
            if (root.left == null)
                return root = root.right;

            Node t = root;
            root = min(t.right);

            root.left = t.left;
            root.right = deleteMin(t.right);

        } else if (comp < 0)
            root.left = delete(root.left, key);
        else
            root.right = delete(root.right, key);

        root.N = size(root.left) + size(root.right) + 1;
        return root;

    }

Copier après la connexion

Dans l'ordre imprimer arbre——imprimer

  public void print() {
        print(root);
    }

    private void print(Node root) {

        if (root == null)
            return;
        print(root.left);
        System.out.println(root.key);
        print(root.right);

    }

Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!