이진 트리 대 이진 검색 트리: 이진 트리와 이진 검색 트리의 차이점

소개

정렬은 데이터를 보다 효과적으로 분석할 수 있도록 체계적인 순서로 데이터를 정렬하는 프로세스입니다. 특정 레코드를 식별하는 프로세스를 검색이라고 합니다. 데이터가 특정 순서로 적절하게 정렬되면 검색이 쉽고 효율적인 작업이 됩니다. 이 기사에서는 가장 중요한 비선형 데이터 구조 중 하나인 트리를 다룹니다.

트리는 주로 요소 간의 계층적 관계를 보여줌으로써 데이터를 나타내는 데 사용됩니다. 예를 들어, 목차, 가계도. 기술적으로, 트리는 하나의 노드가 트리의 루트로 할당되고 다른 노드가 n>=0개의 disjoint 집합 T1, T2, T3, T4 .... Tn 및 해당 루트 노드의 하위 트리 또는 자식으로 호출됩니다.

이진 트리 란 무엇입니까?

이진 트리는 노드가 0, 1 또는 2개의 노드를 가질 수 있는 비선형 데이터 구조입니다. 이진 트리의 각 노드는 부모 노드 또는 자식 노드로 불립니다. Binary Tree의 최상위 노드를 루트 노드라고 합니다. 각 부모 노드는 왼쪽 자식 노드와 오른쪽 자식 노드인 최대 2개의 자식 노드를 가질 수 있습니다.

이진 트리의 노드에는 세 개의 필드가 있습니다.

1. 데이터 요소 – 노드가 저장할 데이터 값을 저장합니다.
2. 왼쪽 자식에 대한 포인터 – 왼쪽 자식 노드에 대한 참조(또는 주소)를 저장합니다.
3. 오른쪽 자식에 대한 포인터 – 오른쪽 자식 노드에 대한 참조를 저장합니다.

이러한 방식으로 여러 노드를 결합하여 이진 트리를 만듭니다.

이진 트리는 다음과 같이 나타낼 수 있습니다.

원천

위 그림에서 루트 노드 2는 두 개의 자식(또는 자식 노드)인 7과 5를 갖습니다. 7은 왼쪽 자식 노드, 5는 오른쪽 자식 노드라고 합니다. 이러한 방식으로 각 자식 노드는 여러 다른 노드의 부모 노드 역할을 하며 함께 이진 트리를 나타냅니다.

확인: 이진 트리의 유형

이진 트리에서 사용되는 용어

노드 : 트리에서 종료 지점의 기본 표현입니다.

루트 노드 : 바이너리 트리의 최상위 노드.

부모 노드 : 노드가 가장자리를 통해 다른 노드와 연결되어 있는 경우 이를 부모 노드라고 합니다. 이진 트리에서 부모 노드는 최대 2개의 자식 노드를 가질 수 있습니다.

자식 노드 : 노드에 선행 노드가 있는 경우 이를 자식 노드라고 합니다.

리프 노드 : 자식 노드가 없는 노드를 리프 노드라고 합니다.

노드의 깊이 : 루트 노드에서 깊이를 측정할 특정 노드까지의 거리입니다.

트리 높이 : 루트 노드에서 리프 노드까지의 가장 긴 거리입니다.

이것은 이진 트리의 몇 가지 기본 용어입니다. 이진 트리에 대한 기본적인 이해를 바탕으로 이진 탐색 트리로 알려진 이진 트리의 발전으로 넘어가 보겠습니다.

더 읽어보기: 이진 검색 알고리즘: 기능, 이점, 시간 및 공간 복잡성

이진 검색 트리란?

이름에서 알 수 있듯이 이진 검색 트리 또는 BST는 데이터를 정렬, 검색 및 검색하는 데 사용되는 트리입니다. 또한 노드가 특정 순서로 배열된 비선형 데이터 구조의 한 유형입니다. 따라서 " Ordered Binary Tree " 라고도 합니다. 다음과 같은 속성이 있습니다.

