지금까지 자료구조 중 비순차적 자료 구조는 해시 테이블 뿐이다
트리는 비순차적 자료구조 중 하나로
정보를 쉽게 검색하기 위해 저장할 때 유용하다
트리는 계층 구조를 추상화한 모델
트리는 부모 자식 관계를 가진 다수의 노드로 구성된다
최상위 노드를 제외한 각 노드는 부모 노드를 가지며
다수 ㄴ자식 노드를 가질 수 있고 없을 수도 있다
최상위 노드는 루트라고 하며 부모가 없는 노드
트리의 원소는 노드라고 부르고 내부 노드와 외부 노드로 나뉜다
1개 이상의 자식을 가진 노드는 내부 노드
자식이 하나도 없는 노드를 외부 노드 혹은 leaf 라고 부른다
서브트리는 노드와 후손으로 구성된다
트리를 이루는 트리를 서브 트리라고 한다
노드의 깊이는 조상의 개수다
이진 트리와 이진 탐색 트리
이진 트리에서 노드는 좌/우 각 하나씩 최대 2개의 자식 노드를 갖는다
노드의 삽입, 조회, 삭제를 효과적으로 수행할 수 있어
아주 폭넓게 활용된다
이진 탐색 트리는 이진 트리의 변형으로
좌측 자식 노드에는 더 작은 값을, 우측 자식 노드에는 더 큰 값을 가지고 있다
연결 리스트와 마찬가지로 노드간 연결은 포인터로 나타내고
간선이라고 표현한다
트리는 포인터가 2개 있는데 각각 좌, 우측 자식 노드를 가리킨다
트리에서는 노드를 원소라고 하지 않고 key 라고 한다
트리에서는 키로 노트를 식별한다
그 밖에는 연결리스트와 비슷하다
첫 번째 노드를 변수로 선언하여 제어하는 식으로 진행된다
트리에서는 헤드가 아닌 루트라는 점은 다르다
insert
search
inOrderTraverse: 중위 순회
preOrderTraverse: 전위 순회
postOrderTraverse: 후위 순회
min
max
remove
메서드를 가진다
트리 순회
트리의 노드를 방문하는 것을 트리 순회라고 한다
순회를 하는 방법은 여러가지가 있다
트리의 최상단에서 시작해서 하위로
최하단에서 상위로
좌측 부터, 우측부터 등을 결정해서 순회해야 한다
순회 방법은 크게 중위, 전위, 후위 세 가지로
분류된다
중위 순회
중위 순회는 BST 노드를 오름차순으로 방문한다
트리 정렬 시 사용된다
inOrderTraverse (callback) {
this.inOrderTraverseNode(this.root, callback)
}
inOrderTraverseNode(node, callback) {
if (node !== null) {
this.inOrderTraverseNode(node.left, callback)
callback(node.key)
this.inOrderTraverseNode(node.right, callback)
}
}inOrderTraverse 의 인자로 줄 콜백 함수에는
노드 방문 시 수행할 작업을 기술한다
이러한 방식의 프로그래밍을 방문자 패턴이라고 한다
BST 구현 알고리즘은 대부분 재귀 호출을 사용하므로
프라이빗 헬퍼 함수를 별도로 만들어
node 와 callback 을 전달한다
먼저 인자 node 가 null 인지 확인해야 한다
이렇게 재귀 호출이 중단되는 시점을
기본 상태라고 한다
전위 순회
자식 노드보다 노드 자신을 먼저 방문한다
구조화된 문서를 출력할 때 많이 사용된다
preOrderTraverse (callback) {
this.preOrderTraverseNode(this.root, callback)
}
preOrderTraverseNode(node, callback) {
if (node !== null) {
callback(node.key)
this.preOrderTraverseNode(node.left, callback)
this.preOrderTraverseNode(node.right, callback)
}
}전위 순회는 노드 자신을 먼저 방문한 후 좌측, 우측 순서로 방문한다
후위 순회
후위 순회는 자식 노드를 자신보다 먼저 방문한다
디렉토리와 서브 디렉토리의 파일 용량을 계싼할 때 쓰는 방법이라고 한다
postOrderTraverse (callback) {
this.postOrderTraverseNode(this.root, callback)
}
postOrderTraverseNode(node, callback) {
if (node !== null) {
this.postOrderTraverseNode(node.left, callback)
this.postOrderTraverseNode(node.right, callback)
callback(node.key)
}
}트리 노드 검색
- 최솟값 찾기
- 최댓값 찾기
- 특정 값 찾기
최솟값/최댓값 찾기
트리의 가장 좌측이 최소값, 우측이 최댓값이다
min () {
return this.minNode(root)
}
minNode(node) {
if (node) {
while (node && node.left !== null) {
node = node.left
}
return node.key
}
return null
}max 는 min 의 left 를 right 로만 변경해주면 된다
특정 값 찾기
search(key) {
return searchNode(root, key)
}
searchNode(node, key) {
if (node === null) return false
if (key < node.key) return this.searchNode(node.left, key)
if (key > node.right) return this.searchNode(node.right, key)
return true;
}노드 삭제
노드를 삭제하는 메서드는 가장 복잡하다
재귀 호출을 하는 동시에 상이한 경우의 수를 고려해야 하기 때문이다
remove(key) {
this.root = this.removeNode(root, key)
}
removeNode(node, key) {
if (node === null) return null
if (key < node.key) {
node.left = this.removeNode(node.left, key)
return node
}
if (key > node.key) {
node.right = this.removeNode(node.right, key)
}
// 리프 노드
if (node.left === null && node.right === null) {
node = null
return node
}
// 자식이 하나인 노드
if (node.left === null) {
node = node.right
return node
}
if (node.right === null) {
node = node.left
return node
}
// 자식이 둘인 노드
const aux = this.minNode(node.right)
node.key = aux.key
node.right = this.removeNode(node.right, aux.key)
return node
}리프 노드인 경우
리프 노드인 경우 해당 노드에만 null 을 대입하면 될 것 같지만
부모 노드를 가지고 있기 때문에 부모 노드 또한 null 로 만들어줘야 한다
이런 이유에서 노드의 값을 반환하는 것이다
자식이 하나인 노드의 경우
한 쪽에만 자식이 있는 경우에는 손주 노드를 연결시켜주고 삭제하면 된다
자식이 둘인 노드의 경우
좌/우측 모두 자식이 존재하는 경우는 가장 복잡한 케이스다
자식 노드와 함께 삭제하려면 다음 네 단계를 거쳐야 한다
- 우측 서브 트리부터 최소 노드를 찾는다
- 찾은 최소 노드의 값으로 수정한다 (삭제할 노드의 키 자체가 교체되므로 삭제되는 것)
- 2번의 결과로 동일 키를 가지는 노드가 중복되므로 우측 서브트리의 최소 노드를 2에서 삭제한 노드의 위치로 옮긴다
- 수정된 노드를 반환한다
왜 오른쪽으로 정했는지는 모르겠지만..
이진 트리 보충
BST 는 노드 개수에 따라 한 쪽으로만 깊은 간선이 늘어질 수 있다
이런 형태의 트리는 노드 추가/삭제 및 조회 시 간선에 따라 성능 문제가 발생할 수 있다
때문에 아델슨-벨스키와 랜디스의 트리(AVL) 라는 대안이 만들어졌다
스스루 균형을 잡는 BST 트리의 일종으로 어떤 노드의 높이도 1 이상 차이나지 않도록 조정한다
레드-블랙 트리는 중위 순회 과정이 효율적이고
힙 트리라는 종류도 있다
