유제필의 개발 블로그

요약 수식 계산을 위한 트리 구조로 후위 변환 표기식으로 트리를 구축하고, 중위 표기식으로 변환하여 사용 1개의 연산자와 2개의 피연산자를 요구함 피 연산자는 잎 노드임 연산자는 뿌리 또는 가지 노드임 뒤에서부터 역순으로 계산이 되어야 함 뒤에서부터 1개씩 토큰을 확인해 연산자인지 피연산자인지 확인 수식 트리(Experssion Tree) 수식 트리란 이름 그대로 수식을 표현하는 트리이며, 수식 이진 트리라고도 한다. 하나의 연산자가 2개의 피연산자를 취한다는 가정 아래, 수식 트리는 일반적으로 2가지의 규칙을 가진다. 피연산자는 잎 노드이다. 연산자는 뿌리 노드 또는 가지 노드이다. 예를 들어 아래와 같은 수식이 있다. (1 * 2) + (7 - 8) 피연산자 1, 2, 7, 8은 모두 잎 노드이고, ..

요약 트리 구조에서 하나의 노드가 자식 노드를 2개까지 가질 수 있는 트리 구조 포화 이진 트리와 완전 이진 트리 구조로 나뉨 높이에 따라 높이 균형 트리와 완전 높이 균형 트리 구조로 나뉨 노드 방문 순서에 따라 전위 순회, 중위 순회로 나뉨 트리 소멸 시 잎 구조부터 제거해야 하며 후위 순회 방식으로 제거해야 이진 트리(Binary Tree) 이진 트리란 일반 트리와 개념은 같지만, 하나의 노드가 자식 노드를 2개까지만 가질 수 있다는 점이 다르다. 이진 트리라는 이름도 자식을 둘만 가진다는 의미에서 붙어진 이름이다. 아래 그림이 이진 트리의 구조를 개념적으로 표현한 그림이다. 이진 트리의 종류 이진 트리의 가장 중요한 부분은 노드의 최대 차수가 2라는 사실이다. 즉, 모든 이진 트리 노드의 자식 수..

이진 탐색 트리 요약 시간 복잡도 : O(log(n)) ~ O(n) 왼쪽 하위 트리는 루트보다 작은 값이 위치함 오른쪽 하위 트리는 루트보다 큰 값이 위치함 정렬되어 있는 트리 구조에서 빠른 탐색 속도를 보임 한쪽으로 편향되어 있는 트리 구조에서 비효율적임 이진 탐색 트리(Binary Search Tree) 이진 탐색 트리란 트리 내부에 있는 노드의 값을 찾는 방법으로 아래와 같이 3가지의 조건을 만족하면 된다. 각 노드는 왼쪽 자식 노드보다 큼 각 노드는 오른쪽 자식보다 작음 같은 키 값을 갖는 노드는 없음 위 그림은 이진 탐색 트리를 구현한 예이다. 여기서 노드 5를 보면 왼쪽 하위 트리 노드(4, 1)은 모두 5보다 작다. (조건 1번에 해당) 그리고 오른쪽 하위 트리 노드(7, 6, 9)는 모두 ..