본문 바로가기

Data structure11

CS 자료구조 Binary Search Tree(이진 탐색 트리) 이진 탐색 트리(BST)는 각 노드가 최대 두 개의 자식을 가지는 이진 트리의 특수한 형태로, 데이터의 정렬과 효율적인 검색을 목적으로 설계된 자료 구조다. 노드에 저장된 데이터를 기준으로 왼쪽 서브트리와 오른쪽 서브트리가 특정 조건을 만족하도록 설계되어 있다. ㅇ  이진 탐색 트리의 특징왼쪽 서브트리의 모든 노드는 부모 노드보다 작은 값을 가진다.오른쪽 서브트리의 모든 노드는 부모 노드보다 큰 값을 가진다. ㅇ 이진 탐색 트리의 주요 연산탐색(Search)이진 탐색 트리에서 특정 값을 찾을 때 트리의 루트에서부터 시작한다.찾고자 하는 값이 현재 노드의 값보다 작으면 왼쪽 트리로 이동한다.크면 오른쪽 트리로 이동한다.원하는 값을 찾거나 탐색할 노드가 없으면 종료한다.시간복잡도: 평균적으로 O(log n).. 2024. 10. 8.
CS 자료구조 Tree(트리) 트리는 계층적인 데이터를 표현하는 비선형 데이터 구조다. 나무를 거꾸로 뒤집어 놓은 모양과 유사하다. 트리는 트리 내에 다른 하위 트리가 있고, 하위 트리 안에 또 다른 하위 트리가 있는 재귀적 자료구조다. 컴퓨터의 디렉토리 구조가 트리의 대표적인 예가 될 수 있다. ㅇ 트리의 기본 용어 노드(Node)트리를 구성하고 있는 기본 요소노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음A, B, C, D, E, F, G, H, I, J 간선(Edge)노드와 노드 간의 연결 선 루트 노드(Root Node)트리 구조에서 부모가 없는 최상위 노드A 부모 노드(Parent Node)자식 노드를 가진 노드H, I의 부모 노드 D 자식 노드(Child Node)부모 노드의 하위 노드D의 자식 노드 H, I.. 2024. 10. 8.

티스토리툴바