트리란 비선형 자료구조이며, 이름 그대로 나무 형태의 자료 구조이다.
자식과 부모 관계로 이루어져있다
트리의 용어
- 루트(root) : 트리의 최상위 노드
- 노드(node) : 각 노드는 널 값이나 자식을 가리키는 두 개의 포인터와 데이터를 가진다
- 간선(edge) : 두 노드를 연결하는 데 사용한다
- 리프(leaf) : 자식이 없는 노드를 말한다
- 자식 : 한 노드로부터 가지로 연결 된 아래쪽 노드이다
- 부모 : 한 노드에서 가지로 연결 된 위쪽 노드를 말한다
- 형제 : 같은 부모를 가지는 노드를 말한다
- 높이(height / depth) : 루트부터 리프까지 가장 긴 경로의 간선수를 말한다
- 레벨 : 루트에서 노드까지의 경로에 있는 간선 수를 말한다. 루트의 레벨이 0이며, 가지가 하나씩 아래로 뻗어 나갈 때마다 레벨이 1씩 늘어난다.
- 차수(degree) : 노드가 갖는 자식의 수를 말한다
- 서브트리 : 트리 안에서 다시 어떤 노드를 루트로 정하고 그 자손으로 이루어진 트리를 말한다.
트리는 부모를 가지게 되는데 최상위 부모를 루트라고 하며, 루트부터 시작하게 된다.
루트는 왼쪽과 오른쪽에 자식을 가지게 된다. 부모 자식 관계를 트리라고 하며, 자식을 두명씩 가지고 있으면 이진트리, 세명 가지고 있으면 삼진트리라고 한다.
프로그래밍에서 가장 관심을 가지는 것은 이진트리이다 (이진트리 = 부모가 최대 2명의 자식을 가지는 구조)
루트가 왼쪽과 오른쪽에 자식을 가지고 있게 되는데, 왼쪽 자식은 부모 B를 중심으로 다시 왼쪽 자식과 오른쪽 자식으로 나누어지게 된다. 이것을 서브 트리가 형성이 되었다고 한다(서브트리 : 자식에서 또 다른 트리의 구조가 만들어지는 것)
서브노드 B의 오른쪽 자식 E도 또 다른 왼쪽과 오른쪽 자식을 가지게 된다. 이렇게 트리 안에서 또 다른 트리를 가지는 것이 서브 트리이다.
더 이상 자식이 없는 노드를 리프라고 부르게 된다. 이름 그대로 잎이라는 뜻인데,
트리는 나무가 거꾸로 들어진 상태라고 보면 된다. 뿌리를 중심으로 나무가 있는 상태로 나무 끝에는 나뭇잎이 있다.
리프 노드는 더 이상 자식이 없기 때문에 단말 노드라고 한다.
루트를 중심으로, 루트가 트리의 시작을 말하게 되는데
루트에서 c로 갈 때 한 단계를 거치는 데 갈 수 있는 길을 간선(edge)라고 부르게 된다.
루트에서 c를 가면서 하나의 간선을 거치는 것이 레벨1이고 몇 단계를 거쳤냐에 따라 레벨을 판단한다.
루트에서 리프를 가려면 3단계를 거쳐야 한다.
트리의 높이는 최대 레벨의 차수이며, 이 트리의 높이는 3이 된다.
이진 트리(binary tree)
최대 자식을 두명까지 가질 수 있는 트리가 이진트리이며, 종류에는 완전 이진 트리, 정 이진 트리, 포화 이진 트리가 있다
- 완전 이진 트리
- 완전 이진트리는 마지막 노드인 리프를 제외하고는 모든 노드가 채워져 있는 상태가 되어야 한다.
- 마지막 레벨은 왼쪽부터 차례대로 채워져야 한다, 중간에 하나가 비면 완전 이진 트리가 아니다.
- 정 이진 트리
- 자식이 없거나 최대 2개의 자식이 있는 트리이다
- 포화 이진 트리
- 모든 leaf 레벨이 같다. 모든 노드가 채워져야 한다. 완벽한 피라미드의 형태를 갖는다
- 완전 이진트리도 된다
이진 트리 순회 방법
순회란 모든 노드를 빠짐 없이 방문하는 것이다.
순회하는 방식에는 부모를 언제 들리는지에 따라서 세 가지로 나뉜다
- 중위 순회 : 가운데에 들린다
- 후위 순회 : 나중에 들린다
- 전위 순회 : 먼저 들린다
중위 순회는 부모를 가운데에 두고 순회하는 방식이다.
왼쪽 자식을 먼저 순회하고, 부모를 들리고, 마지막에 오른쪽 자식을 순회한다
- 부모 루트의 왼쪽 자식 4는 서브 트리가 형성되어있다.
- 4를 부모로 해서 왼쪽 자식부터 해결을 한 다음에 부모를 방문하고 오른쪽 자식을 방문한다
- 1 5 3 4 2 → 루트 노드 11의 왼쪽 자식이 해결됨
- 오른쪽 자식을 보면 9를 부모로 해서 왼쪽과 오른쪽 자식으로 나뉜다. 왼쪽 자식부터 해결을 한다
- 6 9 7 10
- 따라서 방문 순서는 1 5 3 4 2 11 6 9 7 10
전위 순회는 부모를 앞에 두고 순회하는 방식이다, 무조건 부모 노드가 앞에 온다
- 부모 11을 중심으로 왼쪽 자식과 오른쪽 자식으로 나뉘며, 왼쪽 자식 4를 중심으로 또 나뉘어지게 된다
- 부모 먼저 들리기 때문에 4부터 간다 → 5부터 간다
- 11 4 5 1 3 2
- 11의 오른쪽 자식으로 가면 9를 중심으로 서브트리가 형성이 되어 있다
- 9부터 가고, 그다음 부모 트리인 6을 간다
- 9 6 7 10
- 따라서 방문 순서는 11 4 5 1 3 2 9 6 7 10
후위 순회는 부모가 맨 마지막에 가는 것이다. 왼쪽 자식 → 오른쪽 자식 → 부모 방식으로 순회한다
- 11을 중심으로 왼쪽 자식 4부터 이루어진다
- 서브트리 1 3 5 2 4 순서로 이루어지고(부모가 무조건 마지막에 온다) 오른쪽으로 간다
- 6 10 7 9
- 마지막에 11을 들린다
- 따라서 방문 순서는 1 3 5 2 4 6 10 7 9 11
BST (Binary Serch Tree)
이진 검색 트리를 의미하며, 부모 노드를 중심으로 왼쪽에 있는 자식 노드의 값은 부모 노드보다 작은 값으로 구성되고, 오른쪽의 자식 노드 값은 부모 노드보다 큰 값으로 구성되어 있다.
이진 검색 트리에서 중복값은 허용되지 않는다. 검색을 하려면 어떻게 해야 할까?
검색은 루트부터 시작해서 검색한다. 찾고자 하는 값이 루트에 있는 경우가 가장 베스트이다.
찾고자 하는 값이 루트보다 작거나 큰 경우, 작은 경우에는 왼쪽으로 이동해서 검색을 시작하고 크다면 오른쪽으로 이동해서 검색을 한다. 찾고자 하는 값이 7이고 루트 노드가 10이라면 루트(10)부터 비교해서 7은 10보다 작으니까 왼쪽으로 이동한다. 그 다음 5는 7보다 작은 값이니까 오른쪽으로 이동한다. 그러면 7을 찾게 된다
찾고자 하는 값을 루트부터 시작해서 작다면 왼쪽, 크다면 오른쪽으로 이동하면서 검색한다
- 최댓값/최솟값 : 루트를 중심으로 왼쪽 끝으로 가게 되면 그곳에 최솟값이 있고, 오른쪽 끝으로 가게 되면 그곳에 최댓값이 들어 있다. 최댓값과 최솟값은 왼쪽과 오른쪽 끝으로 가면 찾을 수 있다. (BST는 왼쪽 자식은 무조건 부모 노드보다 작고, 오른쪽은 무조건 작다)
- 원소 삽입 : 원소를 삽입하려면 삽입 할 위치부터 검색해야 한다. 17이라는 값을 삽입하려면, 17이라는 값이 10의 왼쪽으로 갈지 오른쪽으로 갈 지를 먼저 검색한다. 끝까지 찾아갔을 때 Null을 만나는 순간 원소를 삽입한다
- 원소 삭제
- 자식 노드가 없는 경우 : 예를 들어 자식 노드가 없는 19번을 삭제할 때, 왼쪽도 오른쪽도 null이기 때문에 자식 노드가 없다. 타깃을 삭제를 하고 부모 노드에게 null을 넘겨준다
- 왼쪽 자식 노드만 있는 경우 : 3번은 왼쪽 자식 노드만 있는데, 그냥 3번을 삭제하면 1번의 주소를 기억하는 노드가 없어지기 때문에 1번의 주소 값을 임시 변수 temp를 선언해서 넣어주고, 3번 노드를 제거한다음 temp의 값을 부모 노드인 5번에게 넘겨준다
- 오른쪽 자식 노드만 있는 경우 : 왼쪽 자식 노드만 있는 경우와 같다. 임시 변수 temp를 선언해서 자식 노드의 주소를 넣은다음 해당 노드를 삭제하면 부모에게 temp 주소 값을 넘겨준다
- 자식 노드가 둘 다 있는 경우 : 7번 노드 같은 경우는 왼쪽과 오른쪽 자식 노드를 모두 가지고 있다. 7은 자식 노드가 두개 있으면 삭제 되는 것이 아니다. 7의 왼쪽 자식 중 최댓값을 찾는다 (6이다) 이 값을 삭제할 위치로 넣어준다. 즉, 7의 자리에 6을 넣어준다. 왼쪽 자식 중 최댓값을 찾아서 올리고 왼쪽 자식 최댓값을 삭제하면 bst는 여전히 유지가 된다
레드 블랙 트리
BST의 한 종류로, BST 단점을 보완하고자 만들어졌다. 자바라는 언어에서 컬렉션 중 하나로 구현될만큼 굉장히 효율적이다.
BST의 문제점은 무엇일까? BST는 루트를 중심으로 루트보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 붙는 자료 구조이다.
만약 계속 큰 값이 할당되어서 오른쪽에만 붙는다면 특정 노드 값을 관측하기 위해 시간 복잡도가 모든 노드를 검색해야 하는 O(N)이 나오게 된다.
BST 목적은 루트를 중심으로 왼쪽이나 오른쪽으로 빠져서 둘 중 하나는 보지 않고도 문제를 해결하는 방법인데,
한쪽으로 편향되면 BST를 구현한 의미가 없어져버린다.
루트를 중심으로 왼쪽과 오른쪽, 균형을 맞춘 형태로 만들기 위해서, 레드 블랙 트리를 사용한다.
레드 블랙 트리는 노드에 레드, 블랙 색상 값을 구분지어서 스스로 균형을 잡게끔 하는 트리구조이다. 노드를 추가하고 나서 약간 조정하는 작업이 필요하다
다섯 가지 규칙을 모두 만족해야 레드 블랙 트리이다
NIL 노드란 노드 자체가 값을 가지고 있지 않다는 것으로, 값을 가지지 않는 더미 노드이다.
(메모리를 낭비하면서 가장 끝에 매달아 놓은 이유는 3규칙을 만족시키기 위해서이다)
블랙은 자식 노드가 블랙이어도 상관 없지만, 레드 노드의 자식은 무조건 블랙이어야 한다.
레드 블랙 트리의 회전 방법
레드 블랙 트리는 색깔 바꾸고 회전하고를 반복한다. 삽입, 삭제할 때는 회전을 잘 하면 된다
레드 블랙 트리에서 삽입, 삭제를 하려고 하면 삽입 삭제 시 레드 블랙 트리 규칙에 맞지 않는 경우가 생긴다.
데이터 노드를 하나 삭제하는 순간 레드 블랙 트리에 벗어나는 등… 그래서 회전하면서 균형을 맞추는 작업이 필요한데 우회전 하는 방법과 좌회전 하는 방법이 있다.
우측 회전은?
3번을 루트로 삼고 싶어서 6번 자리로 가려면 오른쪽으로 이동, 우회전이 된다.
루트 노드로 삼고 싶은 3번을 오른쪽으로 이동하기 위해서 3번을 임시변수 leftTemp에 잠시 넣어준다
3번을 루트로 삼고 싶어서 6번으로 올리게 되면 6과 10은 3보다 큰 값이고, 따라서 오른쪽 자식으로 붙어야 한다.
원래 3의 오른쪽에 있던 자식 5는 6보다는 항상 작은 값이다. 그래서 일단 3번의 오른쪽 자식 노드 값을 부모의 왼쪽 자식으로 연결을 해준다. 그 다음에 루트 노드가 된 3번의 오른쪽 자식으로 붙이면 된다
좌측 회전은?
6번을 부모로 만들고 싶을 때, 3번의 오른쪽 자식이란 3보다 무조건 다 큰 값들이다.
내가 6번을 루트로 만들 때 원래 부모였던 값들은 다 6보다 작은 값들이다.
내가 6을 부모로 올리면 3과 1은 6의 왼쪽 자식으로 붙어야 한다.
그러면 5는? 3과 1보다는 항상 큰 값이다. 그래서 3의 오른쪽의 자식으로 붙는다.
'컴퓨터 일반 > 자료구조론' 카테고리의 다른 글
| 자료구조 문제 정리 (1) 배열, 리스트 (4) | 2024.10.25 |
|---|---|
| 알고리즘 시간복잡도 (0) | 2024.10.24 |
| 선형 자료구조 (0) | 2024.10.24 |
| 그래프 알고리즘 (1) | 2024.10.23 |
| 자료구조 그래프 정리 (1) | 2024.10.23 |
