[자료구조/JAVA] 트리 (2) : 이진 탐색 트리(Binary Search Tree, BST)
이진 탐색 트리(Binary Search Tree, BST)
앞의 포스팅에서는 이진 트리에 대해서 알아 보았었다. 그런데 이진 트리는 정렬되지 않은 형태이므로 탐색을 수행하기 적절하지 않았다.
이를 위해서 이진 트리의 특수한 형태인 이진 탐색 트리가 있으며, 정렬된 형태의 이진 트리이고 이는 탐색을 위한 트리로서 사용될 수 있다.
다음 규칙들이 추가되었다고 생각하면 된다.
구조 : 각 노드의 왼쪽 서브 트리에 있는 모든 값은 해당 노드의 값보다 작거나 같다. 오른쪽 서브 트리에 있는 모든 값은 해당 노드의 값보다 크거나 같다.
삽입 규칙: 새로운 값을 삽입할 때, 구조 규칙에 따라 트리를 탐색하며 적절한 위치를 찾는다.
특정 값 삭제 : 해당 노드를 삭제하고, 트리 구조 규칙에 맞추기 위해 재배치하는 로직을 거친다.
즉, 이진 탐색의 개념을 트리 형태의 구조에 접목한 자료구조이다.
이진 탐색 : 정렬된 데이터의 중간에 위치한 항목을 기준으로 데이터를 두 부분으로 나누어 가며 탐색하는 방법
이진탐색 트리의 특징 : 트리를 중위순회(Inorder)하면 정렬되어 출력된다.
- 위의 트리를 중위순회하면 1-3-4-6-7-8-10-13-14
이진 탐색 트리 구현 : 기본 구조 작성
class BSTNode<Key extends Comparable<Key>, Value> {
Key key;
Value value;
BSTNode<Key, Value> left;
BSTNode<Key, Value> right;
public BSTNode(Key key, Value value){
this.key = key;
this.value = value;
}
//Getter & Setter (key, value, left, right)
}
이진 탐색 트리의 노드 구조이다.
정렬 및 검색을 위한 Key값과, 이에 따르는 Value, 그리고 왼쪽 자식 노드와 오른쪽 자식 노드를 구조로 가진다.
class BinarySearchTree<Key extends Comparable<Key>, Value>{
BSTNode<Key, Value> root;
// 전위 순회
public void preorder(){
this.preorder(this.root);
}
private void preorder(BSTNode<Key, Value> n){
if(n != null){
System.out.print(n.key + " ");
preorder(n.left);
preorder(n.right);
}
}
// 중위 순회
public void inorder(){
this.inorder(this.root);
}
private void inorder(BSTNode<Key, Value> n){
if(n != null){
inorder(n.left);
System.out.print(n.key + " ");
inorder(n.right);
}
}
// 후위 순회
public void postorder(){
this.postorder(this.root);
}
private void postorder(BSTNode<Key, Value> n){
if(n != null){
postorder(n.left);
postorder(n.right);
System.out.print(n.key + " ");
}
}
// 레벨 순회
public void levelorder(){
this.levelorder(this.root);
}
private void levelorder(BSTNode<Key, Value> n){
Queue queue = new LinkedList<BSTNode<Key, Value>>();
queue.add(n);
while(!queue.isEmpty()){
BSTNode<Key, Value> current = (BSTNode<Key, Value>) queue.poll();
System.out.print(current.key + " ");
if(current.left != null){
queue.add(current.left);
}
if(current.right != null){
queue.add(current.right);
}
}
}
public int getHeight(){
return this.getHeight(this.root);
}
private int getHeight(BSTNode<Key, Value> n){
if(n == null){
return 0;
}
else{
return 1 + Math.max(getHeight(n.left), getHeight(n.right));
}
}
public int getSize(){
return this.getSize(this.root);
}
private int getSize(BSTNode<Key, Value> root){
if(root == null){
return 0;
}
else{
return 1 + getSize(root.left) + getSize(root.right);
}
}
public boolean isEqual(BinarySearchTree<Key, Value> compare){
return this.isEqual(this.root, compare.root);
}
private boolean isEqual(BSTNode<Key, Value> n, BSTNode<Key, Value> m){
if(n == null || m == null){
return n == m; //둘 다 null일 경우 True, 아니면 False(XOR)
}
if (n.key.compareTo(m.key) != 0){
return false;
}
return isEqual(n.left, m.left) && isEqual(n.right, m.right);
}
}
앞선 포스팅에서 이진 트리를 구현할 때의 기본적인 연산들을 작성해주었다.
포함된 연산으로는 전위 순회, 중위 순회, 후위 순회, Height 구하기, Node의 수 구하기, 트리가 동일한지에 대해 판단하는 메서드들이다.
만약 해당 내용이 이해가 되지 않는다면 아래의 포스팅을 참고하도록 하자.
https://sjh9708.tistory.com/203
[자료구조/JAVA] 트리 (1) : 이진 트리(Binary Tree) : 순회 및 연산
트리(Tree) 계층적인 구조를 표현하는 데 사용되는 비선형 자료 구조. 트리는 노드(node)들의 집합이며, 각 노드는 부모(parent)와 자식(children) 관계로 연결된다. 중요한 특징으로는 순환이 없다는 점
sjh9708.tistory.com
이진 탐색 트리 구현 : 탐색 연산
public BSTNode search(Key k){
return search(k, this.root);
}
private BSTNode search(Key k, BSTNode n){
if(n == null){
return null;
}
int comp = n.getKey().compareTo(k);
if(comp == 0){
return n;
}
else if(comp > 0){ // 현재 노드보다 키값이 작은 경우
return search(k, n.getLeft());
}
else{
return search(k, n.getRight());
}
}
1. 검색 시작: 루트 노드에서 검색을 시작
2. 키 비교: 검색하려는 k를 현재 서브트리의 루트 노드의 키와 비교
k가 현재 노드의 키보다 작으면 왼쪽 서브트리로 이동
k가 현재 노드의 키보다 크면 오른쪽 서브트리로 이동
3. 재귀: 해당 과정을 키를 찾을 때 까지 재귀적으로 반복
k가 현재 노드의 키와 일치하면 탐색에 성공한 것. 해당 노드를 반환
이동을 반복하다가 Null인 하위 노드를 만나면 이는 k가 트리에 존재하지 않는다는 것을 의미하고 null을 반환
이진 탐색 트리 구현 : 삽입 연산
public void insert(Key k, Value v){
this.root = insert(k, v, root);
}
private BSTNode insert(Key k, Value v, BSTNode n){
if(n == null){
return new BSTNode(k, v);
}
int comp = n.getKey().compareTo(k);
// insert 재귀는 두 가지 케이스를 반환함.
// case1. 서브트리 탐색 끝에 Null일 경우에는 새로운 노드 반환
// case2. 서브트리 탐색 시 노드가 존재할 경우 기존 노드 반환
if(comp == 0){ // 같은 키값의 노드 -> Value만 갱신(Key 중복 허용 X)
n.setValue(v);
}
else if(comp > 0){ // 현재 노드보다 키값이 작은 경우 -> case1) 왼쪽에 삽입 or case2) 기존 left 노드를 setLeft(변화 없음)
n.setLeft(insert(k, v, n.getLeft()));
}
else{ // 현재 노드보다 키값이 큰 경우 -> 오른쪽 서브트리에 삽입 -> case1) 오른쪽에 삽입 or case2) 기존 right 노드를 setRight(변화 없음)
n.setRight(insert(k, v, n.getRight()));
}
return n;
}
1. null 체크: 해당 위치가 null이라면, 삽입할 위치라는 뜻이다. 새로운 노드를 생성하여 반환한다.
2. 키 비교: 삽입하려는 k를 현재 노드의 키와 비교한다.
k가 현재 노드의 키보다 작으면 왼쪽 서브트리로 이동
k가 현재 노드의 키보다 크면 오른쪽 서브트리로 이동
k가 현재 노드의 키와 같다면 같은 키가 이미 존재하는 것. Value만 갱신하고 현재 노드를 반환한다.
3. 재귀 호출: 2번 과정을 왼쪽 또는 오른쪽 삽입 위치를 찾을 때까지 서브트리에 재귀적으로 호출한다.
4. 노드 반환: 삽입이 완료되면 삽입된 노드를 반환
이진 탐색 트리 구현 : 노드의 최대값과 최소값 구하기
public BSTNode getMin(){
if(this.root == null){
return null;
}
return getMin(this.root);
}
private BSTNode getMin(BSTNode n){
if(n.getLeft() == null){
return n; //Left 존재하지 않으면 최소값
}
return getMin(n.getLeft()); //최소값 나올때까지 left로 이동하며 재귀호출
}
public BSTNode getMax(){
if(this.root == null){
return null;
}
return getMax(this.root);
}
private BSTNode getMax(BSTNode n){
if(n.getRight() == null){
return n; //Right가 존재하지 않으면 최대값
}
return getMax(n.getRight()); //최대값 나올때까지 right로 이동하며 재귀호출
}
최소값은 왼쪽 서브트리로 계속 이동하다가, 노드의 left가 비어 있는 것이 확인된다면 해당 노드가 최소값이 된다.
이를 재귀적으로 left가 null일 때 까지 호출하다가 해당 조건 만족 시 해당 노드(최소값 노드)를 반환한다.
마찬가지로 최대값 또한 오른쪽 서브트리로 계속 이동하다가 right가 null인 노드를 반환한다.
이진 탐색 트리 구현 : 최소값 삭제 연산
public void deleteMin(){
this.root = deleteMin(this.root);
}
private BSTNode deleteMin(BSTNode n){
if(n.getLeft() == null){
return n.getRight(); //Left 존재하지 않으면 최소값
}
n.setLeft(deleteMin(n.getLeft())); //최소값 나올 때 까지 Left로 이동
return n;
}
해당 노드가 Root인 서브트리에서 최소값을 탐색한다.
재귀적으로 left로 이동하면서, left가 null인 경우가 최소값이 될 것이라는 것은 앞의 연산을 통해 알 수 있었다.
이 때 최소값 노드를 발견하면 두 가지 케이스로 삭제한다.
1. 오른쪽 서브트리가 존재하는 경우 : 오른쪽 서브트리의 루트 노드를 해당 최소값 노드의 위치로 대체하고 삭제한다.
2. 오른쪽 서브트리가 존재하지 않는 경우 : 이 경우 자식 노드가 없다. 따라서 null로 설정하여 삭제한다.
해당 두 가지 케이스는 삭제 대상의 위치를 삭제 대상의 right로 변경하면 해결된다. (right는 있거나, null이거나 일 테니)
이진 탐색 트리 구현 : 삭제 연산
public void delete(Key k){
this.root = delete(k, this.root);
}
private BSTNode delete(Key k, BSTNode n){
if(n == null){
return null;
}
int comp = n.getKey().compareTo(k);
if(comp > 0){ // 현재 노드보다 키값이 작은 경우 -> 왼쪽 서브트리로 이동하며 delete() 재귀호출
n.setLeft(delete(k, n.getLeft()));
}
else if(comp < 0){ // 현재 노드보다 키값이 큰 경우 -> 오른쪽 서브트리로 이동하며 delete() 재귀호출
n.setRight(delete(k, n.getRight()));
}
else{ // 삭제할 노드 발견
if(n.getRight() == null){ //오른쪽 서브트리가 없는 경우 : 왼쪽 서브트리를 현재 노드의 위치로 연결
return n.getLeft();
}
if(n.getLeft() == null){ //왼쪽 서브트리가 없는 경우 : 오른쪽 서브트리를 현재 노드의 위치로 연결
return n.getRight();
}
//양쪽 서브트리가 없는 경우 : 위 코드에 의해서 해당 노드가 null로 변경된다.
//양쪽 서브트리가 모두 존재하는 경우
BSTNode targetNode = n; // 삭제 대상 노드를 targetNode로 설정
n = getMin(targetNode.getRight()); // 대체 : 삭제 대상의 오른쪽 서브트리의 최소값 노드를 삭제 위치로 이동
n.setRight(deleteMin(targetNode.getRight())); // 대체 노드의 right : 삭제 대상의 right 서브트리로 설정 + 이동된 노드는 제거
n.setLeft(targetNode.getLeft()); // 대체 노드의 left : 삭제 대상의 left 서브트리로 설정
}
return n;
}
삭제 연산은 BST의 규칙에 맞추어 삭제 후 노드를 재배치해주어야 할 필요가 있다.
따라서 삭제 대상 노드를 탐색 -> 케이스 별로 삭제 후, 기존 노드의 재배치 과정을 거친다.
재귀 호출: 현재 노드 n의 키와 삭제하려는 키 k를 비교한다.
- 키가 작을 경우: 왼쪽 서브트리에 delete 함수 재귀호출 -> 왼쪽 서브트리로 이동
- 키가 클 경우: 오른쪽 서브트리에 delete 함수 재귀호출 -> 오른쪽 서브트리로 이동
- 현재 노드가 null일 경우 : 삭제할 노드가 존재하지 않으므로 null을 반환
삭제할 노드 발견: 현재 노드 n의 키가 k와 같을 경우 삭제 작업을 수행한다.
- 오른쪽 서브트리가 없는 경우: 왼쪽 서브트리를 현재 노드의 위치로 연결
- 왼쪽 서브트리가 없는 경우: 오른쪽 서브트리를 현재 노드의 위치로 연결
- 두 서브트리가 모두 없는 경우 : 현재 노드의 위치를 null로 설정
- 두 서브트리가 모두 있는 경우: 양쪽 서브트리가 모두 존재한다면 삭제 이후 기존 노드들을 가장 재배치하기 쉬운 방법은 삭제될 대상 노드 다음으로 큰 값으로 변경하는 것이다. 이는 오른쪽 서브트리의 최소값 노드를 삭제 대상 노드 위치로 이동시킨다는 말과 같다.
1. 삭제 대상 노드 : targetNode, 삭제될 위치에 삽입될 기존 노드 : n
2. 오른쪽 서브트리의 최소값 노드를 삭제 노드의 위치로 이동 (n에 저장)
3. deleteMin 함수를 재귀적으로 호출하여 최소값 노드를 기존 위치에서 삭제
4. n의 오른쪽 서브트리에 기존 삭제 대상 노드(targetNode)의 오른쪽 서브트리를 연결
5. n의 왼쪽 서브트리에 기존 삭제 대상 노드(targetNode)의 왼쪽 서브트리를 연결
삭제 과정 : 오른쪽 서브트리, 왼쪽 서브트리 둘 중 하나만 있는 경우
삭제 대상 노드가 하나의 서브트리만을 가진다면 이야기가 쉽다. 단지 해당 서브트리의 루트 노드를 삭제 위치로 옮겨주기만 하면 되기 때문이다.
삭제 과정 :두 서브트리가 모두 있는 경우
1. 삭제 대상 노드 : targetNode, 삭제될 위치에 삽입될 기존 노드 : n
2. 오른쪽 서브트리의 최소값 노드를 삭제 노드의 위치로 이동 (n에 저장)
먼저 해당 과정처럼 삭제 대상이 targetNode가 될 것이고, 오른쪽 서브트리에서의 최소값이 n으로 설정될 것이다.
이제 targetNode의 위치에 n이 설정될 것이고, 아직 왼쪽 서브트리와 오른쪽 서브트리의 재배치를 하지 못한 상황이다.
3. deleteMin 함수를 재귀적으로 호출하여 최소값 노드를 기존 위치에서 삭제
이제 300이라는 값은 삭제 대상 노드의 위치로 재배치되었으므로, 기존 서브트리에서 해당 노드를 삭제하고 재배치하는 과정을 거쳐준다.
해당 서브트리에서 알 수 있듯, 300이 삭제된 형태의 이진 탐색 트리는 200이 300으로 대체되어도 이상할 것이 없는 형태가 되었다.
4. n의 오른쪽 서브트리에 기존 삭제 대상 노드(targetNode)의 오른쪽 서브트리를 연결
5. n의 왼쪽 서브트리에 기존 삭제 대상 노드(targetNode)의 왼쪽 서브트리를 연결
따라서 이제 왼쪽 서브트리와 오른쪽 서브트리를 n에 연결시켜 주면 된다.해당 과정을 통해 삭제 대상 노드가 오른쪽 서브트리의 최소값으로 대체되었으며 노드의 배치도 올바르게 이루어졌다.
전체 코드
class BSTNode<Key extends Comparable<Key>, Value> {
Key key;
Value value;
BSTNode<Key, Value> left;
BSTNode<Key, Value> right;
public BSTNode(Key key, Value value){
this.key = key;
this.value = value;
}
public Key getKey() {
return key;
}
public void setKey(Key key) {
this.key = key;
}
public Value getValue() {
return value;
}
public void setValue(Value value) {
this.value = value;
}
public BSTNode<Key, Value> getLeft() {
return left;
}
public void setLeft(BSTNode<Key, Value> left) {
this.left = left;
}
public BSTNode<Key, Value> getRight() {
return right;
}
public void setRight(BSTNode<Key, Value> right) {
this.right = right;
}
}
class BinarySearchTree<Key extends Comparable<Key>, Value>{
BSTNode<Key, Value> root;
// 전위 순회
public void preorder(){
this.preorder(this.root);
}
private void preorder(BSTNode<Key, Value> n){
if(n != null){
System.out.print(n.key + " ");
preorder(n.left);
preorder(n.right);
}
}
// 중위 순회
public void inorder(){
this.inorder(this.root);
}
private void inorder(BSTNode<Key, Value> n){
if(n != null){
inorder(n.left);
System.out.print(n.key + " ");
inorder(n.right);
}
}
// 후위 순회
public void postorder(){
this.postorder(this.root);
}
private void postorder(BSTNode<Key, Value> n){
if(n != null){
postorder(n.left);
postorder(n.right);
System.out.print(n.key + " ");
}
}
// 레벨 순회
public void levelorder(){
this.levelorder(this.root);
}
private void levelorder(BSTNode<Key, Value> n){
Queue queue = new LinkedList<BSTNode<Key, Value>>();
queue.add(n);
while(!queue.isEmpty()){
BSTNode<Key, Value> current = (BSTNode<Key, Value>) queue.poll();
System.out.print(current.key + " ");
if(current.left != null){
queue.add(current.left);
}
if(current.right != null){
queue.add(current.right);
}
}
}
public int getHeight(){
return this.getHeight(this.root);
}
private int getHeight(BSTNode<Key, Value> n){
if(n == null){
return 0;
}
else{
return 1 + Math.max(getHeight(n.left), getHeight(n.right));
}
}
public int getSize(){
return this.getSize(this.root);
}
private int getSize(BSTNode<Key, Value> root){
if(root == null){
return 0;
}
else{
return 1 + getSize(root.left) + getSize(root.right);
}
}
public boolean isEqual(BinarySearchTree<Key, Value> compare){
return this.isEqual(this.root, compare.root);
}
private boolean isEqual(BSTNode<Key, Value> n, BSTNode<Key, Value> m){
if(n == null || m == null){
return n == m; //둘 다 null일 경우 True, 아니면 False(XOR)
}
if (n.key.compareTo(m.key) != 0){
return false;
}
return isEqual(n.left, m.left) && isEqual(n.right, m.right);
}
public BSTNode search(Key k){
return search(k, this.root);
}
private BSTNode search(Key k, BSTNode n){
if(n == null){
return null;
}
int comp = n.getKey().compareTo(k);
if(comp == 0){
return n;
}
else if(comp > 0){ // 현재 노드보다 키값이 작은 경우
return search(k, n.getLeft());
}
else{
return search(k, n.getRight());
}
}
public void insert(Key k, Value v){
this.root = insert(k, v, root);
}
private BSTNode insert(Key k, Value v, BSTNode n){
if(n == null){
return new BSTNode(k, v);
}
int comp = n.getKey().compareTo(k);
// insert 재귀는 두 가지 케이스를 반환함.
// case1. 서브트리 탐색 끝에 Null일 경우에는 새로운 노드 반환
// case2. 서브트리 탐색 시 노드가 존재할 경우 기존 노드 반환
if(comp == 0){ // 같은 키값의 노드 -> Value만 갱신(Key 중복 허용 X)
n.setValue(v);
}
else if(comp > 0){ // 현재 노드보다 키값이 작은 경우 -> case1) 왼쪽에 삽입 or case2) 기존 left 노드를 setLeft(변화 없음)
n.setLeft(insert(k, v, n.getLeft()));
}
else{ // 현재 노드보다 키값이 큰 경우 -> 오른쪽 서브트리에 삽입 -> case1) 오른쪽에 삽입 or case2) 기존 right 노드를 setRight(변화 없음)
n.setRight(insert(k, v, n.getRight()));
}
return n;
}
public BSTNode getMin(){
if(this.root == null){
return null;
}
return getMin(this.root);
}
private BSTNode getMin(BSTNode n){
if(n.getLeft() == null){
return n; //Left 존재하지 않으면 최소값
}
return getMin(n.getLeft()); //최소값 나올때까지 left로 이동하며 재귀호출
}
public BSTNode getMax(){
if(this.root == null){
return null;
}
return getMax(this.root);
}
private BSTNode getMax(BSTNode n){
if(n.getRight() == null){
return n; //Right가 존재하지 않으면 최대값
}
return getMax(n.getRight()); //최대값 나올때까지 right로 이동하며 재귀호출
}
public void deleteMin(){
this.root = deleteMin(this.root);
}
private BSTNode deleteMin(BSTNode n){
if(n.getLeft() == null){
return n.getRight(); //Left 존재하지 않으면 최소값
}
n.setLeft(deleteMin(n.getLeft())); //최소값 나올 때 까지 Left로 이동
return n;
}
public void delete(Key k){
this.root = delete(k, this.root);
}
private BSTNode delete(Key k, BSTNode n){
if(n == null){
return null;
}
int comp = n.getKey().compareTo(k);
if(comp > 0){ // 현재 노드보다 키값이 작은 경우 -> 왼쪽 서브트리로 이동하며 delete() 재귀호출
n.setLeft(delete(k, n.getLeft()));
}
else if(comp < 0){ // 현재 노드보다 키값이 큰 경우 -> 오른쪽 서브트리로 이동하며 delete() 재귀호출
n.setRight(delete(k, n.getRight()));
}
else{ // 삭제할 노드 발견
if(n.getRight() == null){ //오른쪽 서브트리가 없는 경우 : 왼쪽 서브트리를 현재 노드의 위치로 연결
return n.getLeft();
}
if(n.getLeft() == null){ //왼쪽 서브트리가 없는 경우 : 오른쪽 서브트리를 현재 노드의 위치로 연결
return n.getRight();
}
BSTNode targetNode = n; // 삭제 대상 노드를 targetNode로 설정
n = getMin(targetNode.getRight()); // 대체 : 삭제 대상의 오른쪽 서브트리의 최소값 노드를 삭제 위치로 이동
n.setRight(deleteMin(targetNode.getRight())); // 대체 노드의 right : 삭제 대상의 right 서브트리로 설정 + 이동된 노드는 제거
n.setLeft(targetNode.getLeft()); // 대체 노드의 left : 삭제 대상의 left 서브트리로 설정
}
return n;
}
}
public class C02_BinarySearchTree {
static BinarySearchTree makeBinarySearchTree(Integer lastKey){
BinarySearchTree<Integer, String> t = new BinarySearchTree<>();
t.insert(600, "Frog");
t.insert(400, "Dog");
t.insert(300, "Carrot");
t.insert(100, "Apple");
t.insert(200, "Banana");
t.insert(700, "Grape");
t.insert(500, "Elephant");
t.insert(lastKey, "Lemon");
return t;
}
public static void main(String[] args) {
BinarySearchTree t = makeBinarySearchTree(800);
System.out.print("Preorder : ");
t.preorder();
System.out.println();
System.out.print("Inorder : ");
t.inorder();
System.out.println();
System.out.print("Postorder : ");
t.postorder();
System.out.println();
System.out.print("Levelorder : ");
t.levelorder();
System.out.println();
System.out.println("Height : " + t.getHeight());
System.out.println("Size : " + t.getSize());
BinarySearchTree t2 = makeBinarySearchTree(800);
System.out.println("isEqual : " + t.isEqual(t2));
BinarySearchTree t3 = makeBinarySearchTree(700);
System.out.println("isEqual : " + t.isEqual(t3));
System.out.println("Search 300 : " + t.search(300).getValue());
System.out.println("Search 900 : " + t.search(900));
System.out.println("Search getMin : " + t.getMin().getKey());
System.out.println("Search getMax : " + t.getMax().getKey());
System.out.println("Delete 400");
t.delete(400);
System.out.print("Inorder : ");
t.inorder();
System.out.println();
System.out.print("Inorder : ");
t.inorder();
System.out.println();
System.out.println("Delete min");
t.deleteMin();
System.out.print("Inorder : ");
t.inorder();
System.out.println();
}
}Preorder : 600 400 300 100 200 500 700 800
Inorder : 100 200 300 400 500 600 700 800
Postorder : 200 100 300 500 400 800 700 600
Levelorder : 600 400 700 300 500 800 100 200
Height : 5
Size : 8
isEqual : true
isEqual : false
Search 300 : Carrot
Search 900 : null
Search getMin : 100
Search getMax : 800
Delete 400
Inorder : 100 200 300 500 600 700 800
Inorder : 100 200 300 500 600 700 800
Delete min
Inorder : 200 300 500 600 700 800
이진 탐색 트리의 시간 복잡도
완전 이진 트리와 편향 이진 트리
- 완전 이진 트리: 모든 레벨이 완전히 채워진 이진 트리. 트리의 높이는 log N
- 편향 이진 트리: 한쪽 방향으로만 연결된 노드가 많은 트리. 이 경우 트리의 높이는 N
최악의 경우
시간 복잡도 : O(h) (h는 트리의 높이)
트리가 완전히 편향된 경우, 즉 모든 노드가 한쪽 방향으로만 연결되어 있는 경우
삽입 또는 삭제하려는 값이 항상 트리의 가장 깊은 레벨에 위치하는 경우
이러한 경우에는 트리의 모든 노드를 방문해야 하기 때문에 h에 비례하게 된다.
평균적인 경우
시간 복잡도 : O(log N)
트리가 균형 잡힌 경우 -> 즉 모든 노드의 왼쪽과 오른쪽 서브트리가 비슷한 크기인 경우
따라서 트리가 균형 잡혀 있으면, 트리의 높이는 log N에 비례하고, 이가 곧 시간 복잡도가 된다.
따라서, 완전 이진 트리는 평균적인 경우 연산 시간이 O(log N)이고, 편향 이진 트리는 최악의 경우 연산 시간이 O(N)
일반적인 경우
실제 사용되는 이진 검색 트리는 완전 이진 트리도 아니고 편향 이진 트리도 아닐 확률이 높다.
일반적으로 트리의 높이는 log N과 N 사이의 값을 가진다.
따라서 시간 복잡도는 O(log N) ~ O(N)이며, 평균적으로 1.39(logN)이라고 한다.
AVL 트리
트리가 편향될 경우, 연산의 시간 복잡도가 O(N)으로 악화될 수 있다. AVL 트리는 이러한 문제를 해결하기 위해 개발된 이진탐색 트리이다.
해당 트리는 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 최대 1을 유지하도록 한다. 따라서\ 트리가 편향되는 것을 방지하고, 모든 연산의 시간 복잡도를 O(log N)으로 유지할 수 있다.
다음 포스팅에서는 AVL 트리에 대해서 다루어 보려고 한다.
'PS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조/JAVA] 우선순위 큐 : 힙(Heap) (0) | 2024.03.28 |
|---|---|
| [자료구조/JAVA] 트리 (3) : AVL 균형 트리 (AVL Tree) (0) | 2024.03.25 |
| [자료구조/JAVA] 트리 (1) : 이진 트리(Binary Tree) : 순회 및 연산 (0) | 2024.03.19 |
| [자료구조/JAVA] 연결 리스트(Linked List) (0) | 2024.03.13 |
| [자료구조/JAVA] 동적 배열(Dynamic Array) 구현 (1) | 2024.03.12 |
