IM

작지만 단단하게

본문과 관련하여 실습한 전체코드는 리파지토리에 별도 작성하였습니다.
https://github.com/ejImDev/data_structure_study.git

탐색트리

  • 저장된 데이터에 대해 탐색, 삽입, 삭제, 갱신 등의 연산을 수행할 수 있는 자료구조
  • 배열이나 연결리스트는 각 연산을 수행하는데 O(N) 시간이 소요
  • 스택이나 큐는 특정 작업에 적합한 자료구조
  • 이진탐색트리, AVL트리, 2-3트리, 레드블랙트리, B트리 등

이진탐색트리 (BST)

  • 이진탐색의 개념을 트리 형태의 구조에 접목한 자료구조
  • 이진탐색 : 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 특정 항목을 찾는 탐색 방법 (데이터는 오름차순으로 정렬 되어있어야 함)
  • 이진탐색트리의 특징 중 하나는 트리를 중위순회하면 정렬되어 출력 됨
  • 이진탐색트리는 이진트리로서 각 노드가 다음과 같은 조건을 만족함
    • 각 노드 n의 키값이 n의 왼쪽 서브트리에 있는 노드들의 키값보다 크고, 오른쪽 서브트리에 있는 노드들의 키값보다 작다.

이진탐색트리 구현

  • 노드 클래스는 이진트리의 구현에 사용된 노드와 거의 유사
  • 노드 객체는 id(키), name(키에 관련된 정보), 왼쪽 자식과 오른쪽 자식을 각각 가리키기 위한 left, right

  1. 노드 클래스 
    public class Node <Key extends Comparable<Key>, Value> {
 private Key id;
 private Value name;
 private Node left, right;
 public Node(Key newId, Value newName){
     id = newId;
     name = newName;
     left = right = null;
 }
 public Key getKey() { return id; }
 public Value getValue() { return name; }
 public Node getLeft() { return left; }
 public Node getRight() { return right; }
 public void setKey(Key newId) { id = newId; }
 public void setValue(Value newName) {name = newName; }
 public void setLeft(Node newLeft) {left = newLeft; }
 public void setRight(Node newRight) {right = newRight; }
}
  2. BST 클래스 
    public class BST<Key extends Comparable<Key>, Value>{
 public Node root;
 public Node getRoot() { return root; }
 public BST(Key newId, Value newName){
     root = new Node(newId, newName);
 }
 ...
}

참고 자료 : ‘경기대학교 소프트웨어중심대학사업단 - JAVA 자료구조’ https://youtu.be/G-vfkaLP2vo

Updated: