BST (Binary_Search_Tree) - sihyun10/data_structures_docker GitHub Wiki

BST란? (Binary Search Tree)

모든 원소는 유일한 key 값을 갖는다 (중복 없음)

왼쪽 서브 트리의 모든 원소들은 루트(root)의 키보다 작은 값을 갖는다
오른쪽 서브 트리의 모든 원소들은 루트(root)의 키보다 큰 값을 갖는다
즉 왼쪽 서브트리 < 루트 < 오른쪽 서브트리 순서이다.

왼쪽 서브트리, 오른쪽 서브트리 둘 다 이진 탐색트리이다

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

BST의 특징

• 중위 순회(Inorder Traversal)를 수행하면 정렬(오름차순)된 값이 나온다
• [시간복잡도] 균형 상태 : O(logN), 불균형 상태 : 최대 O(N)

---

BST 구조체

// 이진 탐색 트리 노드 1개를 나타내는 구조
typedef struct _bstnode {
  int item;
  struct _bstnode *left;
  struct _bstnode *right;
} BSTNode; 

• item : 이 노드가 가지는 정수 데이터
• left : 왼쪽 자식 노드의 주소
• right : 오른쪽 자식 노드의 주소

Q. 왜 left, right는 자기참조(self-reference) 구조체일까?

이진트리에서 노드가 다른 노드를 가리켜야 하는데, 왜 자기 자신을 가리키는 포인터를 써야하는지 궁금했다.

트리는 노드들끼리 연결되어 계층 구조를 만들어야한다.

// 10은 루트(root) 노드  
// 10의 왼쪽 자식 : 5 (root->left = 주소_5)
// 10의 오른쪽 자식 : 15 (root->right = 주소_15)

      10
     /  \
    5   15

노드끼리 서로 주소로 연결되어야 트리 구조를 형성할 수 있다.

트리 구조는 재귀적인 구조이다.

        10
       /  
      5

5를 혼자 보면 "루트 노드"가 될 수 있다

트리는 이렇게 작은 트리들이 계속 연결된 구조이기 때문에, 자식들도 똑같이 BST Node니까 "각 노드가 자신의 자식 노드를 가리켜야한다"
그래서 자기 자신을 참조하는 포인터를 사용해 자식 노드를 연결한다

즉 정리하자면
left, right는 자식 노드와 연결하는 통로이며,
그걸 통해 노드끼리 연결되어 트리 구조가 만들어지는 것이다.