가장 일반적인 이진 트리 인터뷰 질문 및 답변 [초보자 및 경험자용]

소개

데이터 구조는 객체 지향 프로그래밍에서 가장 기본적인 개념 중 하나입니다. 간단히 설명하면 데이터 구조는 데이터를 효과적으로 처리할 수 있도록 컴퓨터에서 데이터를 구성하는 특정 방식입니다. 고유한 속성을 가진 스택, 큐, 트리와 같은 여러 데이터 구조가 있습니다.

트리를 사용하면 데이터를 계층적 방식으로 구성할 수 있습니다. 이러한 데이터 구조는 연결 목록이나 배열과 같은 선형 데이터 구조와 매우 다릅니다. 트리는 정보를 전달하는 노드로 구성됩니다.

이진 트리는 최대 두 개의 자식만 가질 수 있는 특수한 유형의 트리입니다. 이것은 이진 트리의 특정 노드에 자식이 없거나, 하나 또는 두 개의 자식이 있을 수 있지만 그 이상은 가질 수 없음을 의미합니다. 이진 트리는 어려운 문제를 해결하고 복잡한 코드를 작성할 수 있는 중요한 데이터 구조입니다.

Java 개발자 또는 소프트웨어 엔지니어로 취업을 지원하는 경우 인터뷰에 이 개념과 관련된 몇 가지 질문이 포함될 수 있습니다. 종종 후보자는 이진 트리, 이진 검색 트리 및 관련 프로그램을 기반으로 한 질문에 답하기가 어렵습니다. 이 기사에서는 이진 트리와 관련하여 가장 자주 묻는 인터뷰 질문을 살펴보겠습니다. 이 기사는 개념을 더 잘 이해하고 꿈의 직업을 가질 수 있도록 준비하는 데 도움이 될 것입니다!

상위 이진 트리 인터뷰 질문 및 답변

다음 섹션에는 이진 트리 개념을 기반으로 한 질문 목록과 예상 답변이 포함되어 있습니다.

1) 리프 노드란 무엇입니까?

자식이 없는 이진 트리 또는 트리의 모든 노드를 리프 노드라고 합니다.

2) 루트 노드란 무엇입니까?

트리의 첫 번째 노드 또는 최상위 노드를 루트 노드라고 합니다.

3) Java에서 바이너리 트리의 최하위 공통 조상(LCA)을 어떻게 찾습니까?

이진 트리의 일부인 두 개의 노드 n1과 n2를 고려해 보겠습니다.

n1과 n2의 최하위 공통 조상(LCA)은 루트에서 가장 멀리 위치한 n1과 n2의 공유 조상입니다.

다음 방법에 따라 LCA를 찾을 수 있습니다.

1. a) 루트 노드에서 n1까지의 경로를 찾아 배열에 저장합니다.
2. b) 루트 노드에서 n2까지의 경로를 찾아 배열에 저장합니다.
3. c) 값이 두 배열에서 동일할 때까지 두 경로를 모두 탐색합니다.

4) 주어진 이진 트리가 다른 이진 트리의 하위 트리인지 어떻게 확인합니까?

이진 트리 T가 있다고 가정합니다. 이제 이진 트리 S가 T의 하위 트리인지 확인하려고 합니다.

이렇게 하려면 먼저 S에 있는 노드를 T에서 찾는지 확인하십시오.

이 공통 노드를 찾으면 다음 노드도 S의 일부인지 확인하십시오.

그렇다면 S는 T의 하위 트리라고 안전하게 말할 수 있습니다.

반드시 읽어야 할 내용: 데이터 구조 프로젝트 아이디어 및 주제

5) 이진 트리에서 두 노드 사이의 거리를 어떻게 구합니까?

이진 트리의 일부인 두 개의 노드 n1과 n2를 고려하십시오.

n1과 n2 사이의 거리는 한 노드에서 다른 노드로 도달하기 위해 통과해야 하는 최소 모서리 수와 같습니다.

노드 사이의 최단 거리를 횡단한다는 점에 유의하는 것이 중요합니다.

6) 이진 검색 트리란 무엇입니까?

BST(이진 검색 트리)는 각 내부 노드에 키가 포함된 특수한 유형의 이진 트리입니다. 이진 검색 트리의 경우 규칙은 다음과 같습니다.

1. a) 노드는 노드의 왼쪽 하위 트리에 있는 모든 키보다 큰 키를 가질 수 있습니다.
2. b) 노드는 노드의 오른쪽 하위 트리에 있는 모든 키보다 작은 키를 가질 수 있습니다.

따라서 n1이 키 8을 가진 노드이면 n1의 왼쪽 하위 트리에 있는 모든 노드에는 8보다 작은 키가 포함되고 n1의 오른쪽 하위 트리에 있는 모든 노드에는 8보다 큰 키가 포함됩니다.

7) 자기균형나무란?

자체 균형 이진 검색 트리는 삽입 및 삭제와 같은 작업이 수행될 때 자동으로 높이를 가능한 한 작게 유지합니다.

