자가균형 이진탐색트리2 RB(Red-Black) 트리 - 성질/삽입방법/활용 탄생 계기 이진탐색트리는 위 그림과 같이 한쪽으로 노드가 쏠릴 수가 있는 문제점이 있다. 10,9,8,7,6을 순서대로 삽입한다고 생각해보면 저런 형태의 트리가 만들어진다는 것을 알 수 있을 것이다. 이런 트리를 편향 트리라 하는데 이러한 형태에서 특정 값을 찾으려면 O(N)의 시간이 필요하다. 예를 들어 6을 찾으려면 모든 노드를 탐색해야지 찾을 수 있다. 따라서 성능이 매우 나빠지게 된다. 이진 탐색 트리 (BST-Binary Search Tree) 이진 탐색 트리란? 이진탐색트리(Binary Search Tree; BST)는 정렬된 tree이다. 어느 노드를 선택하든 해당 노드의 왼쪽 서브 트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로만 이루어져 있고, 오 hyolls100.tistory.c.. 2023. 8. 11. 이진 탐색 트리 (BST-Binary Search Tree) 이진 탐색 트리란? 이진탐색트리(Binary Search Tree; BST)는 정렬된 tree이다. 어느 노드를 선택하든 해당 노드의 왼쪽 서브 트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로만 이루어져 있고, 오른쪽 서브 트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로만 이루어져 있는 이진 트리이다. 서브 트리도 재귀적으로 이러한 조건을 만족한다. 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 특징 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리.. 2023. 8. 10. 이전 1 다음
