이진탐색트리 (Binary Search Tree)

데이터의 탐색 속도 증진을 위해 사용하는 구조

트리의 용어

• 내부노드(indernal node) : 1개 이상의 자식을 가진 노드
• 외부노드 (external node) 또는 리프(leaf) : 자식이 하나도 없는 노드
• 서브트리(subtree) : 노드와 후손으로 구성된다.
• 깊이(depth) : 조상의 개수 / 그림에서 노드 H의 깊이는 3개의 조상을 갖고 있으므로 3이다.
• 높이(height) 또는 레벨(level) : 깊이의 최대치 / 루트는 레벨 0, 그 하위 자식은 레벨 1, 이런식이다. 그림 속의 트리 높이는 3이다.
• 간선 (edge) : 노드를 연결하는 선. link,branch 라고도 한다

이진트리와 이진탐색트리

이진트리(binary tree) : 노드는 좌, 우측에 각각 하나씩 최대 2개의 자식 노드를 갖는다. 즉 노드의 삽입, 조회, 삭제를 효과적으로 수행할 수 있어서 컴퓨터 과학에서 폭넓게 활용된다.

이진탐색트리(vinary search tree) : 이진 트리의 변형으로, 좌측 자식 노드에는 더 작은 값을, 우측 자식노드에는 더 큰 값을 들고 있다는 차이점이 있다.

데이터 탐색방법

전위 순회 (Preorder Traversal)

한 서버에서 트리의 구조를 그대로 다른 서버로 보내고 싶을 때 사용

1. 자기 자신을 처리
2. 왼쪽 자식 노드를 방문
3. 오른쪽 자식 노드를 방문

중위 순회 (Inorder Traversal)

트리를 정렬 할 때 사용

1. 왼쪽 자식 노드를 방문
2. 자기 자신을 처리
3. 오른쪽 자식 노드를 방문

후위 순회 (Postorder Traversal)

트리를 지울 때 사용 노드를 하나씩 지워야 할 때 손자 노드를 할아버지 노드에 재연결할 필요가 없어서 퍼포먼스가 좋다.

1. 왼쪽 자식 노드를 방문
2. 오른쪽 자식 노드를 방문
3. 자기 자신을 처리

단점

BST는 노드 개수에 따라 한쪽으로 깊게 치우쳐 간선이 길게 늘어질 수 있는 단점이 있다. 즉 레벨이 높은 가지와 레벨이 낮은 가지가 공존하는 트리가 만들어질 수 있다.

이런 형태 트리는 노드 추가/삭제 및 조회 시 간선에 따라 성능 문제가 발생할 수 있다.

그래서 AVL트리라는 대안이 만들어졌다.

AVL트리

스스로 균형을 잡는 BST트리의 일종으로 어떤 노드의 좌/우측 서브트리의 높이도 1이상 차이 나지 않도록 조정한다.

노드 삽입 방법

insert

1. 루트의 값이 없다면

   1-1 노드는 루트이다.

2. 루트의 값이 있다면

    2-1 노드삽입 메서드를 호출한다.

insertNode

 1. 새로운 노드보다 루트 노드가 크면

     1-1. 루트노드의 왼쪽 자식의 값이 없다면

       1-1-1. 새로운 노드는 왼쪽 자식노드가 된다.

     1-2. 루트 노드의 왼쪽 자식의 값이 있다면

      1-2-1. 왼쪽자식노드와 새로운노드로 다시 insertNode를 실행한다.

2. 새로운 노드보다 루트 노드가 작으면

         1-1. 루트노드의 오른쪽 자식의 값이 없다면

           1-1-1. 새로운 노드는 오른쪽 자식노드가 된다.

         1-2. 루트 노드의 오른쪽 자식의 값이 있다면

            1-2-1. 오른쪽자식노드와 새로운노드로 다시 insertNode를 실행한다.

노드 삭제 방법

remove

1. 루트값을 removeNode의 반환값으로 바꾼다. (루트 포인터 값을 바꾼다)

removeNode

1.  지울 노드가 존재하지 않으면 종료한다.

2.  지울 노드가 현재 노드보다 작으면

    2-1. 현재 노드의 왼쪽자식 노드의 값을 removeNode의 반환값으로 바꾼다. (왼쪽자식 노드의 포인터 값을 바꾼다.)

    2-2. 현재 노드를 반환한다.

3.  지울 노드가 현재 노드보다 크면

    3-1. 현재 노드의 오른쪽자식 노드의 값을 removeNode의 반환값으로 바꾼다. (오른쪽자식 노드의 포인터 값을 바꾼다.)

    3-2. 현재 노드를 반환한다.

4.  2,3조건에 포함하지 않으면 (지울 노드를 찾았으면)

    4-1. 왼쪽자식 노드와 오른쪽 자식노드가 모두 없으면

        4-1-1. 현재 노드를 지운다.

        4-1-2. 현재 노드를 반환한다

    4-2. 왼쪽자식 노드만 없으면

        4-2-1. 현재 노드를 오른쪽 노드로 바꾼다.

        4-2-2. 현재 노드를 반환한다.

    4-3. 오른쪽자식 노드만 없으면

        4-3-1. 현재 노드를 왼쪽 노드로 바꾼다.

        4-3-2. 현재 노드를 반환한다.

    4-4. 자식노드가 둘다 있으면

        4-4-1. 오른쪽 서브트리로부터 최소값을 찾는다.

        4-4-2. 현재 노드의 키값을 찾은 최소값으로 바꾼다.

        4-4-3. 오른쪽 서브트리를 시작으로 최소값을 지운뒤 현재
        노드의 오른쪽 포인터 값을 차례대로 수정한다.

        4-4-4. 현재 노드를 반환한다.

코드

github/binarySearchTree