이진탐색트리2 이진 탐색 트리 (BST-Binary Search Tree) 이진 탐색 트리란? 이진탐색트리(Binary Search Tree; BST)는 정렬된 tree이다. 어느 노드를 선택하든 해당 노드의 왼쪽 서브 트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로만 이루어져 있고, 오른쪽 서브 트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로만 이루어져 있는 이진 트리이다. 서브 트리도 재귀적으로 이러한 조건을 만족한다. 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 특징 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리.. 2023. 8. 10. 여러 종류의 트리(Tree) 정리 (이진 트리, 전 이진 트리, 완전 이진 트리, 포화 이진 트리, 이진 탐색 트리) 트리의 개념 - 노드로 이루어진 자료구조로 스택이나 큐 같은 선형 구조가 아닌 비선형 자료구조이다. - 계층적 관계를 표현하는 자료구조이다. 트리의 특성 - 하나의 루트 노드를 갖는다. - 루트 노드는 0개 이상의 자식 노드를 갖는다. - 자식 노드 또한 0개 이상의 자식 노드를 갖는다. - 노드들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다. - 사이클(Cycle)이 존재할 수 없다. 트리는 사이클이 없는 하나의 연결 그래프라고 할 수 있다. ★사이클이란? 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있는 구조를 말함한다. - 트리의 노드는 self-loop가 존재해서는 안된다. - N개의 노드를 갖는 트리는 항상 N-1개의 간선을 갖는다. - 모든 자식 노드는 한 개의.. 2023. 8. 9. 이전 1 다음