• 노드의 왼쪽 하위 트리에는 해당 노드의 키보다 작은 노드만 있습니다.
• 노드의 오른쪽 하위 트리에는 해당 노드의 키보다 큰 노드만 있습니다.
• 각 노드에는 고유한 키가 있으며 이진 검색 트리에서는 중복이 허용되지 않습니다.
• 왼쪽 및 오른쪽 하위 트리도 이진 검색 트리여야 합니다.

이진 검색 트리를 명확하게 이해하기 위해 이 개념을 시각화해 보겠습니다.

원천

위의 그림에서 루트 노드의 값이 8임을 알 수 있습니다. 추가 조사를 통해 왼쪽 하위 트리의 모든 값이 루트 노드의 값보다 작고 오른쪽 하위 트리의 모든 값이 루트 노드보다 큰 값 또한 이진 검색 트리의 각 값은 고유하며 중복이 없습니다. 따라서 위에서 설명한 Binary Search Tree의 속성이 검증됩니다.

또 다른 예에서 왼쪽 및 오른쪽 하위 트리가 트리 전체에서 고유한 값을 갖는 이진 탐색 트리임을 알 수 있습니다. 왼쪽 서브트리의 리프 노드 값은 루트 노드 값인 12보다 큰 12입니다. 따라서 이것은 BST의 속성을 만족하지 않으므로 이진 탐색 트리가 아닙니다.

BST에서 검색 작업 –

아래 주어진 값을 가진 이진 검색 트리를 고려하십시오. 이진 검색 트리에서 9를 얻기 위해 검색 작업이 수행되는 방법을 이해합시다.

원천

이진 검색을 수행하기 위해 먼저 모든 정수를 정렬된 배열로 정렬합니다. 이것을 검색 공간이라고 합니다. 이 검색 공간은 시작 및 끝 포인터라고 하는 두 개의 포인터로 구성됩니다. 위에 주어진 이진 탐색 트리의 배열은 다음과 같이 표현됩니다.

첫 번째 단계는 배열의 중간 값을 계산하고 검색할 값(우리의 경우 9)과 비교하는 것입니다. 이것은 n/2를 계산하여 수행됩니다. 여기서 n은 배열(BST)의 총 요소 수이고 6입니다. 따라서 세 번째 요소는 중간 요소인 5입니다.

이제 중간 요소가 9와 비교되고 동일하지 않으므로(크게) 오른쪽 배열에서 검색 작업이 수행됩니다. 이런 식으로 검색 작업이 아래와 같이 절반으로 줄어듭니다.

다음 단계에서 중간 요소가 계산되고 검색할 요소와 일치하는 9가 발견됩니다.

이진 트리 대 이진 검색 트리 –

이제 우리는 이진 트리와 이진 탐색 트리에 대한 기본적인 이해를 얻었으므로 두 트리의 차이점을 빠르게 요약해 보겠습니다.

결론

따라서 우리는 이진 트리와 이진 탐색 트리 모두 노드 모음과 함께 공통 계층 구조를 가지고 있지만 응용 프로그램에서 몇 가지 차이점이 있다고 추론합니다. 이진 트리는 부모가 2개 이상의 자식을 가질 수 없다는 간단한 규칙을 가진 기본 구조인 반면, 이진 검색 트리는 노드가 구성되어야 하는 특정 순서를 따르는 이진 트리의 변형입니다.

이진 트리 대 이진 검색 트리에 대해 자세히 알아보려면 작업 전문가를 위해 만들어졌으며 10개 이상의 사례 연구 및 프로젝트, 실용적인 실습 워크샵, 업계 멘토링을 제공하는 IIIT-B & upGrad의 데이터 과학 PG 디플로마를 확인하십시오. 전문가, 업계 멘토와의 1:1 학습, 최고의 기업과의 400시간 이상의 학습 및 직업 지원.

세계 최고의 대학에서 온라인으로 데이터 과학 과정 을 배우십시오 . 이그 제 큐 티브 PG 프로그램, 고급 인증 프로그램 또는 석사 프로그램을 획득하여 경력을 빠르게 추적하십시오.