algorihthm1 [Algorithm] 6-3. Red-Black Tree 이번 시간에는 balanced search tree 중 하나인 red-black tree에 대해 알아보도록 하겠다. ● Red-Black Tree - red-black tree는 binary search tree로써, 아래의 4가지 조건을 만족한다. ① Root Property : root는 검은색이다. ② External Property : 모든 leaf node들은 검은색이다. ③ Internal Property : 빨간 노드의 자식들은 검은 노드이다. (부모와 자식이 모두 빨간색인 경우는 없다.) ④ Depth Property : 모든 leaf node들은 같은 black depth를 가져야한다. * black depth - 어떤 노드에서 root까지 가는 경로에 있는 black 노드들의 수. - .. 2020. 4. 28. 이전 1 다음
