[data-structures] 이진 트리와 이진 검색 트리의 차이점

누구나 이진 트리 와 이진 검색 트리 의 차이점을 예를 들어 설명 할 수 있습니까 ?

답변

이진 트리 : 각 노드에 최대 두 개의 잎이있는 트리

  1
 / \
2   3

이진 검색 트리 :에 사용 검색 . 진 왼쪽의 자녀가 포함 트리 만 덜 부모 노드가 아닌 값으로 노드를 어디에 올바른 아이 만 보다 크거나 부모에게 같은 값으로 노드를 포함한다.

  2
 / \
1   3

답변

이진 트리는 두 명의 자녀 (왼쪽 자녀와 오른쪽 자녀)가있는 특수한 형태의 나무입니다. 그것은 단순히 트리 구조의 데이터 표현입니다

이진 검색 트리 (BST) 는 다음과 같은 조건을 따르는 특수 유형의 이진 트리입니다.

왼쪽 자식 노드가 부모 노드보다 작습니다
오른쪽 자식 노드가 부모 노드보다 큽니다.

답변

이진 트리는 노드로 구성되며 각 노드에는 “왼쪽”포인터, “오른쪽”포인터 및 데이터 요소가 포함됩니다. “루트”포인터는 트리에서 최상위 노드를 가리 킵니다. 왼쪽 및 오른쪽 포인터는 양쪽의 작은 “하위 트리”를 재귀 적으로 가리 킵니다. 널 포인터는 요소가없는 이진 트리 (빈 트리)를 나타냅니다. 공식 재귀 정의는 다음과 같습니다. 이진 트리가 비어 있거나 (널 포인터로 표시됨) 왼쪽 및 오른쪽 포인터 (재귀 정의 앞의)가 각각 이진 트리를 가리키는 단일 노드로 구성됩니다.

이진 검색 트리 (BST) 또는 “순서 이진 트리”는 노드가 순서대로 배열 된 이진 트리 유형입니다. 각 노드에 대해 왼쪽 하위 트리의 모든 요소는 노드 (<)보다 적으며 모든 요소는 오른쪽 하위 트리에서 노드 (>)보다 큽니다.

위에 표시된 트리는 이진 검색 트리입니다. “루트”노드는 5이고 왼쪽 하위 트리 노드 (1, 3, 4)는 <5이고 오른쪽 하위 트리 노드 (6, 9)는> 5입니다. 재귀 적으로 각 하위 트리는 이진 검색 트리 제약 조건을 따라야합니다. (1, 3, 4) 하위 트리에서 3은 루트, 1 <3 및 4> 3입니다.

“이진 검색 트리”는 “이진 트리”와는 다른 문제의 정확한 문구를주의하십시오.

답변

위의 모든 사람들이 이진 트리와 이진 검색 트리의 차이점에 대해 설명했듯이 주어진 이진 트리가 이진 검색 트리인지 테스트하는 방법을 추가하고 있습니다.

boolean b = new Sample().isBinarySearchTree(n1, Integer.MIN_VALUE, Integer.MAX_VALUE);
.......
.......
.......
public boolean isBinarySearchTree(TreeNode node, int min, int max)
{

    if(node == null)
    {
        return true;
    }

    boolean left = isBinarySearchTree(node.getLeft(), min, node.getValue());
    boolean right = isBinarySearchTree(node.getRight(), node.getValue(), max);

    return left && right && (node.getValue()<max) && (node.getValue()>=min);

}

그것이 도움이되기를 바랍니다. 여기서 언급 할 가치가 있다고 생각하여 주제에서 벗어나면 죄송합니다.

답변

이진 트리는 두 개의 자식 참조 만 가질 수 있는 노드 로 구성된 데이터 구조 를 나타냅니다 .

반면, 이진 검색 트리 ( BST )는 각 노드 가 비슷한 값을 가지며 왼쪽에있는 값이 큰 하위 값과 오른쪽에 연결된 값이 큰 하위 값 이있는 특수한 형식의 이진 트리 데이터 구조 입니다.

따라서 모든 BST 는 이진 트리 이지만 일부 이진 트리 만 BST 일 수도 있습니다 . BST 는 이진 트리 의 하위 집합 임을 알립니다. .