BST가 자체 균형을 유지하려면 왼쪽 하위 트리에는 낮은 값의 키가 있고 오른쪽 하위 트리에는 높은 값의 키가 있도록 BST의 규칙을 일관되게 따르는 것이 중요합니다.

이것은 두 가지 작업을 사용하여 수행됩니다.

– 왼쪽 회전

– 오른쪽 회전

8) AVL 트리란 무엇입니까?

AVL 트리는 Adelson, Velski 및 Landis의 발명가의 이름을 따서 명명되었습니다. AVL 트리는 왼쪽 하위 트리와 오른쪽 하위 트리의 높이를 확인하고 차이가 1 이하인지 확인하는 자체 균형 이진 트리입니다. 이 차이를 균형 요소라고 합니다.

따라서 BalanceFactor = 높이(왼쪽 하위 트리) – 높이(오른쪽 하위 트리)

균형 요소가 1보다 크면 트리는 다음 기술 중 일부를 사용하여 균형을 이룹니다.

– 왼쪽 회전

– 오른쪽 회전

– 좌우 회전

– 오른쪽-오른쪽 회전

더 읽어보기: 데이터 구조의 정렬

9) Java에서 이진 트리를 이진 검색 트리로 어떻게 변환합니까?

이진 트리와 이진 검색 트리의 주요 차이점은 BST 다음에 오는 왼쪽 하위 트리는 더 낮은 키 값을 가져야 하고 오른쪽 하위 트리는 더 높은 키 값 규칙을 가져야 한다는 것입니다. 이것은 다음과 같은 일련의 순회 기술을 사용하여 수행할 수 있습니다.

1. 트리의 중위 순회를 저장하는 임시 배열을 만듭니다.
2. 임시 배열을 정렬합니다. 여기에서 모든 정렬 알고리즘을 사용할 수 있습니다.
3. 다시 트리에 대해 중위 순회를 수행합니다.
4. 배열 요소를 각 트리 노드에 하나씩 복사합니다.

10) Java의 이진 검색 트리에서 노드를 어떻게 삭제합니까?

BST의 삭제 작업은 작업 후에 속성을 보존해야 하기 때문에 까다로울 수 있습니다. 가능한 세 가지 경우를 모두 살펴보겠습니다.

1. 삭제할 노드는 리프 노드입니다.
   노드를 제거하기만 하면 됩니다.
2. 제거할 노드에는 자식이 하나 있습니다.

이 경우 자식을 노드에 복사하고 자식을 삭제합니다.

1. 제거할 노드에는 두 개의 자식이 있습니다.

이 경우 노드의 inorder 후임자를 찾습니다. 그런 다음 해당 콘텐츠를 노드에 복사하고 inorder 후속 작업을 삭제할 수 있습니다.

11) Red-Black 트리 데이터 구조는 무엇입니까?

Red-Black 트리는 다음과 같은 속성을 가진 특별한 유형의 자체 균형 트리입니다.

1. 각 노드에는 빨간색 또는 검은색의 색상이 있습니다.
2. 루트는 항상 검은색입니다.
3. 레드 노드는 레드 부모나 레드 자식을 가질 수 없습니다.
4. 루트 노드에서 NULL 노드까지의 모든 경로에는 동일한 수의 블랙 노드가 있습니다.

반드시 읽어야 할 내용: 데이터 구조 프로젝트 아이디어 및 주제

12) 두 나무가 동일한지 어떻게 알 수 있습니까?

두 개의 이진 트리는 데이터와 배열이 동일하면 동일합니다. 이것은 두 트리를 탐색하고 데이터와 배열을 비교하여 수행할 수 있습니다.

이를 가능하게 하는 알고리즘은 다음과 같습니다.

1. 루트 노드의 데이터 확인( tree1 데이터 ==tree2 데이터)
2. 왼쪽 하위 트리를 재귀적으로 확인합니다. sameTree(tree1-> 왼쪽 하위 트리, tree2-> 왼쪽 하위 트리) 호출
3. 마찬가지로 오른쪽 하위 트리를 확인하십시오.
4. b,c가 참이면 1을 반환합니다.

확인: 이진 트리의 유형

마지막 생각들

이 기사에서 우리는 가장 일반적으로 묻는 이진 검색 트리 인터뷰 질문 중 일부를 탐색했습니다. 데이터 구조에 대해 더 많이 탐색하면 논리와 프로그래밍을 더 잘 이해하는 데 도움이 될 수 있습니다. 이 기사에 언급된 예를 보고 가치를 변경하여 기초를 구축하는 연습을 시도할 수 있습니다. 약간의 연습을 하면 면접을 깰 수 있는 좋은 위치에 서게 될 것입니다.

데이터 과학에 대해 자세히 알아보려면 작업 전문가를 위해 만들어졌으며 10개 이상의 사례 연구 및 프로젝트, 실용적인 실습 워크샵, 업계 전문가와의 멘토링, 1 - 업계 멘토와 일대일, 400시간 이상의 학습 및 최고의 기업과의 취업 지원.