균형 이진 탐색 트리 : AVL 트리와 회전 연산 - C 언어
·
C
AVL 트리 (Adelson-Velskii & Landis Tree) : 대표적인 균형 이진 탐색 트리각 노드에서 왼쪽 서브 트리의 높이(hL : height of left subtree)와 오른쪽 서브 트리의 높이(hR : height of right subtree)의 차이가 1 이하인 트리 특징- 왼쪽 서브 트리 - 각 노드의 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이 (hL - hR)를 노드의 균형 인수(BF, balance factor)라고 함- 각 노드의 균형 인수로 {-1, 0, +1} 값만 가지게 함으로써 균형을 유지함  루트 노드 50을 기준으로 왼쪽 서브 트리의 높이는 2, 오른쪽 서브 트리의 높이는 3이므로 BF = hL-hR = -1이 된다.위와 같은 방식으로 그림 속 노드..
이진 탐색 트리의 탐색/삽입/삭제 연산 - C언어
·
C
https://tildacoderecorder.tistory.com/104이진 트리에 대한 개념 설명은 아래 글 참조 👇🏻 [ 자료구조 ] 트리와 이진트리의 개념과 구조 - C언어트리 : 원소들 간에 1:n 관계를 가지는 비선형 자료구조, 원소들 간에 계층 관계를 가지는 계층형 자료구조, 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조 트리는 하나tildacoderecorder.tistory.com 이진 탐색 트리 Binary search Tree: 이진 트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정한 것모든 원소는 서로 다른 유일한 키를 갖는다.왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다.오른쪽 서브 트리에 있는 원소들의 키는 그 루..
트리와 이진트리의 개념과 구조 - C언어
·
C
트리 Tree트리 : 원소들 간에 1:n 관계를 가지는 비선형 자료구조, 원소들 간에 계층 관계를 가지는 계층형 자료구조, 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무) 모양의 구조트리는 하나의 루트 노드를 가지며 각 자식 노드와 부모 노드는 간선(edge)로 연결되어 있다. 트리의 이해차수노드의 차수 : 노드에 연결된 자식 노드의 수. ex ) 위 노드를 예로 들어 F의 차수는 2, G의 차수는 1, H의 차수는 0트리의 차수 : 트리에 있는 노드의 차수 중 가장 큰 값  ex ) 위 트리의 차수는 2단말 노드 : 차수가 0인 노드. 자식 노드가 없는 노드.  ex ) 위 노드에서는 A, C, E, H가 해당 높이노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨  ex ) B..