이진 트리 유형

난이도 쉽게
자주 묻는 질문 배달 인포시스 MAQ
이론 나무조회수 72

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

진행하기 전에 먼저 BT가 실제로 무엇인지 알고 있습니까? 바이너리 트리는 데이터 구조 그것은 본질적으로 계층 적입니다. BT는 모든 노드가 왼쪽에있는 노드, 오른쪽 포인터 및 노드의 가중치로 데이터로 표시됩니다. 각 노드는 상위 노드의 왼쪽 및 오른쪽 하위를 참조하는 최대 2 개의 하위를 포함 할 수 있습니다.

이진 트리 유형

바이너리 트리가 필요한 이유는 무엇입니까? | 바이너리 트리를 사용하는 이유는 무엇입니까?

  • BT를 사용하면 데이터에 대한 빠른 검색, 삽입 및 삭제를 수행 할 수 있습니다 (BST와 같이 우선 순위가 부여됨).
  • BT를 사용하여 가장 가까운 항목을 찾을 수도 있습니다.
  • 데이터를 계층 적으로 저장합니다 (예 : 컴퓨터의 파일 시스템).
  • 작업을 수행하는 데 시간이 덜 걸리는 포인터를 사용하여 BT를 구현하십시오.
  • 접두사 조회를 사용하여 사전을 구현합니다.
  • 주어진 데이터 세트의 고정 텍스트에서 빠른 검색.

이진 트리의 속성

  1. 모든 수준의 최대 노드 수 : 2 ^ L 여기서 L은 여러 수준 (0 <= L <= H)입니다.
  2. 높이 H의 BT에서 최소 및 최대 노드 수 : 최소- H + 1 및 최대 2 ^ (H + 1) – 1 여기서 레벨 0은 높이 0입니다.
  3. N 노드가있는 주어진 BT의 가능한 최소 높이 : log2 (N + 1) -1 여기서 레벨 0은 높이 0입니다.
  4. 총 리프 노드 수 : 2 개의 하위 + 1이있는 총 노드 수
  5. L 리프 노드가있는 BT의 최소 수준 수 : (log2 L) +1.

이진 트리 유형

전체 이진 트리

루트 및 중간 노드에 2 개의 자식 노드가있는 이진 트리입니다. 즉, 리프 노드를 제외하고 모든 노드에는 2 개의 자식 노드가 있다고 말할 수도 있습니다.

참고 : 전체 이진 트리의 리프 노드 수 : 내부 노드 수 +1.

전체 이진 트리

완전한 이진 트리

마지막 레벨을 제외한 모든 레벨이 완전히 채워지고 모든 노드가 왼쪽에서 오른쪽으로 채워지는 이진 트리

참고 : 이진 힙은 완전한 이진 트리의 예입니다.

완전한 이진 트리

완벽한 이진 트리

내부 노드와 루트 노드에 2 개의 자식이 있고 모든 리프가 동일한 수준에있는 이진 트리입니다.

참고 : Perfect Binary Tree의 총 노드 수 : 2 ^ H -1 여기서 H는 BT의 높이입니다.

완벽한 이진 트리

균형 이진 트리

왼쪽 하위 트리 높이가 h1이고 오른쪽 하위 트리 높이가 h2 인 이진 트리 | h1-h2 | <= 1.

참고 : AVL 및 RB 트리는 균형 잡힌 이진 트리를 유지합니다.

균형 이진 트리

병리 적 이진 트리 (비뚤어진 BT / BT 퇴화)

모든 내부 노드에 자식이 하나만있는 이진 트리는 왼쪽 자식이거나 오른쪽 자식 일 수 있습니다.

참고 : 병리학 적 BT 높이 : 노드 수 -1.

병리학 적 이진 트리

 

참고 면접 질문

균열 시스템 설계 인터뷰
Translate »