가장 많이 쓰이는 완전 이진트리에 대해 정리하겠습니다. 완전 이진트리는 마지막 레벨을 제외한 나머지 레벨의 자식수가 2개로 꽉 차 있고 마지막 레벨에서는 왼쪽부터 자식이 차는 트리입니다. 한쪽으로 쭉 뻗어있는 편향트리도 이진트리라고는 할 수 있지만, 완전이진트리는 아니죠.

완전 이진트리는 각 레벨에 최대 2^N개의 노드가 들어갈 수 있죠. 이로인해 총 노드의 수는 최대 2^k -1개 까지 가질 수 있습니다.

이진탐색트리

이진탐색트리는 이진트리의 성질과 함께 부모노드와 자식노드간의 비교에 따라 왼쪽, 오른쪽 나누어 저장하는 자료구조입니다.

오른쪽 자식노드는 부모보다 커야하고, 왼쪽자식노드는 부모보다 작아야하는 규칙을 갖죠. 이외에도 각 노드는 유일한 값을 가져야 한다는 추가 규칙도 있습니다.

따라서 탐색에 소요되는 시간복잡도는 O(logN)입니다. 다만 최악의 경우 편향트리가 되어 O(N)이 될 수도 있습니다.

특정

• 이진탐색 트리의 순회는 중위순회(in order)방식입니다. 왼쪽 → 루트 → 오른쪽 순이죠. 이렇게하면 정렬된 순서를 읽을 수 있습니다.
• 중복된 노드가 없어야합니다. 검색을 목적으로 하는 자료구조이기 때문에 굳이 중복이 많은 경우 이 트리를 사용할 필요가 없습니다. 트리에 삽입하는 것보다 노드에 Count 변수를 두는것이 훨씬 효율적이죠.

BST(Binary Search Tree의 핵심 연산)

• 검색 - O(logN), 최악 O(N)
• 삽입 - O(logN), 최악 O(N)
  • 루트노드와 비교해가며 위치를 찾아 추가합니다.
• 삭제
  • 루트노드부터 탐색하여 노드를 찾습니다. 다만 자식노드가 있는 경우 해당 노드를 삭제하고 해당 노드의 자식노드와 부모노드를 연결해줍니다.
  • 다만 삭제하려는 자식노드가 2개인 경우 탐색 → 해당노드 삭제 →오른쪽 서브트리의 최소값을 부모노드에 할당 순서로 동작합니다.
  • O(logN), 최악 O(N)
• 트리생성
• 트리삭제