이진 트리

트리

- 트리에는 가장 상위 노드를 루트라 부른다. 여기선 2가 루트다

- 90은 50, 150의 부모고 반대로 50, 150은 90의 자식이다.

- 트리는 레벨이 있다. 여기선 4 레벨이다 (맨위가 1 레벨)

 

 

 

이진 트리(+트리 특징)

- 각 노드의 작식은 0개나 1개, 2개다.

- 한 노드에 자식이 둘이면 한자식은 부모보다 작은 값을, 다른 자식은 부모보다 큰 값을 가져야한다.

 

검색

- 111을 찾는다고 가정하고 두 자식중 부모가 111보다 큰지 작은지 비교 후 조건에 맞는 자식에게 타고 들어가면서 찾고자하는 값을 찾는다. (여기선 111이 부모 90보다 크다 고로 우측 150으로 타고옴)

- 이진 트리 검색은 O(log N) 단계이다.

 

삽입

- 100을 삽입한다고 가정하면 먼저 루트90부터 큰지 작은지 비교한다.(여기선 90보다 크므로 우측트리로)

- 트리를 타고오면 결국 111 자식에 100이 삽입된다.

- 결국 검색 log N 단계 + 삽입 1단계 가 걸린다.

- 정렬된 배열에선 검색뿐 아니라 삽입할 공간마련할때 우측으로 그 공간만큼 시프트하므로 O(N)이 걸린다. 그래서 이진트리가 삽입에서는 더 효율적이다.

 

삭제

- 삭제할 노드에 자식이 없다면 그냥 삭제한다.

- 삭제할 노드에 자식이 하나면 노드삭제후, 그 자식을 삭제된 노드 위치에 넣는다.

- 자식이 둘인 노드를 삭제할 때는 삭제된 노드를 후속자 노드로 대체한다.

(후속자 노드란 삭제된 노드보다 큰 값중 최솟값을 갖는 자식 노드다.)

- 만약 후속자 노드에 오른쪽 자식이 있으면 후속자를 삭제된 노드가 있던 자리에 넣은 후, 후속자 노드의 오른쪽 자식을 후속자 노드의 원래 부모의 왼쪽 자식으로 넣는다.

- 삭제도 일반적으로 O(log N)단계이다.

 

 

만약 92 우측 자식노드가 91일 경우 91을 92있던 자리에 대체