BST(Java-Binary Search Tree) 알고리즘 샘플 코드 공유

이진 검색 트리는 연결 목록 삽입의 유연성과 순서 있는 배열 검색의 효율성을 결합한 알고리즘입니다. 다음은 BST의 다양한 메소드를 구현하기 위한 순수 코드이다.

이진 검색 트리(BST) 정의

이진 정렬 트리는 빈 트리이거나 다음 속성을 가진 이진 트리 :

1. 왼쪽 하위 트리가 비어 있지 않으면 왼쪽 하위 트리 은 루트 노드

의 값
2. 보다 작거나 같습니다. 오른쪽 하위 트리가 비어 있지 않으면

   오른쪽 하위 트리 모든 노드의 값은 해당 루트 노드

   값보다
크거나
3. 같습니다. 왼쪽 및 오른쪽 하위 트리도 이진 정렬 트리의 기본 노드에 대해

   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;
       }
   }

를 구현합니다.

각각 - 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);

}

값 수정/새 값 삽입——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;
    }

최대값/최소값——min /max

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

    private Node min(Node root) {

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

        return min(root.left);

    }

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

    private Node max(Node root2) {

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

        return max(root.right);

    }

올림/내림——바닥/천장

  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;

    }

    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;

    }

선택——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;

    }

순위 - 순위

  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);

    }

최소/최대 키 삭제 - 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;

    }

rrree

키 삭제 - 삭제

    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;

    }

순차 인쇄 트리——인쇄

  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;

    }

위 내용은 BST(Java-Binary Search Tree) 알고리즘 샘플 코드 공유의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!