[자료구조/Java] 이진탐색트리 (Binary Search Tree)

[자료구조/Java] 이진탐색트리 (Binary Search Tree) - 각 노드의 자식이 2개 이하인 트리 - 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼 노드 삽입 시간 균등 트리 : 노드 개수 N개일 때 O(logN) 편향 트리 : 노드 개수 N개일 때 O(N) 삽입,검색,삭제의 시간복잡도는 트리 높이에 비례함 삭제가 조금 까다로움 (3가지 case) 1. 자식이 없는 leaf 노드면? → 그냥 지우면 끝 2. 자식이 1개인 노드면? → 지워진 노드에 자식을 올리면 끝 3. 자식이 2개인 노드면? - 자식 노드 중에서 삭제할 노드보다 크면서 가장 작은 값 - 자식 노드 중에서 삭제할 노드보다 작으면서 가장 큰 값 편향된 트리(ex. 정렬된 상태인 값을 트리로 만들면 한쪽으로 뻗는다)에서..