[책] 프로그래밍 면접 이렇게 준비한다 - Ch6. 트리와 그래프(작성중)

트리

이진 검색 트리(BST)

룩업

• 수도 코드
• 찐 코드

특성

• 균형 이진 검색 트리에서 룩업 : O(log(n))
• 삭제 및 삽입 : O(log(n))
• 왼쪽 자식만 따라가면 가장 작은 값, 오른쪽 자식만 따라가면 가장 큰 값
• 모든 노드를 정렬된 순서로 출력 : O(n)
• 어떤 노드 다음으로 높은 노드 찾기 : O(log(n))

그래프

트리 및 그래프 문제

트리 높이

int getTreeHeight(Node N)
{
if (n==null) return 0;
return 1+ Math.max( getTreeHeight(N.getLeft(), getTreeHeight(N.getRight() );
}

• O(N)

프리오더

재귀 O

void preorderTraversal( Node root )
{
if (root == null ) return;
root.printValue();
preorderTraversal(root.getLeft());
preorderTraversal(root.getRight());
}

• O(N)

재귀 X

• 스택을 만든다.
• 루트 노드를 스택에 넣는다.
• 스택이 바어 있지 않은 동안
  • 노드를 하나 꺼낸다.
  • 출력
  • 오른쪽 자삭이 있다면 스택에 넣는다.
  • 왼쪽 자식이 있다면 스택에 넣는다.

void preorderTraversal( Node root )
{
Stack stack = new Stack();
stack.push(root);
while(!stack.empty())
{
Node curr = stack.pop();
curr.printValue();
Node n = curr.getRight();
if(n != null) stack.push(n);
Node n = curr.getLeft();
if(n != null) stack.push(n);
}
}

• O(N)

가장 가까운 공통 조상(BST에서)

• 현재 노드 검사
  • value1과 value2가 현재 노드보다 작으면
    • 왼쪽 자식 검사
  • value1과 value2가 현재 노드보다 크면
    • 오른쪽 자식 검사
  • 그렇지 않으면
    • 현재 노드가 최소 공통 조상
• O(log(n))

요약