[자료구조]트리

원문: https://blog.naver.com/qoxmfaktmxj/223757113838

트리(Tree)

부모-자식 관계로 계층형 구조, Node의 모음으로 이루어진 비선형 구조, 비순환 구조

비선형? => 데이터를 순차적으로 저장하지 않음

계층 구조? => 자식노드에게는 오직 하나의 부모 노드만 있음

비순환 구조? => 트리에서 두 개의 노드를 잇는 경로는 오직 하나뿐이며 순환이 존재하지 않음

import java.util.TreeMap; import java.util.Map;

public class test10 { public static void main(String[] args) { // TreeMap 생성 TreeMap<String, String> treeMap = new TreeMap<>();

// 요소 삽입 treeMap.put(“Banana”, “Yellow”); treeMap.put(“Apple”, “Red,Green”); treeMap.put(“Mango”, “Yellow”); treeMap.put(“Grapes”, “Purple”);

// 요소 조회 (반복문 사용) System.out.println(“=== TreeMap 요소 출력 ===”); for (Map.Entry<String, String> entry : treeMap.entrySet()) { System.out.println(entry.getKey() + “ -> “ + entry.getValue()); }

// 특정 키 포함 여부 확인 String keyToCheck = “Apple”; if (treeMap.containsKey(keyToCheck)) { System.out.println(“\nTreeMap에 “ + keyToCheck + “ 키가 포함되어 있습니다.”); }

// 특정 값 포함 여부 확인 String valueToCheck = “Yellow”; if (treeMap.containsValue(valueToCheck)) { System.out.println(“TreeMap에 값 “ + valueToCheck + “ 이(가) 포함되어 있습니다.”); }

// 요소 삭제 treeMap.remove(“Banana”); System.out.println(“\nBanana 삭제 후 TreeMap:”); for (Map.Entry<String, String> entry : treeMap.entrySet()) { System.out.println(entry.getKey() + “ -> “ + entry.getValue()); }

// 첫 번째 및 마지막 키 조회 System.out.println(“\n첫 번째 키: “ + treeMap.firstKey()); System.out.println(“마지막 키: “ + treeMap.lastKey()); } }

❓이진 탐색 트리(Binary Search Tree, BST)

import java.util.Arrays; public class BinarySearchExample { public static void main(String[] args) { // 정렬된 배열 int[] numbers = {1, 3, 5, 7, 9, 11, 13, 15}; int target = 7;

// 이진 탐색 수행 int result = binarySearch(numbers, target);

// 결과 출력 if (result != -1) { System.out.println(“값 “ + target + “은(는) 인덱스 “ + result + “에 있습니다.”); } else { System.out.println(“값 “ + target + “을(를) 찾을 수 없습니다.”); } }

// 이진 탐색 메서드 public static int binarySearch(int[] arr, int target) { int left = 0, right = arr.length - 1;

while (left <= right) { int mid = left + (right - left) / 2; // 중간값 계산

if (arr[mid] == target) { return mid; // 찾았을 경우 인덱스 반환 } else if (arr[mid] < target) { left = mid + 1; // 오른쪽 탐색 } else { right = mid - 1; // 왼쪽 탐색 } } return -1; // 값이 없을 경우 -1 반환 } }

❓TreeMap 사용

TreeMap은 내부적으로 Red-Black Tree(균형 이진 탐색 트리) 를 사용하여 키를 정렬된 상태로 유지하고,

탐색 연산 (get, containsKey, higherKey, lowerKey 등)을 O(log n) 시간 복잡도로 수행합니다.

import java.util.TreeMap;

public class TreeMapBinarySearch { public static void main(String[] args) { // TreeMap 생성 및 값 추가 (자동 정렬됨) TreeMap<Integer, String> treeMap = new TreeMap<>(); treeMap.put(1, “One”); treeMap.put(3, “Three”); treeMap.put(5, “Five”); treeMap.put(7, “Seven”); treeMap.put(9, “Nine”);

int target = 7;

// 특정 값 찾기 (이진 탐색과 유사하게 동작) if (treeMap.containsKey(target)) { System.out.println(“값 “ + target + “이(가) 존재합니다: “ + treeMap.get(target)); } else { System.out.println(“값 “ + target + “이(가) 존재하지 않습니다.”); }

// 특정 키보다 작거나 같은 가장 큰 키 찾기 (floorKey) System.out.println(“target 이하 가장 큰 값: “ + treeMap.floorKey(target));

// 특정 키보다 크거나 같은 가장 작은 키 찾기 (ceilingKey) System.out.println(“target 이상 가장 작은 값: “ + treeMap.ceilingKey(target));

// 특정 키보다 큰 값 찾기 (higherKey) System.out.println(“target보다 큰 가장 가까운 값: “ + treeMap.higherKey(target));

// 특정 키보다 작은 값 찾기 (lowerKey) System.out.println(“target보다 작은 가장 가까운 값: “ + treeMap.lowerKey(target)); } }

---

🔹 설명

• containsKey(target) → 특정 값이 존재하는지 확인 (O(log n))
• floorKey(target) → target보다 작거나 같은 가장 큰 값 찾기 (이진 탐색에서 <= 찾기와 유사)
• ceilingKey(target) → target보다 크거나 같은 가장 작은 값 찾기 (이진 탐색에서 >= 찾기와 유사)
• higherKey(target) → target보다 큰 가장 가까운 값 찾기
• lowerKey(target) → target보다 작은 가장 가까운 값 찾기

이렇게 하면 직접 이진 탐색을 구현하지 않아도, TreeMap이 내부적으로 균형 잡힌 트리 구조를 유지하면서 빠르게 탐색을 수행할 수 있습니다.