이진 탐색 트리

박상훈·2022년 4월 8일

용어

노드(node) : 실제로 저장하는 데이터
루트 노드(root node) : 최상위에 위치한 데이터
리프 노드(leaf node) : 마지막에 위치한 데이터
부모 관계 : 연결된 노드들 간의 상대적 관계
자식은 없을 수도, 많이 있을 수도, 부모는 하나, 조부모/삼촌/형제자매 등...
깊이(depth) : 노드 -> 루트 경로의 길이, 루트 = 0, 부모 자식관계 마다 + 1
높이(height) : 노드 -> 리프 경로의 최대(여러 자식 중 깊이가 제일 깊은) 길이
하위 트리(subtree) : 어떤 노드 아래의 모든 것을 포함하는 트리

자식 수에 따른 트리 구조

자식 수 여럿인 경우

public class Node {
	private int data;
    private ArrayList<Node> children;
}

자식이 둘인 경우

public class Node {
	private int data;
    private Node left;
    private Node right;
}

자식이 하나인 경우

public class Node {
	private int data;
    private Node next;
}

용도

계층적 데이터를 표현
HTML, XML 의 문서 개체 모델(DOM) 을 표현
JSON, YAML 처리 시 계층 관계를 표현
프로그래밍 언어를 표현하는 추상 구문 트리(abstract syntax tree)

이진 트리

자식이 최대 둘
무언가 계층적(재귀적) 으로 이분해 나갈 때 적합
무언가를 이분하는 기준(탐색에 특화 된) 을 만들면 이진 탐색 트리

이진 탐색 트리

이진 트리에 이분하는 규칙을 추가
왼쪽 자식은 언제나 부모보다 작다
오른쪽 자식은 언제나 부모와 같거나 크다
위 두 조건은 반대여도 성립

트리 순회법

전위(pre-order) 순회법 : 부모 , left, right
중위(in-order) 순회법 : left, 부모, right
후위(post-order) 순회법 : left, right, 부모

루트 -> 리프 순 전위 순회
리프 -> 노드 순 후위 순회
순서대로 -> 중위 순회

BST 탐색, 삽입, 삭제

Node Class

public class Node {
	private int data;
    private Node left;
    private Node right;
}

탐색

기본적으로 이진 탐색과 동일(재귀적 분할 정복)
차이점은 각 노드마다 두 하위 트리로 이분됨
하위 트리로 내려갈 때마다 검색 공간이 절반으로 줄어 시간복잡도는 O(log n)

public static Node getNodeOrNull(Node node, int data) {
    if (node == null) {
        return null;
    }

    if (node.data == data) {
        return node;
    }

    if (data < node.data) {
        return getNodeOrNull(node.left, data);
    }
    return getNodeOrNull(node.right, data);
}

삽입

새로운 노드를 받아줄 수 있는 부모 노드를 찾음
그 후 노드 추가
새로 추가되는 값은 언제나 리프 노드

public static Node insertRecursive(Node node, int data) {
    if (node == null) {
        return new Node(data);
    }

    if (data < node.data) {
        node.left = insertRecursive(node.left, data);
    } else {
        node.right = insertRecursive(node.right, data);
    }

    return node;
}

삭제

트리에서 노드를 지울 때 언제나 리프 노드를 제거
지울 값을 가지고 있는 노드를 찾음
노드의 바로 전 값을 가진 노드를 찾음
두 값 교환
리프 노드 삭제
오른쪽 하위 트리에서 최솟값(제일 왼쪽 리프 in-order successor)
왼쪽 하위 트리에서 최대값(제일 오른쪽 리프 in order predecessor)