•
트리 : Node 와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
•
실제로 어디에 많이 사용되나?
◦
트리 중 이진 트리 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
2.
알아둘 용어
•
Node : 트리에서 데이터를 저장하는 기본요소(데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
•
Root Node : 트리 맨 위에 있는 노드
•
Level : 최상위 노드를 Level 0 으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
•
Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
•
Child Node : 어떤 노드의 상위 레벨에 연결된 노드
•
Leaf Node(Terminal Node) : Child Node 가 하나도 없는 노드
•
Sibling (Brother Node) : 동일한 Parent Node를 가진 노드
•
Depth : 트리에서 Node가 가질 수 있는 최대 Level
3.
이진 트리와 이진 탐색 트리
•
이진 트리 : 노드의 최대 Branch가 2인 트리
•
이진 탐색 트리 : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
◦
왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음
4.
자료 구조 이진 탐색 트리의 장점과 주요 용도
•
주요 용도 : 데이터 검색(탐색)
•
장점 : 탐색 속도를 개선할 수 있음
5.
자바 객체지향 프로그래밍으로 링크드 리스트 구현하기
5.1. 노드 클래스 만들기
public class NodeMgmt {
public class Node {
Node left;
Node right;
int value;
public Node(int data){
this.value = data;
this.left = null;
this.right = null;
}
}
}
Java
복사
5.2. 이진 탐색 트리에 데이터 넣기
•
이진 탐색 트리 조건에 부합하게 데이터를 넣어야 함
public class NodeMgmt{
Node head = null;
public class Node{
Node left;
Node right;
int value;
public Node(int data){
this.value = data;
this.left = null;
this.right = null;
}
}
public boolean insertNode(int data) {
if(this.head == null){
this.head = new Node(data);
} else {
Node findNode = this.head;
while(true){
if(data < findNode.value) {
if(findNode.left !=null){
findNode = findNode.left;
Java
복사