자바 에서 트 리 의 최대 요소 와 최소 요 소 를 검색 하 는 방법 에 대한 자세 한 설명 을 삭제 합 니 다.

이 글 은 자바 가 이 진 트 리 의 최대 요소 와 최소 요 소 를 삭제 하 는 방법 을 보 여 준다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
앞의'자바 이 진 트 리 옮 겨 다 니 기 동작'에서 트 리 의 옮 겨 다 니 기 를 완 성 했 습 니 다.이 절 은 이 진 트 리 에서 최대 요소 와 최소 요 소 를 삭제 하 는 방법 에 대해 소개 합 니 다.
2 분 검색 트 리 의 최소 값 과 최대 값 을 삭제 하려 면 2 분 검색 트 리 의 최소 값 과 최대 값 을 찾 아야 합 니 다.사실은 쉬 운 것 입 니 다.이 진 검색 트 리 의 특징 에 따라 왼쪽 트 리 는 현재 노드 보다 작 아야 하기 때문에 이 진 검색 트 리 의 최소 값 은 왼쪽 트 리 가 계속 내 려 가 끝까지 가 야 합 니 다.마찬가지 로 이 진 트 리 에서 오른쪽 트 리 노드 값 은 현재 노드 보다 크 기 때문에 오른쪽 트 리 가 계속 내 려 가면 반드시 최대 치 입 니 다.
왼쪽으로 가면 움 직 이지 않 을 때 까지 반드시 잎 노드 에 도달 해 야 하 는 것 이 아니 라 움 직 이지 않 을 때 까지 만 다음 그림 의 예 를 보 세 요.

왼쪽으로 16 까지 가면 움 직 일 수 없 지만 16 아래 에는 원소 가 있다.
조회 조작
1.1 2 분 검색 트 리 의 최소 노드 조회

 //             
  public E minimum() {
    if (size == 0) {
      throw new IllegalArgumentException("BST is empty");
    }

    Node ninNode = minimum(root);
    return ninNode.e;
  }

  //    node                 
  private Node minimum(Node node) {
    if (node.left == null) {
      return node;
    }

    //               
    return minimum(node.left);
  }

1.2 2 분 검색 트 리 의 최대 노드 조회

 //             
  public E maxmum() {
    if (size == 0)
      throw new IllegalArgumentException("BST is empty");
    Node maxNode = maxmum(root);

    return maxNode.e;
  }

  //    node                 
  private Node maxmum(Node node) {
    if (node.right == null) {
      return node;
    }

    return maxmum(node.right);
  }

2.삭제 작업
최소 값 을 삭제 하 는 방법:
1)삭제 할 노드 가 잎 사 귀 노드 라면 바로 삭제
2)삭제 할 노드 아래 에 오른쪽 하위 트 리 가 있다 면 아래 오른쪽 하위 트 리 를 전체적으로 이전 노드 의 왼쪽 하위 트 리 로 옮 기 면 된다.

22 이 노드 를 삭제 한 후에 33 이 노드 와 그 이하 의 서브 트 리 를 41 노드 의 왼쪽 서브 트 리 로 바 꾸 면 됩 니 다.
2.1 최소 값 삭제

 public E removeMin() {
    E ret = minimum();//      
    root = removeMin(root);

    return ret;
  }

  //     node              
  //                 
  private Node removeMin(Node node) {

    //        ，          ，         
    //        ，            ，               
    //                ，            ，            
    if (node.left == null) {
      Node rightNode = node.right;
      node.right = null; //      ，       ，       
      size--;
      return rightNode;//               
    }

    //          ，           ，                   ，
    //                node                  
    node.left = removeMin(node.left);

    return node;//    ，      node，    
  }

2.2 최대 값 삭제

 //                 
  public E removeMax() {
    E ret = maxmum();
    root = removeMax(root);
    return ret;
  }

  //     node              
  //                 
  private Node removeMax(Node node) {
    if (node.right == null) {
      Node leftNode = node.left;
      node.left = null;
      size--;
      return leftNode;
    }

    node.right = removeMax(node.right);//  "="          right,             
    return node;

  }

 원본 주소  https://github.com/FelixBin/dataStructure/blob/master/src/BST/BST.java
자바 알고리즘 과 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.