데이터 구조의 트리: 모든 데이터 과학자가 알아야 할 8가지 유형의 트리

소개

컴퓨팅 영역에서 데이터 구조는 디스크에 데이터를 배열하는 패턴을 말하며, 이를 통해 저장 및 표시가 편리합니다. 그들은 2021년에 유리한 직업 선택이 될 것으로 예측되는 데이터 과학 분야와 관련이 있습니다. 향후 몇 년 동안의 예측을 바탕으로 대규모 딥 러닝 모델과 차세대 스마트 장치가 이 부문.

따라서 데이터 구조에 대한 지식을 습득하는 것은 기술 발전 속에서 적합한 직업을 찾는 데 필수적일 것입니다. 2021년 데이터 과학 산업의 예측에 따르면 미국과 인도는 2,50,000개 이상의 회사에서 약 50,000명의 데이터 과학자와 300,000명의 데이터 분석가를 고용할 것입니다. [1]

정보의 할당, 관리 및 검색을 위한 경로를 설계하기 위해 데이터 구조가 적용됩니다. 데이터 구조는 특히 전체 처리 데이터의 작성 및 효율성 향상에 필요합니다. 그들은 정보 교환을 효과적으로 촉진하기 위해 데이터를 그룹화하고 구성하여 데이터를 관리합니다.

데이터 구조의 트리

'트리'는 데이터 할당에 대한 계층적 패턴을 따르는 ADT(추상 데이터 유형) 유형입니다. 기본적으로 트리는 가장자리를 통해 연결된 여러 노드의 모음입니다. 이러한 '트리'는 '루트' 노드가 '상위' 노드로 연결되고 결국 '하위' 노드로 이어지는 트리와 유사한 데이터 구조 설계를 형성합니다 . 연결은 '가장자리'로 알려진 선으로 이루어집니다.

'리프' 노드는 더 이상 해당 노드에서 시작되는 자식 노드가 없는 끝점입니다. 데이터 구조 의 트리는 배열의 비선형 특성으로 인해 중요한 역할을 합니다. 이를 통해 설계 단계 전반에 걸쳐 편의성과 함께 검색 중 더 빠른 응답 시간이 가능합니다.

데이터 구조의 트리 유형

데이터 구조에서 다양한 유형의 트리가 아래에 자세히 설명되어 있습니다.

1. 일반 트리

일반 트리는 노드가 가질 수 있는 자식 수에 대한 사양이나 제약이 없다는 특징이 있습니다. 계층 구조를 가진 모든 트리는 일반 트리로 분류할 수 있습니다. 노드는 여러 자식을 가질 수 있으며 트리 방향에 대한 모든 종류의 조합이 있을 수 있습니다. 노드는 0에서 n까지의 임의의 정도일 수 있습니다.

다음은 데이터 구조에 있는 일반 트리의 고전적인 예이며 맨 위에 있는 '2'가 루트 노드입니다.

원천

2. 이진 트리

두 개의 숫자를 의미하는 'binary'라는 단어로 정의된 것처럼 이진 트리는 2개의 자식 노드를 가질 수 있는 노드로 구성됩니다. 이진 트리의 모든 노드는 최대 0, 1 또는 2개의 노드를 가질 수 있습니다. 데이터 구조의 이진 트리는 기능이 뛰어난 ADT이며 여러 유형으로 더 세분화될 수 있습니다. 주로 두 가지 목적으로 데이터 구조에서 사용됩니다.

1. 이진 검색 트리에서 관찰된 것처럼 노드에 액세스하고 레이블을 지정합니다.
2. 분기 구조를 통한 데이터 표현용.

다음은 데이터 구조에서 이진 트리의 기본 다이어그램입니다.

원천

3. 이진 검색 트리

이진 검색 트리(BST)는 데이터의 더 빠른 검색/조회 또는 추가/제거를 용이하게 하는 방식으로 배열된 이진 트리의 고유한 하위 유형입니다. BST는 데이터, 왼쪽 자식 및 오른쪽 자식의 세 가지 필드를 기반으로 하는 노드 표현으로 정의됩니다. BST의 지배 요소는 다음과 같습니다.

1. 왼쪽에 있는 모든 노드(왼쪽 자식)는 부모 노드보다 작은 값을 보유해야 합니다.
2. 오른쪽(오른쪽 자식)의 모든 노드는 부모 노드보다 높은 값을 보유해야 합니다.

이러한 배열은 배열에서 볼 수 있는 선형 검색의 절반으로 검색 시간을 줄입니다. 따라서 데이터 구조의 이진 검색 트리는 다른 ADT에 비해 검색 및 정렬에 널리 적용할 수 있습니다.

원천

BT와 BST 모두 본질적 으로 데이터 구조 의 트리이지만 이름의 유사성으로 인해 혼동하지 마십시오. upGrad에서 바이너리 트리와 바이너리 검색 트리 의 차이점을 자세히 알아 보세요.

4. AVL 트리

AVL 트리는 발명가인 Adelson-Velsky와 Landis에서 이름을 따왔습니다. AVL 트리는 자체 균형 특성이 특징입니다. 루트 노드의 두 하위 트리 높이는 2 미만으로 제한됩니다. 높이 차이가 1 이상으로 증가하면 자식 노드가 재조정됩니다.

