이진 탐색 트리의 편향 발생(불균형 이진트리) Case 1) 이진 탐색 트리에 삽입되는 순서 : 20 → 10 → 30 → 5 Case 2) 이진 탐색 트리에 삽입되는 순서 : 5 → 10 → 20 → 30 균형 이진 탐색 트리 Balanced Binary Search Tree 노드의 삽입과 삭제가 일어날 때 균형을 유지하도록 하는 트리 AVL 트리, Red-Black 트리 AVL 트리 노드가 삽입, 삭제될 떄 트리의 균형을 체크하고 유지하는 트리 각 노드의 BF를 [-1, 0, 1] 만 가지게 하여 균형을 유지 BF(Balance Factor) # 왼쪽 서브 트리 높이 - 오른쪽 서브 트리 높이 AVL 트리 - Rebalancing 균형이 꺠진 경우, BF가 ' + ' 이면 왼쪽 서브 트리에 이상이 있..

이진 탐색 트리(Binary Search Tree) - 왼쪽 자식 노드의 키는 부모 노드의 키보다 작음 - 오른쪽 자식 노드의 키는 부모 노드의 키보다 큼 - 각각의 서브 트리도 이진 탐색 트리를 유지 - 중복된 키는 허용하지 않음 - 이진 탐색 트리 규칙에 의해 데이터가 정렬됨 - 이진 트리에 비해 탐색 빠름(균형 유지 필요) - 균형 상태 : O(logN) - 불균형 상태 : O(N) 이진 탐색 트리 - 탐색 찾고자 하는 데이터를 루트 노드부터 비교시작 대소 비교를 하여 찾는 데이터가 작으면 왼쪽, 크면 오른쪽 노드로 이동 찾는 데이터가 없으면 null 반환 어떤 데이터를 찾더라도 최대 트리 높이 만큼의 탐색이 이루어짐 이진 탐색 트리 - 삽입 Root부터 비교 시작(중복 키 발견 시 노드 추가하지 ..

트리(Tree) 노드와 링크로 구성되 자료구조(그래프의 일종, Cycle 없음) 계층적 구조를 나타낼 때 사용 - 폴더 구조(디렉토리, 서브 디렉토리) - 조직도, 가계도, ... 트리의 구조 노드(Node) : 트리 구조의 자료 값을 담고 있는 단위 에지(Edge) : 노드 간의 연결선 (=link, branch) 루트 노드(Root) : 부모가 없는 노드, 가장 위의 노드 잎새 노드(Leaf) : 자식이 없는 노드 (=단말) 내부 노드(Internal) : 잎새 노드를 제외한 모든 노드 부모(Parent) : 연결된 두 노드 중 상위의 노드 자식(Child) : 연결된 두 노드 중 하위의 노드 형제(Silbing) : 같은 부모를 가지는 노드 깊이(Depth) : 루트에서 어떤 노드까지의 간선의 수 ..