이진 탐색 트리는 '이진 탐색'을 위한 '이진 트리' 입니다.
이진 탐색 알고리즘의 경우 배열인 경우에만 사용할 수 있는 문제가 있습니다.
링크드 리스트는 중앙 요소를 알 수 없기때문에 이진 탐색이 불가능합니다.
이 딜레마를 해결해주는 자료구조가 바로 '이진 탐색 트리' 입니다.
이진 트리 탐색은 규칙이 있습니다.
왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 크다.
위에서 부터 자식노드를 탐색을 하게 됩니다.
데이터도 위의 규칙대로 추가 되게 됩니다.
만약 20 노드가 삭제 될 시에는 삭제된 노드의 오른쪽 하위 트리에서 가장 작은 값을 가진 노드로 위치가 옮겨가면 됩니다.
이진트리의 문제점
이진 탐색 트리의 경우 동적으로 크기가 증가해도 잘 대처 하며 탐색속도도 매우 훌륭합니다. 하지만 문제가 있는데 트리가 기형적으로 성장할 경우 검색의 효율을 극단적으로 떨어뜨리게 됩니다.
레드 블랙 트리
순수한 이진 탐색 트리는 불균형하게 자라는 경우가 많습니다. 이런경우 검색 효율이 심각하게 저하 되게 됩니다.
이 문제에 대한 해답으로 레드 블랙 트리가 있습니다.
레드 블랙 트리는 아래와 같은 규칙을 가지고 있습니다.
1. 모든 노드는 빨간색 아니면 검은색이다.
2. 루트 노드는 검은 색이다.
3. 잎 노드는 검은 색이다.
4. 빨간 노드의 자식들은 모두 검은색이다. 하지만 검은색 노드의 자식이 빨간색일 필요는 없다.
5. 루트 노드에서 모든 잎 노드 사이에 있는 검은색 노드의 수는 모두 동일하다.
참고 URL
레드 블랙 트리 -1
레드 블랙 트리 -2