[알고리즘] 이진검색트리 BST(binary search tree)

코딩테스트 때 툭 치면 툭 나와야 할 코드 스니펫 모음.

이진 검색 트리

반복문

Node findNode(Node root, int value){
    while(root != null){
        int currval = root.getValue();
        if(currval == value){
            break;
        }
        if(currval < value){
            root = root.getRight();
        } else { // currval > value
            root = root.getLeft();
        }
    }
    return root;
}

재귀

tree 문제는 일단 반복문보다 재귀부터 고려해볼 것. 

Node findNode(Node root, int value){
    if(root == null){
    	return null;
    }
    int currval = root.getValue();
    if(currval == value){
    	return root;
    }
    
    if(currval < value){
        return findNode(root.getRight(), value);
    } else { // currval > value
        return findNode(root.getLeft(), value);
    }
}

• Balanced search tree의 룩업 수행 시간 O(log(n))
  balanced되지 않은 tree의 경우, 최악의 경우 노드마다 자식이 하나씩만 있을 수 있고 이 경우 연결리스트와 같아짐. 그런 경우 연결리스트와 마찬가지로 O(n) 연산이 됨.
• 삭제 및 삽입: O(log(n))
• 모든 노드를 정렬된 순서로 출력: O(n)
• 특정 노드보다 높은 노드 룩업: O(log(n))