트리
그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.
트리에서 최상위 노드를 루트 노드(root node 뿌리 노드)라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.
이진 검색 트리 (평균 시간)
탐색 : O(logn)
삽입 : O(logn)
삭제 : O(logn)
단점
아래의 그림과 같이 한쪽으로 치우쳐져 있으면 성능이 좋지 않다.
레드-블랙 트리(red-black tree)
레드-블랙 트리(red-black tree)를 사용하면 스스로 균형을 맞춘다.
레드-블랙 트리는 자료의 삽입과 삭제, 검색에서 최악의 경우에도 일정한 실행 시간을 보장한다(worst-case guarantees). 이는 실시간 처리와 같은 실행시간이 중요한 경우에 유용하게 쓰일 뿐만 아니라, 일정한 실행 시간을 보장하는 또 다른 자료구조를 만드는 데에도 쓸모가 있다. 예를 들면, 각종 기하학 계산에 쓰이는 많은 자료 구조들이 레드-블랙 트리를 기반으로 만들어져 있다.
참고
사이트 : 위키백과 트리구조
사이트 : 위키백과 레드블랙트리
도서 : 그림으로 개념을 이해하는 알고리즘