[자료구조] 탐색트리 -2

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

탐색트리 연산 메소드

get 메소드
탐색하고자 하는 Key가 k라면, 루트노드의 id와 k를 비교하는것으로 탐색을 시작

public Value get(Key k) { return get(root, k); }
public Value get(Node n, Key k) {
 if(n==null) { return null; }
 int t = n.getKey().compareTo(k);
 if(t>0){
     return get(n.getLeft(), k);
 } else if (t<0) {
     return get(n.getRight(), k);
 } else {
     return (Value)n.getValue();
 }
}

삽입 연산 (이파리 노드에 삽입)

삽입은 탐색 연산과 거의 동일
탐색 연산의 마지막에서 null이 반환되어야 할 상황에서 null 대신 삽입하고자 하는 값을 갖는 새 노드를 생성하고, 부모노드와 연결하면 삽입 연산이 완료

단, 이미 트리에 존재하는 id를 삽입할 경우 name을 갱신

public Value put(Key k, Value v) { root =  put(root, k, v); }
public Node put(Node n, Key k, Value v) {
 if(n==null) { return new Node(k, v); }
 int t = n.getKey().compareTo(k);
 if(t>0){
  n.setLeft(put(n.getLeft(), k, v));
 } else if (t<0) {
  n.setRight(put(n.getRight(), k, v));
 } else {
  n.setValue(v);
 }
 return n;
}

최솟값 찾기

루트 노드로부터 왼쪽 자식노드를 따라 내려가며, null을 만났을 때 null의 부모노드가 가진 id

public Key min() {
 if(root==null) {
  return null;
 }
 return (Key) min(root).getKey();
}
private Node min(Node n) {
 if(n.getLeft()==null) {
  return n;
 }
 return min(n.getLeft());
}

최솟값 삭제연산
- 최솟값을 가진 노드를 찾아낸 뒤, x의 부모노드 p와 x의 오른쪽 자식노드 c를 연결
- 이 때 c가 null이더라도 자식으로 연결
- deleteMin() 메소드는 임의의 id를 가진 노드를 삭제하는 delete() 메소드에서 사용
```
public deleteMin() {
 if(root==null) {
  System.out.print("empty 트리");
  root = deleteMin(root);
 }
}
public Node deleteMin(Node n) {
 if(n.getLeft()==null){
  return n.getRight();
 }
 n.setLeft(deleteMin(n.getLeft()));
 return n;	
}
```

삭제 연산

먼저 삭제하고자 하는 노드를 찾은 후, 이진탐색트리 조건을 만족하도록 삭제된 노드의 부모노드와 자식노드들을 연결해 주어야 한다

‘자식노드가 없는 경우 / 자식이 하나인 경우 / 자식이 둘인 경우’ 를 각각 나누어 연산을 수행해야 함

 public void delete(Key k) { root = delete(root, k); }
 public Node delete(Node nm Key k) {
  if(n==null) {
  return null;
  }
  int t = n.getKey().compareTo(k);
  if(t>0) {
  n.setLeft(delete(m.getLeft(),k));
  } else if (t<0) {
  n.setRight(delete(n.getRight(),k));
  } else {
  if(n.getRight()==null) {
      return n.getLeft();
  }
  if(n.getLeft()==null) {
      return n.getRight();
  }
  Node target = n;
  n = min(target.getRight());
  n.setRight(deleteMin(target.getRight()));
  n.setLeft(target.getLeft());
  }
  return n;
 }

수행시간

이진탐색트리에서 탐색, 삽입, 삭제 연산은 공통적으로 루트노드에서 탐색을 시작하여 최악의 경우 이파리노드까지 내려가고, 삽입과 삭제 연산은 다시 루트 노드로 거슬러 올라가야 함
트리를 1층 내려갈 때는 재귀호출이 발생하고, 1층을 올라갈때는 setLeft() 또는 setRight() 메소드가 수행되는데, 이들 각각은 O(1)시간 소요
연산들의 수행시간은 각각 트리의 높이(h)에 비례 O(h)
N개의 노드가 있는 이진탐색트리의 높이가 가장 낮은 경우는 완전이진트리 형태일 때이고, 가장 높은 경우는 편향 이진 트리
Empty 이진탐색트리에 랜점하게 선택된 N개의 키를 삽입한다고 가정했을때 트리의 높이는 약 1.39logN

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

IM

탐색트리 연산 메소드

수행시간