이진 트리 & 레드 블랙 트리

이진트리

한 노드는 하나의 값만을 지니며

노드의 왼쪽엔 자신보다 작은 값을, 오른쪽엔 큰 값을 지닌다

 

평균 시간 복잡도는 log n이지만 트리가 편향되경우 최악의 시간 복잡도는 O(n)

이를 위한 추가적인 조치는 없지만 그만큼 간단하다

 

 

삭제 알고리즘

1)삭제하려는 노드가 리프노드일경우 -> 그냥 삭제하면 됨

2)삭제하려는 노드의 자식이 하나일경우 -> 삭제 후 부모와 자식 노드를 연결

3)삭제하려는 노드의 자식이 둘일경우 

 

1.노드를 삭제하고 노드의 RMIN을 해당 위치에 넣는다

2.RMIN에게 rightNode가 있을 경우 이를 부모 노드와 연결한다

 

 

 

 

 

레드 블랙 트리

 

이진 트리에 레드와 블랙 개념을 도입한 트리

트리가 편향되는 것을 막아 최악의 경우에도 O(log n)의 시간 복잡도를 지님

b-tree에 비해 알고리즘이 복잡하지만 메모리 부분에서 효율적

 

 

https://blogshine.tistory.com/102

[알고리즘] Red-Black Tree : 레드 블랙 트리

더 자세한 규칙은 이 글 참고

 

 

 

 

 

 

https://m.blog.naver.com/dnjswns2280/221978771137

[Algorithm] 쉽게 배우는 알고리즘 6장 (검색 트리)