트리의 표현
* //root
2 3
의 트리가 있을 때
중위식 : 2 * 3
전위식 : * 2 3
후위식 : 2 3 *
트리의 규칙
부모를 기준으로 작은 것이 왼쪽에 와야 한다
연결리스트에서 노드가 next 포인터를 갖고있었던 것처럼
트리에서는 left, right 포인터를 갖는다
트리의 노드 클래스
class Node<E> {
E data;
Node<E> left, right;
public Node(E obj) {
this.data = obj;
left = right = nll;
}
}
트리에 새로운 데이터를 추가하는 과정
- 루트에서부터 시작한다
- 트리의 규칙에 따라 내려간다
- null인 부분을 찾았다면 그 곳에 새로운 노드를 추가한다
트리의 재귀함수
재귀 함수를 이용하여 트리의 규칙에 따라 내려가는 기능을 구현한다
//재귀 메서드의 코드
public void add(E obj, Noce<E> node) {
If(((comparable<E> obj).compareTo(node.data) >0) { //오른쪽으로 탐색
If(node.right == null) {
node.right = new Node<E>(obj);
return;
}
return add(obj, node.right);
}
If(node.left == null) { //왼쪽으로 탐색
node.left = new Node(obj);
return;
}
return add(obj, node.left);
}
트리에 중복된 요소가 있을 경우
-> 등호를 추가한다
If(((Comparable<E> obj).compareTo(node.data) >= 0)
//트리에 접근하는 법 : 루트를 통해 접근한다
public void add(E obj) {If(root == null) //트리가 비었는지 확인
root = new Node<E>(obj); //루트를 생성
else add(obj, root);currentSize++;
}
public boolean contains(E obj) {
return contains(obj, root);
}
private boolean contains(E obj, Node<E> node) {
If(node == null) return false; //노드가 없는 경우
If(((Comparable<E>)obj).compareTo(node.data) == 0)
return true;
If(((Comparable<E>)obj).compareTo(node.data)>0)
return contains(obj, node.right);
return contains(obj, node.left);
}
트리의 contains
1. 루트에서부터 시작한다
2. 트리의 규칙에 따라 내려간다
3. 그 요소를 찾으면 True를 반환하고 null인 노드에 다다르면 False를 반환한다
-> 트리가 비어있으면 false를 반환
트리의 요소 제거
잎 노드를 없앨 때는 부모 노드의 포인터를 null로 설정해준다
- 자식노드가 하나인 노드를 없앨 때는 부모 노드의 포인터를 자식 노드로 향하게 하면 된다
-> 부모 노드에서 같은 포인터를 사용해야 한다 - 두 개의 자식 노드를 가진 노드를 제거하는 경우 중위 후속자나 중위 선임자의 위치를 바꿔야 한다
-> 바꾼 후 제거한다
중위 선임자 : 제거하고자 하는 노드를 기준으로 오른쪽으로 한 번 내려갔다가 계속 왼쪽으로 내려간 곳의 잎 노드이다
-> 제거하고자 하는 노드보다 큰 노드들 중에서 가장 작은 노드이다
중위 후속자 : 제거하고자 하는 노드를 기준으로 왼쪽으로 한 번 내려갔다가
계속 오른쪽으로 내려간 곳의 잎 노드이다
-> 제거하고자 하는 노드보다 작은 노드들 중에서 가장 큰 노드이다
전체를 없애는 것은 좋은 방법이 아니다
풀기 어려운 문제를 직면하였을 때 풀 수 있는 방식으로 접근해야 한다
-> 회전을 이용한다