트리(Tree)

1. 트리(Tree) 구조

• 트리 : Node와 Branch를 이용하여, 사이클(순환)을 이루지 않도록 구성한 데이터 구조
• 이진트리의 형태의 구조로, 탐색 알고리즘 구현에서 많이 사용됨

이진 트리

트리 구조 중 가장 많이 쓰이는 형태는 이진트리이다.
트리라고 해서 무조건 이진트리는 아닌 것을 기억하자.

2. 용어

• Node : 트리에서 데이터를 저장하는 기본 요소
• Root Node : 트리에서 최상단에 있는 노드
• Level: 트리의 깊이를 나타냄. 0 또는 1부터 시작
• Parent Node : 어떤 노드의 상위 노드
• Child Node : 어떤 노드의 하위 노드
• Leaf Node : Child Node가 하나도 없는 노드
• Depth : 트리에서 Node가 가질 수 있는 최대 Level
  
  

3. 이진트리와 이진 탐색 트리(Binary Search Tree)

• 이진 트리 : 노드의 최대 Branch가 2인 트리
• 이진 탐색 트리 : 이진 트리에 다음과 같은 규칙으로 노드를 저장하는 트리
  왼쪽 노드에는 해당 노드보다 작은 값, 오른쪽 노드에는 해당 노드 보다 큰 값

출처 :https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node

이진 탐색 트리는 데이터 검색하는데 주로 이용되며, 검색 속도를 향상할 수 있다!

 

이진트리 vs 배열의 데이터 검색 비교

출처 :https://blog.penjee.com/5-gifs-to-understand-binary-search-tree/#binary-search-tree-insertion-node

 

이진 탐색의 데이터 추가

현재 노드 값보다 작으면 왼쪽, 크면 오른쪽에 삽입

 

이진 탐색의 데이터 삭제

이진트리에서의 데이터 삭제는 다양한 경우가 존재하기 때문에 경우의 수를 나눠서 생각해 보도록 하겠습니다.

 

1. Leaf Node 삭제

삭제할 Node와 Parnent Node와의 연결을 삭제하고, Node를 삭제합니다.

 

90을 제거할 경우

 

 

2. Chide Node 가 하나인 Node 삭제

삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 바라보게 한다.

 

80을 제거할 경우

 

3. Child Node 가 두 개인 Node 삭제

1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 선택한다.
   이 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 합니다.

 

30을 제거할 경우

 

2. 삭제할 Node의 왼쪽 자식 중 가장 큰 값을 선택한다.

    이 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 합니다.

 

30을 제거할 경우

 

 

이진 탐색 트리의 시간 복잡도

이진 탐색 트리의 시간 복잡도는 O(logn) 입니다

=> 한번 실행시마다 50%의 확률로 node를 찾아가기 때문에 50%의 실행시간을 단축시킬 수 있는다는 것을 의미

※빅오 표기법의 log의 밑은 10이 아니라 2입니다.

 

이진 탐색 트리의 단점

이진 탐색 트리의 평균 시간 복잡도는 O(logn)이지만, 한쪽으로 편향된 모습의 이진 탐색 트리의 모습을 가진다면 O(n)의 시간 복잡도를 가질 수 있습니다.