[자료구조] 트리 (Tree)
사진의 출처 : 링크트리(Tree)는 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 자료구조이다.서로 다른 두 노드를 연결하는 길이 하나뿐인 그래프를 트리라고 부른
velog.io
*이진 탐색 트리
이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조.
1. 모든 원소는 서로 다른 유일한 키를 갖는다.
2. 왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다.
3. 오른쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 크다.
4. 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리이다.
기본적으로 루트에서 탐색을 시작한다.
탐색할 키 값 x를 루트 노드의 키 값과 비교한다. - 3개의 케이스 존재
if 키 값 = 루트 노드의 키 값 : 원하는 원소 찾았으므로 탐색 연산 성공.
if 키 값 > 루트 노드의 키 값 : 루트 노드의 오른쪽 서브트리에 대해서 탐색 연산 수행
if 키 값 < 루트 노드의 키 값 : 루트 노드의 왼쪽 서브트리에 대해서 탐색 연산 수행
- 탐색 연산 알고리즘
public TreeNode searchBST(char x) {
TreeNode p = root;
while(p != null) {
//System.out.println(p.data);
if(x < p.data)p = p.left;
else if(x > p.data)p = p.right;
else return p;
}
System.out.println();
return p;
}
-삽입 연산
1. 먼저 탐색 연산을 수행해야함. 삽입할 원소와 같은 원소가 트리에 존재하면 삽입 불가능, 따라서 같은 원소가 트리에 있는지 탐색해서 확인한다.
2. 탐색 시 탐색 실패가 결정되는 위치가 삽입 원소의 자리가 됨. 그 위치에 원소 삽입하면 됨.
*pseudo code
insertBST(bsT, x)
p ← bsT;
while (p≠null) do {
if (x = p.key) then return;
q ← p;
if (x < p.key) then p ← p.left;
else p ← p.right;
}
new ← getNode();
new.key ← x;
new.left ← null;
new.right ← null;
if (bsT = null) then bsT←new;
else if (x < q.key) then q.left ← new;
else q.right ← new;
return;
end insertBST()
public TreeNode insertKey(TreeNode root, char x) {
TreeNode p = root;
TreeNode newNode = new TreeNode();
newNode.data = x;
//새로운 키 넣으니까 좌우는 없어야함.
newNode.left = null;
newNode.right= null;
if(p==null) {
return newNode;
}
else if(newNode.data < p.data) {
p.left = insertKey(p.left, x); //
return p;
}
else if(newNode.data > p.data) {
p.right = insertKey(p.right, x);
return p;
}
else return p;
}
자식 노드가 둘인 노드, 즉 차수가 2인 노드의 삭제 연산
*이진 탐색 트리의 재구성인 후속 처리 필수! - 삭제한 노드의 자리를 자손 노드들 중에서 선택한 후계자에게 물려준다.
1) 왼쪽 서브 트리에서 가장 큰 자손 노드를 선택하는 방법.
왼쪽 서브트리의 오른쪽 링크를 따라 계속 이동하여 오른쪽 링크필드가 NULL인 노드. 즉, 가장 오른쪽에 있는 노드가 후계자가 됨.
2) 오른쪽 서브 트리에서 가장 작은 자손 노드를 선택하는 방법.
오른쪽 서브트리에서 왼쪽 링크를 따라 계속 이동하여 왼쪽 링크 필드가 NULL인 노드. 즉, 가장 왼쪽에 있는 노드가 후계자가 됨.
'Major > Data Structure & Algorithm' 카테고리의 다른 글
[Algorithm] DP (0) | 2022.10.30 |
---|---|
DFS(Depth First Search) (0) | 2022.06.01 |
후위식 연산 (0) | 2022.04.22 |
Stack , 괄호검사(Valid Braces), Infix to Postfix algorithm (0) | 2022.04.16 |
review (0) | 2022.04.16 |