1. 이진 탐색 트리에서 노드가 삭제되는 3가지 상황 2. 이진 탐색 트리에서 Inorder Successor란 무엇인가? 이진 탐색 트리에서 Inorder Successor은 입력된 키 값보다 큰 값들중 제일 작은 수를 의미한다. Inorder Successor는 중위 순회(Inorder Traversal)에서 특정 노드를 기준으로 다음에 방문할 노드를 의미합니다. 이진 탐색 트리의 삭제(remove)에서 Inorder Successor 노드는 삭제될 노드를 기준으로 오른쪽 서브트리에서 가장 작은 값을 가진 노드에 해당됩니다. (minValue 메서드 참조) 아래 이진 탐색 트리에서 8의 inorder successor는 10이고 10의 경우에는 12, 14의 경우에는 20이 inorder succes..

1. 이진 탐색 트리의 특징 특정 노드를 기준으로 왼쪽 서브트리는 특정 노드의 키값보다 작다 특정 노드를 기준으로 오른쪽 서브트리는 특정 노드의 키값보다 크다 왼쪽, 오른쪽 서브트리들의 노드들은 또다른 자식 서브트리로 구성된다. 위의 이진 탐색 트리의 특징들은 탐색, 최솟값, 최대값과 같은 기능들을 빠르게 할 수 있도록 키 값들간에 순서를 제공합니다. 만약 트리에 순서가 없다면 모든 키값과 주어진 키값을 비교해야 합니다. 2. 이진 탐색 트리의 탐색 수행 과정 시작은 root 노드에서 시작합니다. 현재 노드와 탐색하고자 하는 key값을 비교합니다. key값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동 key값이 현재 노드의 값보다 크면 오른쪽 서브트리로 이동 key값이 현재 노드의 값과 동일하면 해..

1. 개요 이진 트리에서 삭제 기능을 구현합니다. 삭제 기능의 전체적인 과정은 삭제될 노드를 탐색하고 삭제하고 남은 빈 자리를 이진 트리에서 제일 오른쪽에 위치하는 노드로 대체합니다. 그리고 노드가 2개로 중복되었으므로 제일 오른쪽에 존재하는 노드를 삭제하면서 종료합니다. 2. 이진트리 삭제 수행과정 시작은 루트 노드(Root Node)에서 시작합니다. 그리고 가장 깊고 오른쪽에 위치한 노드를 탐색하고 삭제하고자 하는 노드를 탐색합니다. 삭제하고자 하는 노드에 가장 깊고 오른쪽에 위치한 노드의 데이터 값으로 대체합니다. 마지막으로 가장 깊고 오른쪽에 위치한 노드를 삭제합니다. 3. 이진트리 삭제 구현 // 이진 트리 삽입 및 삭제 예제 public class BinaryTree { public stati..

1. 개요 이진 트리의 삽입 기능을 구현합니다. 삽입 시 빈 공간에 삽입을 수행하는데 이 순서는 중위 순회(Inorder Traversal)를 따릅니다. 구현 언어는 자바입니다. 2. 중위 순회(Inorder Traversal)이란 무엇인가? 중위 순회란 왼쪽 서브 트리를 방문 후 루트 노드(Root Node)를 방문하고 마지막으로 오른쪽 서브 트리를 방문하는 순회입니다. 2. 이진 트리 삽입 과정 3. 이진 트리 삽입 구현 import java.util.LinkedList; import java.util.Queue; // 이진 트리 삽입 및 삭제 예제 public class BinaryTree { public static class Node { int key; Node left, right; publi..

1. 이진 트리(Binary Tree)의 종류 정 이진 트리(full binary tree) 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리입니다. 포화 이진 트리(perfect binary tree) 모든 내부 노드가 두 개의 자식 노드를 가지며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖습니다. 완전 이진 트리(complete binary tree) 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있습니다. References source code : https://github.com/yonghwankim-dev/DataStruct https://www.geeksforgeeks.org/binary-tree-set-3-types-of..

이진 트리는 하나의 노드가 최대 2개의 자식 노드를 가질 수 있기 때문에 다음 레벨로 올라갈수록 곱하기 2합니다. References source code : https://github.com/yonghwankim-dev/DataStruct https://www.geeksforgeeks.org/binary-tree-set-2-properties/