따라서 이진 트리는 이진 검색 트리 보다 일반적인 데이터 구조 입니다. 또한 당신이 있음을 통지해야 이진 검색 트리 A는 정렬 된 일반 규칙의 이러한 설정이없는 반면, 트리 이진 트리 .

이진 트리

Binary Tree이다 하지BST ;

         5
       /   \
      /     \
     9       2
    / \     / \
  15   17  19  21

이진 검색 트리 (정렬 트리)

이진 검색 트리 도입니다 이진 트리 ;

         50
       /    \
      /      \
     25      75
    /  \    /  \
  20    30 70   80

이진 검색 트리 노드 속성

또한 BST의 모든 상위 노드 에 대해 통지 하십시오 .

왼쪽의 모든 노드는 상위 노드의 값보다 작은 값을 갖습니다. 위의 예에서, 모든 왼쪽 ( 왼쪽 자손 )에 있는 값이 {20, 25, 30} 인 노드 는 50보다 작습니다.
올바른 모든 노드는 상위 노드의 값보다 큰 값을 갖습니다. 위의 예 에서, 오른쪽 ( 오른쪽 자손 )이 모두 50 인 {70, 75, 80} 값을 가진 노드 는 50보다 큽니다.

이진 트리 노드 에는 이러한 규칙이 없습니다 . 이진 트리 노드에 대한 유일한 규칙 은 두 명의 자녀를 두는 것이므로 이진 이라는 이유를 스스로 설명합니다 .

답변

이진 검색 트리는 다음과 같은 속성을 나타내는 특수 종류의 이진 트리입니다. 모든 노드 n에 대해 n의 왼쪽 하위 트리에있는 모든 하위 노드 값은 n의 값보다 작고 오른쪽 하위 트리에있는 모든 하위 노드 값은 다음과 같습니다. n 값보다 큽니다.

답변

이진 트리

이진 트리는 자식 2 개와 부모 1 개가 있는 모든 것이 될 수 있습니다 . 연결 목록 또는 배열로 또는 사용자 정의 API로 구현할 수 있습니다. 특정 규칙을 더 추가하기 시작하면 더 전문화 된 트리가됩니다. 됩니다. 가장 일반적인 알려진 구현은 왼쪽에 작은 노드를 추가하고 오른쪽에 큰 노드를 추가하는 것입니다.

예를 들어, 값이 루트 노드와 크기 9, 높이 3의 표시 이진 트리, 2. 트리입니다 불균형이 아니라 분류 .
https://en.wikipedia.org/wiki/Binary_tree

예를 들어 왼쪽의 트리에서 A에는 6 명의 자식 {B, C, D, E, F, G}가 있습니다. 오른쪽의 이진 트리로 변환 할 수 있습니다.

이진 검색

이진 검색은 노드 체인에서 특정 항목을 찾는 데 사용되는 기술 / 알고리즘입니다. 이진 검색은 정렬 된 배열에서 작동합니다 .

이진 검색은 대상 값을 배열 의 중간 요소 와 비교합니다 . 동일하지 않으면 대상이 놓을 수없는 절반이 제거되고 성공하거나 나머지 절반이 비어있을 때까지 나머지 절반에서 검색이 계속됩니다. https://ko.wikipedia.org/wiki/Binary_search_algorithm

이진 검색을 나타내는 트리 입니다. 여기서 검색되는 배열은 [20, 30, 40, 50, 90, 100]이고 대상 값은 40입니다.

이진 검색 트리

이것은 이진 트리의 구현 중 하나입니다. 이를 위해 전문 검색 .

이진 검색 트리 및 B- 트리 데이터 구조는 이진 검색을 기반으로 합니다.

정렬 또는 정렬 이진 트리라고도하는 이진 검색 트리 (BST) 는 메모리에 “항목”(예 : 숫자, 이름 등)을 저장하는 데이터 구조 인 특정 유형의 컨테이너 입니다. https://ko.wikipedia.org/wiki/Binary_search_tree

크기가 9이고 깊이가 3 인 이진 검색 트리는 루트에 8입니다. 나뭇잎이 그려지지 않습니다.

마지막으로 잘 알려진 데이터 구조와 알고리즘의 성능 비교를위한 훌륭한 스키마 :

알고리즘 (4 판) 에서 가져온 이미지