이진트리 & 레드-블랙트리
"이진 탐색 트리는 기본적으로 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 커야한다." 를 전제로 한다. BST(Binary Searching Tree) : 이진탐색트리 이진트리는 아래와 같은 규칙을 갖는다. 삽입 삽입을 하기 전, 검색을 수행한다. 트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다. 삭제 자식노드가 없는 노드(리프 노드) 삭제 해당 노드를 단순히 삭제한다. 자식노드가 1개인 노드 삭제 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 대입한다. 자식노드가 2개인 노드 삭제 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰값으로 변경하거나, 오른쪽 서브트리에서 가장 작..
DS(Data Structure)
2021. 3. 5. 14:50
