tree

Binary Search Tree 아래 그림과 같이 한 쪽으로 편향될 수 있다. 그렇기에 insert, delete, find 함수의 시간 복잡도는 최악의 경우 O(n), 가장 효율적으로는 O(log(n))이 된다. 즉, 높이 h에 따른다는 것을 알 수 있다. Insert root부터 해당 value 값보다 작으면 left, 크면 right로 내려가 NULL이 아닐때 까지 탐색 Delete 1. child 중 NULL이 있는 경우 -> external이 아닌 노드를 그대로 이어 붙이면 해결된다. 아래 그림은 child에 NULL이 있는 경우인 빨간색 노드를 삭제하는 경우이다. 2. 하지만 만약 child 모두 internal 이라면, 얘기가 달라진다. 아래 그림은 internal node인 빨간색을 삭제..

이진트리란 자식 노드의 수가 0 ~ 2개인 트리를 말한다. 이를 재귀적으로 표현할 수 있는데, 단일 노드이거나 해당 노드의 자식 노드가 모두 이진 트리라면 해당 노드를 이진트리라고 부른다. 완전이진트리란 이진트리를 채워나갈 때 마지막 노드가 왼쪽부터 차례대로 채워진 트리의 형태이다. 위 그림에서 볼 수 있듯이, internal 노드의 수는 3, external 노드의 수는 3, 높이 h는 2이다. external 노드가 왼쪽부터 차례대로 채워졌으므로 위의 트리는 완전이진트리가 된다. 만약 왼쪽부터 채우다가 오른쪽 끝까지, 즉 external 노드의 수가 2^h개라면 이를 포화이진트리라고 부른다. internal 노드의 수는 3, external 노드의 수는 4, 높이 h는 2이다. external 노드가..