데이터의 탐색 속도 증진을 위해 사용하는 구조
- 내부노드(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) : 이진 트리의 변형으로, 좌측 자식 노드에는 더 작은 값을, 우측 자식노드에는 더 큰 값을 들고 있다는 차이점이 있다.
한 서버에서 트리의 구조를 그대로 다른 서버로 보내고 싶을 때 사용
- 자기 자신을 처리
- 왼쪽 자식 노드를 방문
- 오른쪽 자식 노드를 방문
트리를 정렬 할 때 사용
- 왼쪽 자식 노드를 방문
- 자기 자신을 처리
- 오른쪽 자식 노드를 방문
트리를 지울 때 사용 노드를 하나씩 지워야 할 때 손자 노드를 할아버지 노드에 재연결할 필요가 없어서 퍼포먼스가 좋다.
- 왼쪽 자식 노드를 방문
- 오른쪽 자식 노드를 방문
- 자기 자신을 처리
BST는 노드 개수에 따라 한쪽으로 깊게 치우쳐 간선이 길게 늘어질 수 있는 단점이 있다. 즉 레벨이 높은 가지와 레벨이 낮은 가지가 공존하는 트리가 만들어질 수 있다.
이런 형태 트리는 노드 추가/삭제 및 조회 시 간선에 따라 성능 문제가 발생할 수 있다.
그래서 AVL트리라는 대안이 만들어졌다.
스스로 균형을 잡는 BST트리의 일종으로 어떤 노드의 좌/우측 서브트리의 높이도 1이상 차이 나지 않도록 조정한다.
1. 루트의 값이 없다면
1-1 노드는 루트이다.
2. 루트의 값이 있다면
2-1 노드삽입 메서드를 호출한다.
1. 새로운 노드보다 루트 노드가 크면
1-1. 루트노드의 왼쪽 자식의 값이 없다면
1-1-1. 새로운 노드는 왼쪽 자식노드가 된다.
1-2. 루트 노드의 왼쪽 자식의 값이 있다면
1-2-1. 왼쪽자식노드와 새로운노드로 다시 insertNode를 실행한다.
2. 새로운 노드보다 루트 노드가 작으면
1-1. 루트노드의 오른쪽 자식의 값이 없다면
1-1-1. 새로운 노드는 오른쪽 자식노드가 된다.
1-2. 루트 노드의 오른쪽 자식의 값이 있다면
1-2-1. 오른쪽자식노드와 새로운노드로 다시 insertNode를 실행한다.
1. 루트값을 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. 현재 노드를 반환한다.