AVL 트리는 높이 균형을 이루고 이 재조정은 단일 또는 이중 회전을 통해 발생합니다. 밸런싱 팩터는 왼쪽 서브트리와 오른쪽 서브트리 높이의 차이며 값은 -1, 0, 1이다.

5. 레드 블랙 트리

이 유형은 레드 블랙 트리도 높이 균형을 맞추기 때문에 AVL 트리와 유사합니다. 그것들을 구분하는 것은 균형을 잡기 위해 두 번 이상 회전할 필요가 없다는 것입니다. 여기에는 노드의 빨간색 또는 검은색을 정의하는 추가 비트가 포함되어 있어 트리가 삭제 및 삽입되는 동안 균형이 유지됩니다. 빨강 검정 색상 코딩도 변경하는 동안 다시 칠해 지지만 추가 메모리 비용은 거의 없습니다.

6. 스플레이 트리

이진 탐색 트리의 또 다른 하위 유형인 스플레이 트리는 최근 노드를 조정하기 위해 회전 연산을 수행하는 고유한 속성을 가지고 있습니다. 최근에 접속한 노드를 회전시켜 루트 노드로 정렬한다. 균형 잡힌 나무이지만 높이 균형이 잡힌 나무는 아닙니다.

트리 회전이 특정 방식으로 수행되기 때문에 '재생' 동작은 초기 이진 트리 검색 후에 수행됩니다. 모든 연산 후에 트리는 스스로 균형을 잡기 위해 회전하고, 검색된 요소는 루트 노드로 맨 위에 배열됩니다.

7. 함정

데이터 구조의 '트립'은 트리와 힙의 조합입니다. BST에서 왼쪽 자식의 값은 루트 노드보다 작아야 하고 오른쪽 자식의 값은 높아야 합니다. 힙 데이터 구조에서 루트 노드는 가장 낮은 값을 갖고, 그 자식 노드(왼쪽과 오른쪽 모두)는 큰 값을 가집니다.

따라서 treap은 키(BST와 유사) 및 우선순위(힙과 같은) 형태의 값을 보유합니다. 우선 순위 번호가 독립적인 난수인 방식으로 가장 높은 우선 순위 노드가 이진 검색 트리에 먼저 삽입됩니다. 그들은 순서가 지정된 키의 동적 세트를 유지 관리하고 키 내에서 이진 검색을 허용합니다.

8. B-트리

B-Tree는 데이터 구조에서 자체 균형을 유지하는 종류의 트리로서 데이터를 정렬하여 대수 시간에 검색, 순차 액세스, 삭제 및 삽입이 가능하도록 합니다. 이진 트리와 달리 B-트리는 노드가 두 개 이상의 자식을 가질 수 있도록 합니다. 더 큰 데이터 블록을 읽고 쓰는 데이터베이스 및 파일 시스템과 호환됩니다.

데이터 구조의 B-트리는 디스크와 같은 더 큰 스토리지 시스템에 사용됩니다. 모든 잎은 정보를 전달하지 않으며 동일한 수준 내에 나타납니다. B-트리의 내부 노드는 범위에 의해 묶인 가변 크기의 자식 노드를 가질 수 있습니다.

이들은 데이터 구조의 트리로, 데이터 흐름을 설계하는 프로그래머가 구현합니다. 고유한 특성과 응용 프로그램을 배우는 것은 데이터 과학자가 되기 위한 여정에 필수적입니다. 자신을 향상시키는 또 다른 방법 은 데이터 구조의 트리 및 기타 형태의 ADT 에 대한 지식이 필요한 다양한 프로젝트를 통해 연습하는 것입니다 .

DS 프로젝트에 대한 지식을 적용하기 위해 다음 블로그 링크에는 초보자를 위한 13가지 흥미로운 데이터 구조 프로젝트 아이디어와 주제가 있습니다[2021] .

결론

데이터 구조의 나무와 같은 개념에 대해 배우는 것은 까다로울 수 있으며 프로그래밍 지망생은 스스로 교육하기 위해 전문가의 지도가 필요합니다. 데이터 구조의 트리에 대해 자세히 알아보려면 upGrad 의 온라인 과정을 확인하십시오 . 소프트웨어 개발의 이그 제 큐 티브 PG 프로그램 – IIIT-B 및 upGrad의 DevOps를 통한 DevOps 전문화는 프로그래머로서의 경력을 쌓는 데 도움이 될 수 있습니다.

데이터 구조의 능숙도는 코딩 과정에 필수적이므로 학생이 전문 프로그래머 및 소프트웨어 개발자가 되는 데 도움이 될 수 있습니다. 프로그래머와 데이터 과학자는 앞으로 수십 년 동안 수요가 많을 수밖에 없습니다.

우리는 인도에 5억 명의 인터넷 사용자를 보유하고 있으며 많은 양의 데이터를 생성하고 소비하며 수요를 충족하려면 수천 명의 데이터 과학자를 고용해야 합니다. [2] 이러한 데이터 과학자는 이 분야에서 취업하려면 관련 기술 전문성을 갖춘 올바른 교육이 필요합니다.

upGrad & IIIT-Bangalore에서 선별한 소프트웨어 개발의 이그 제 큐 티브 PG 프로그램 – 풀 스택 개발 전문화는 프로필 을 개선하고 프로그래머로서 더 나은 고용 기회를 확보하는 데 도움이 될 수 있습니다.