Java에서 이진 검색 트리의 높이 결정

1. 이진 검색 트리
2. 이진 검색 트리의 적용
3. 이진 검색 트리의 높이 결정

이 심층 문서에서는 Java 프로그램에서 트리의 높이를 결정하기 위해 재귀 검색 프로그램을 구현하기 전에 이진 검색 트리의 기본 사항을 배웁니다. 이 자습서를 이해하려면 트리의 데이터 구조 개념에 대한 기본적인 이해가 있는 것이 좋습니다.

이진 검색 트리

간단하게 합시다. 우리는 긴 이론적 개념으로 당신을 지루하게 만들지 않을 것입니다. 그러나 다음은 숙지해야 하는 핵심 개념입니다.

1. 계층적 데이터 구조의 루트 노드에 대한 단일 참조.
2. 노드당 최대 2개의 자식 노드(왼쪽 및 오른쪽 자식)가 존재합니다.
3. 이진 검색 기능은 노드를 구성합니다.
   • 각 노드는 키 데이터 필드에 따라 정렬됩니다.
   • 트리의 각 노드의 키는 왼쪽 자식의 키보다 크고 오른쪽 자식의 키보다 작아야 합니다.
   • 그림: 이진 검색 트리:

이진 검색 트리의 적용

간단하게 합시다. 우리는 긴 이론적 개념으로 당신을 지루하게 만들지 않을 것입니다.

그러나 다음은 숙지해야 하는 핵심 개념입니다.

1. Java를 포함한 대부분의 프로그래밍 언어에서 map 및 set 메소드와 같이 데이터의 흐름과 구조가 지속적으로 들어오고 나가는 BST를 사용할 수도 있습니다.

2. 객체의 위치와 렌더링 프로세스를 결정하기 위해 3차원 비디오 게임에서도 BST를 사용할 수 있습니다. BST: Binary Space Partition을 사용한 공간 분할에 대해 자세히 읽어보십시오.

3. 주로 네트워킹에 대해 이야기하는 경우 라우터 테이블을 저장하기 위해 거의 모든 고대역폭 라우터에서 이러한 트리를 사용할 수 있습니다. 이진 시도.

4. 토렌트와 고유한 이미지 서명 생성에 관심이 있는 경우. 해시 요구 사항을 확인하려고 하지만 전체 파일을 사용할 수 없다고 가정합니다.

   BST를 사용할 수 있는 곳이기도 합니다. 더 읽어보기: 해시 트리

요컨대, 원하는 데이터를 정렬하는 데 도움이 되는 기능 덕분에 다양한 응용 프로그램에서 이진 검색 트리를 사용할 수 있습니다. 이진 검색 트리를 사용하여 다단계 인덱싱을 수행할 수 있습니다.

또한 다양한 검색 알고리즘을 구현하는 데 사용할 수도 있습니다. BST는 정렬된 데이터 스트림을 유지하는 데 도움이 될 수 있기 때문입니다.

이진 검색 트리의 높이 결정

이진 검색 트리의 높이를 결정하는 것은 다음과 같은 쉬운 단계를 따르면 어려운 작업이 아닙니다.

1. 루트에서 리프 노드까지 가장 긴 경로의 길이가 이진 트리의 높이를 결정합니다. 이진 트리의 깊이라고도 합니다.

   뿌리의 높이는 나무의 높이와 같습니다.

2. 노드의 깊이는 루트까지의 경로 길이입니다.

3. 나무의 높이를 계산하려면 뿌리와 가장 먼 잎사귀 사이의 가장자리 수를 세어야 합니다.

위의 그래프에서 볼 수 있듯이 루트와 가장 먼 리프 사이의 가장자리 수는 3입니다. 따라서 트리의 높이도 3입니다.

이진 검색 트리에서 특정 키 검색

이진 검색 트리에서 재귀적으로 또는 반복적으로 특정 키를 검색할 수 있습니다. 이 두 가지 방법 모두 다양한 데이터 구조 작업에 널리 사용되는 선택입니다.

재귀 검색 방법에 대해 이야기하면 검색 프로세스는 루트 노드 검사로 시작됩니다. 이와 관련하여 트리가 nil이라고 가정하면 찾고자 하는 키가 트리에 존재하지 않습니다.

검색 결과가 성공하면 키가 루트와 일치하면 노드가 반환됩니다. 그러나 키가 루트보다 작고 프로그램 검색이 왼쪽 하위 트리로 이동한다고 가정합니다.

이진 검색 트리의 높이를 찾는 재귀 단계

트리가 비어 있으면 높이는 0입니다. 반대로 맨 위 노드에서 아래로 시작해야 합니다.

재귀적으로 왼쪽 하위 트리의 최대 깊이를 결정한다고 가정합니다. 이 둘의 최대 깊이는 이진 트리(왼쪽 및 오른쪽 하위 트리)의 높이입니다.

다음 의사 코드를 확인하십시오.

BinarySearchTree(a, k)
   if a = NIL or k = a.key then
     return a
   if k < a.key then
     return Tree-Search(a.L, k)
   else
     return Tree-Search(a.R, k)
   end if

BST 내에서 높이를 검색하기 위해 프로그램을 재귀적으로 구현해 보겠습니다.

예:

package heightofbinarysearchBSTree.delftstack;
// Java program to find the height of BSTree
// A binary BSTree BSTreeNode
public class DetHeight {
  int BSTreedata;
  DetHeight BSTreeNodeLeft, BSTreeNoderight;
  DetHeight(int i) {
    BSTreedata = i;
    BSTreeNodeLeft = BSTreeNoderight = null;
  }
}
class BST {
  DetHeight BSTreeroot;
  /* Compute the "MaximumHeight" of a BSTree -- the number of
  BSTreeNodes along the longest path from the BSTreeroot BSTreeNode
  down to the farthest leaf BSTreeNode.*/
  int MaximumHeight(DetHeight BSTreeNode) {
    if (BSTreeNode == null)
      return -1;
    else {
      /* compute the depth of each subBSTree */
      int LeftHeight = MaximumHeight(BSTreeNode.BSTreeNodeLeft);
      int Rightheight = MaximumHeight(BSTreeNode.BSTreeNoderight);

      /* use the larger one */
      if (LeftHeight > Rightheight)
        return (LeftHeight + 1);
      else
        return (Rightheight + 1);
    }
  }
  /* Driver program to test above functions */
  public static void main(String[] args) {
    BST BSTree = new BST();
    BSTree.BSTreeroot = new DetHeight(12);
    BSTree.BSTreeroot.BSTreeNodeLeft = new DetHeight(25);
    BSTree.BSTreeroot.BSTreeNoderight = new DetHeight(35);
    BSTree.BSTreeroot.BSTreeNodeLeft.BSTreeNodeLeft = new DetHeight(47);
    BSTree.BSTreeroot.BSTreeNodeLeft.BSTreeNoderight = new DetHeight(26);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNodeLeft = new DetHeight(29);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNoderight = new DetHeight(53);
    BSTree.BSTreeroot.BSTreeNoderight.BSTreeNodeLeft.BSTreeNoderight = new DetHeight(31);
    System.out.println("Height of BSTree is : " + BSTree.MaximumHeight(BSTree.BSTreeroot));
  }
}

출력:

The height of this tree : 3

검색 프로그램의 복잡성

이 특별한 경우에는 높이를 유지하면서 이진 트리의 모든 노드를 재귀적으로 순회하기 때문에 선형입니다. 따라서 시간 복잡도는 O(N)이며, 여기서 N은 트리의 노드 수입니다.