728x90
반응형
- 트리(Tree)란?
계층적인 데이터 구조를 표현하고 데이터를 효율적으로 저장하고 검색하는 데 사용된다.
각 요소를 노드(Node)라고 부르며 이들 사이 관계는 가지(branch)로 표현한다.
- Tree의 주요 특징과 용어
- 부모 노드 : 다른 하나 이상의 노드를 자식으로 가지고 있는 노드
- 자식 노드 : 부모 노드로부터 직접 연결된 노드이자 자기 자신과 연결된 노드 중 자신보다 낮은 노드를 의미한다.
- 루트 노드 : 트리의 가장 상위에 있는 노드로 모든 다른 노드들은 이 루트노드에서 시작하는 경로를 통해 접근할 수 있다. 트리에서 근본이 되는 뿌리 노드이기 때문에 하나밖에 존재하지 않으며 부모 노드가 없다.
- 리프 노드 : 자식 노드가 없는 노드로 가장 최하위에 위치한다. 단말 트리(노드)라고도 부른다.
- 서브 노드 : 트리 내에서 특정 노드와 그 자손 노드들로 구성된 작은 트리를 의미한다.
깊이 : 특정 노드에 도달하기 위해 거쳐야 하는 간선의 개수를 의미한다.
레벨 : 특정 깊이에 있는 노드들의 집합으로 구현하는 사람에 따라 0 또는 1부터 시작한다.
치수 : 특정 노드가 하위 노드와 연결된 개수이다.
- 이진 트리(Binary Tree)란?
각 노드가 최대 두 개의 자식 노드를 가지는 트리로 각 자식 노드는 왼쪽 자식과 오른쪽 자식으로 구분이 된다.
!!!노드를 삽입하고 돌아가면서 출력하는 이진 트리의 순회 :Depth-First Search; 깊이 우선 탐색, Breadth-First Search;너비 우선 탐색
- 전위 순회(Pre-order traversal, 깊이 우선 탐색) : root(뿌리)를 가장 먼저 방문
- 중위 순회(In-order traversal, 깊이 우선 탐색) : 왼 쪽 하위 트리를 방문 후 root(뿌리)를 방문
- 후위 순회(Post-order traversal, 깊이 우선 탐색): 하위 트리 모두 방문 후 root(뿌리)로 방문
- 층별 순회(Level-order traversal, 너비 우선 탐색) : 위 쪽 node들 부터 아래 방향으로 차례대로 방문
- 이진 검색 트리(BST, Binary Search Tree)란?
이진 트리 중 중요한 종류로 데이터를 정렬된 순서로 저장하여 검색 및 삽입 연산에 효율적이다.
- 자가 균형 이진 탐색 트리(AVL,Adelson-Velsky and Landis)란?
모든 노드의 서브트리로 높이 차이가 최대 1인 트리로 이렇게 균형을 유지하면 검색, 삽입, 삭제 연산의 평균 시간 복잡도가 0(log n)이 된다.
- 이진 힙(Binary Heap)이란?
최대 힙과 최소 힙 두 가지가 있으며 우선 순위 큐와 같은 데이터 구조를 구현하는 데 사용된다.
최대 힙 : 부모 노드가 항상 자식 노드보다 크거나 같은 값을 가진다.
최소 힙 : 부모 노드가 항상 자식 노드보다 작거나 같은 값을 가진다.
- 이진 트리의 확장
이진 트리를 확장한 구조로는 이진 탐색 트리와 레드-블랙, B-트리, B+트리 등이 있다.
데이터베이스 인덱싱, 파일 시스템, 자료 구조 등에서 활용한다.
public class TreeNode {
int data;
TreeNode left;
TreeNode right;
public TreeNode(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}public class BinaryTree {
TreeNode root;
public BinaryTree() {
this.root = null;
}
// insert 메서드와 insertRec 메서드는 이진 트리에 새로운 노드를 삽입하는 데 사용된다.
public void insert(int data) { // insert 외부에 노출되는 메서드
root = insertRec(root, data);
}
private TreeNode insertRec(TreeNode root, int data) { // insertRec 실제 삽입 작업 메서드로 재귀적으로 노드를 삽입하고 적절한 위치를 찾아 새로운 노드를 생성한다.
// 재귀적 : 자기 자신을 포함하고 다시 자기 자신을 사용해서 정의 내림
if ( root == null ) {
root = new TreeNode(data);
return root;
}
if (data < root.data) {
root.left = insertRec(root.left, data);
} else if (data > root.data) {
root.right = insertRec(root.right, data);
}
return root;
}
public void inOrderT() { // in order traversal : 중위 순회
inOrderTR(root);
}
public void inOrderTR(TreeNode root) { // 중위 순회를 수행하여 트리의 노드를 출력하는 데 사용되고 왼쪽 서브트리, 현재 노드, 오른쪽 서브트리 순서로 노드 출력
if (root != null) {
inOrderTR(root.left);
System.out.println(root.data + " ");
inOrderTR(root.right);
}
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.insert(50);
tree.insert(30);
tree.insert(70);
tree.insert(20);
tree.insert(40);
tree.insert(60);
tree.insert(80);
System.out.println("이진 트리의 중위 순회 결과 : ");
tree.inOrderT();
}
}728x90
반응형