이진 검색 트리는 연결 목록 삽입의 유연성과 순서 있는 배열 검색의 효율성을 결합한 알고리즘입니다. 다음은 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!