반응형 이진 탐색 트리2 [Data-Structure] Tree (트리)와 Binary Search Tree (이진 탐색 트리) (2)Binary Search Tree (이진 탐색 트리) 란 지난번 글에 이어서 이번에는 Binary Search Tree (BST, 이진 탐색 트리) 에 대해서 알아보았다. 이진 탐색 트리는 최대 2개의 자식만 갖는 트리이다. 트리 구조는 재귀적이므로, 자식 노드 역시 최대 2개의 자식을 갖는다. 이진 탐색 트리에서는 노드의 값이 정렬 방법에 따라 순서가 존재하는데 노드의 왼쪽 서브 트리에는 노드의 값보다 작은 값이, 오른쪽 서브 트리에는 노드의 값보다 같거나 큰 값이 존재하게 된다. 이진 탐색 트리는 트리 자료구조를 활용한 자료구조로 데이터 탐색 속도를 높일 때 사용한다. 이진 탐색 트리가 주어졌을 때, 세가지 방법으로 순회가 가능하다. 전위 순회(Preorder Traversal): 부모 → 좌 → 우 중위 순회(Inorder Traversal): 좌 → 부.. 2020. 10. 26. [Data-Structure] Tree (트리)와 Binary Search Tree (이진 탐색 트리) (1)Tree 구조란 오늘은 트리 구조(Tree)와 이진 탐색 트리(Binary Search Tree)에 대해서 공부해보았다. 트리 구조란 노드로 구성된 계층적 자료구조이다. 최상위 노드(루트)를 만들고, 루트 노드의 child를 추가하고, 그 child에 또 child를 추가하는 방식으로 트리 구조를 구현할 수 있다. 트리 구조와 관련하여 반드시 알아야 할 개념들이다. [정보통신기술용어해설] 참조 A, B, C, D 등 트리의 구성요소를 노드(node) 라고 한다. 위 그림의 A처럼, 트리 구조에서 최상위에 존재하는 노드를 root이다. 루트를 기준으로, 다른 노드로의 접근하기 위한 거리를 depth 라고 한다. 같은 부모를 가지면서 같은 depth에 존재하는 노드들은 sibling 관계에 있습니다. (같은 부모를 가진 노.. 2020. 10. 26. 이전 1 다음 반응형
