728x90 AVL 트리 개념과 특징 AVL 트리란? 이진 탐색 트리(BST)의 한 종류 스스로 균형(balancing)을 잡는 트리 balance factor(BF)를 통해 균형 유지 노드의 balance factor란? 임의의 노드 x에 대해서 BF(x) = h(lSubtree(x)) - h(rSubtree(x)) BF = balance factor, h = height, lSubtree = left subtree, rSubtree = right subtree AVL의 트리의 특징 balance factor가 -1, 0, 1 셋 중 하나의 값을 가짐. 트리에 삽입 혹은 삭제 후 BF(x)가 -1, 0, 1이 아니라면 노드가 생기면 균형을 맞추는 작업을 수행! AVL 동작 방식 🟨 오른쪽 오른쪽으로 편향된 상태 중간값을 위로 올림. (왼쪽.. 2022. 7. 25. 이진 탐색 트리(binary search tree) 이진 탐색 트리(binary search tree)란? 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 더 큰 값들만 가지는 트리 👉 이진 탐색 트리의 최솟값 트리의 가장 왼쪽에 존재 👉 이진 탐색 트리의 최댓값 트리의 가장 오른쪽에 존재 👉 노드의 successor(후임자) 해당 노드보다 값이 큰 노드들 중에서 가장 값이 작은 노드 👉 노드의 predecessor(선임자) 해당 노드보다 값이 작은 노드들 중에서 가장 값이 큰 노드 👉 이진 탐색 트리 순회하는 방법 이진 탐색 트리에서는 중위 순회를 대체로 사용함! 트리의 탐색 방법에는 3가지가 있음 inorder traversal (중위 순회) 재귀적으로 왼쪽 서브 트리 순회 현재.. 2022. 7. 25. 트리(tree)와 이진 트리(binary tree) 기초 개념 정리 트리(tree)란? 노드들의 집합 각 노드는 값과 다른 노드들을 가리키는 레퍼런스들로 구성 트리 관련 용어 🔸 간선(edge) 노드와 노드를 연결하는 선 구현 관점에서는 레퍼런스를 의미 a.k.a. link, branch 🔸 루트(root) 노드 트리의 최상단에 있는 노드 트리의 시작점 🔸 자녀 노드 모든 노드는 0개 이상의 자녀 노드를 가짐 🔸 부모 노드 자녀 노드를 가지는 노드 🔸 형제 노드 같은 부모를 가지는 노드들 🔸 조상 노드 부모 노드를 따라 루트 노드까지 올라가면 만나는 모든 노드 🔸 자손 모드 자녀 노드를 따라 내려가며 만날 수 있는 모든 노드 🔸 내부 노드 자녀 노드를 가지는 노드 a.k.a branch node, inner node 🔸 외부 노드 자녀 노드가 없는 노드 a.k.a lea.. 2022. 7. 25. 이전 1 다음 728x90