트리

트리 개념 

 

트리는 노드 기반 자료구조이며 각 노드는 여러 노드로의 링크를 포함할 수 있다. 

• 가장 상위 노드를 '루트' 라고 한다.
• 트리는 부모 - 자식 관계이다. 
• 트리에는 자손과 조상 개념이 있다. 한 노드의 자손은 그 노드에서 생긴 모든 노드를 말하고 한 노드의 조상은 그 노드를 생겨나게 한 모든 노드이다. 
• 트리에서의 레벨은 줄을 말하며 루트는 첫 번째 레벨 루트의 자식 노드는 두 번째 레벨에 위치한다. 다음 자식 노드는 세 번째 레벨에 위치하며 이러한 방식으로 레벨이 늘어난다. 
• 균형 트리는 하위 트리의 노드의 개수가 같은 것을 말한다.
• 컬렉션으로 TreeSet이 있다.

 

이진 탐색 트리 

• 자식이 0개나 1개 또는 2개다.
• 노드의 자식은 노드의 값보다 작을 경우 왼쪽에 위치, 클 경우 오른쪽에 위치하고 왼쪽, 오른쪽 각각 최대 1개의 자식만이 유효하다.
• 균형 트리일 시 레벨을 추가할 때마다 트리 크기는 2배가 된다. 
• 검색(범위검색)과 정렬에 유리하다.
• 중복된 값을 저장하지 못한다.
• TreeSet은 이미 저장할 때 정렬되어있어 읽을 시 따로 정렬할 필요 없다.

 

이진 탐색 트리 검색 

 

각 단계마다 해당 노드의 값보다 작으면 왼쪽, 크면 오른 쪽으로 이동 하기때문에 탐색할 노드의 예상 개수가 최대 반으로 줄어든다. 때문에 시간복잡도는 O(logN)이다.

 

TreeSet은 subSet()을 이용해 범위검색하는데 시작범위는 포함되지만 끝 범위는 포함되지않는다.

 ex) set.subSet(a,d) 이면 a부터 c까지의 결과가 나온다.

대문자를 소문자보다 우선한다. 예상과 다른 결과가 나올 수 있으므로 가능하면 대소문자를 통일하는 것이 좋다. 

 

headSet()과 tailSet()은 저장된 객체 중 지정된 값보다 큰 값 객체들과 작은 값 객체들을 구할 수 있다.

 

 

이진 탐색 트리 삽입

• 이진 탐색 트리는 삽입에서 가장 효율적이다.
• 정렬된 배열 : 검색 + 삽입을 위한 자리 마련을 위한 데이터 이동 >>> O(N)
• 이진 탐색 트리 :  검색 + 삽입 1단계 >>> O(logN)
• 따라서 데이터 변경이 많을 시 이진 탐색 트리를 사용하는 것이 정렬된 배열을 사용하는 것보다 효율적이다.
• 정렬된 배열은 이진 탐색 트리로 변경 시 무작위 배열로 변경 후 적용시키는 것이 좋다. >>> 가운데 값이 루트값이 되는것이 가장 좋기 때문

범위 검색 시 

 

 

이진 탐색 트리 삭제

1. 삭제할 노드에 자식이 없다면 그냥 삭제한다.
2. 삭제할 노드에 자식이 하나면 삭제한 노드 자리에 자식 노드를 넣는다.
3. 삭제할 노드에 자식이 둘이면 삭제한 노드 자리에 후속자 노드( 처음 오른쪽 자식 이후 바닥까지 왼쪽 자식 즉 삭제된 노드값보다 큰 값 중 최소값 )로 대체 한다. 
4. 만약 후속자 노드에 오른쪽 자식이 있다면 원래 후속자노드의 부모의 왼쪽 자식 노드 자리로 오른쪽 자식의 위치를 변경한다.