2023. 12. 30. 09:51ㆍ프로그래밍 공부/Data Structure
7.3 이진 트리
이진 트리(binary tree)는 다음과 같은 속성을 가진 순서 트리이다:
1. 모든 노드에는 최대 2개의 자식이 있다.
2. 각 자식 노드는 왼쪽 자식(left child) 또는 오른쪽 자식(right child)으로 레이블이 지정된다.
3. 노드의 자식 순서에서 왼쪽 자식이 오른쪽 자식 앞에 온다.
내부 노드 v의 왼쪽 부분 트리(left subtree) : 내부 노드 v의 왼쪽 자식에 루트를 둔 부분 트리
내부 노드 v의 오른쪽 부분 트리(right subtree): 내부 노드 v의 오른쪽 자식에 루트를 둔 부분 트리
만약 각 노드가 0개 또는 2개의 자식을 가진다면 이진 트리는 적절하다(proper).
완전 이진 트리(full binary tree): 각 노드가 0개 또는 2개의 자식을 가진 이진 트리
따라서, 적절한 이진 트리에서 모든 내부 노드는 정확히 2개의 자식을 가진다.
적절하지 않은 이진 트리는 부적절하다(improper).
예제 7.8: 이진 트리의 중요한 클래스는
일련의 예 또는 아니오 질문에 대한 대답으로 인해
발생할 수 있는 여러 가지 다른 결과를 나타내고자 하는 맥락에서 발생한다.
각 내부 노드는 질문과 관련되어 있다.
질문에 대한 답이 "예"인지 "아니오"인지에 따라
루트에서 시작하여 현재 노드의 왼쪽 또는 오른쪽 자식으로 이동한다.
각 결정에서 우리는 부모에서 자식으로 가장자리를 따라가며,
결국 루트에서 외부 노드로 트리의 경로를 추적한다.
의사결정 트리(decision tree) :
각 외부 노드 v는 v의 조상과 관련된 질문에 v로 이어지는 방식으로 답하면
어떻게 해야 할지에 대한 결정을 나타내는 이진 트리
의사결정 트리는 적절한 이진 트리이다.
그림 7.10은 투자자에게 추천을 제공하는 의사결정 트리를 보여준다.
그림 7.10: 투자 자문을 제공하는 의사결정 트리.
예제 7.9: 외부 노드가 변수나 상수와 연관되어 있고
내부 노드가 연산자 +, -, ×, / 중 하나와 연관되어 있는
이진 트리로 산술 수식을 나타낼 수 있다.
(그림 7.11 참조) 그러한 트리의 각 노드는 연관된 값을 가진다.
• 노드가 외부에 있으면 노드 값은 변수 값 또는 상수 값이다.
• 노드가 내부에 있으면 해당 노드의 값은
해당 노드의 연산을 자식 값에 적용하여 정의된다.
연산자 +, -, ×, / 가 정확히 두 피연산자를 취하므로
산술 수식 트리는 적절한 이진 트리이다.
물론 만약 -x에서와 같이 부정(-)과 같은 단항 연산자를 허용한다면
부적절한 이진 트리를 가질 수 있다.
그림 7.11: 산술 수식을 나타내는 이진 트리이다.
이 트리는 (((3 + 1) × 3)/((9 - 5) + 2) - ((3) × (7 - 4) + 6) 식을 나타낸다.
"/" 레이블이 지정된 내부 노드와 관련된 값은 2이다.
재귀적 이진 트리 정의
또한 재귀적인 방법으로 이진 트리를 정의하여
이진 트리가 비어 있거나 다음과 같이 구성될 수 있다:
• 원소를 저장하는 T의 루트라고 하는 노드 r
• T의 왼쪽 부분 트리라고 하는 이진 트리
• 이진 트리로, T의 오른쪽 부분 트리라고 하다.
아래에서는 이진 트리에 대한 몇 가지 전문적인 주제에 대해 논의한다.
7.3.1 이진 트리 ADT
이진 트리는 추상 데이터 타입으로서
다음과 같은 세 가지 추가 접근 방식을 지원하는 트리의 전문화이다:
left(v):
v의 왼쪽 자식을 반환한다.
v에 왼쪽 자식이 없으면 오류 상태가 발생한다.
right(v):
v의 오른쪽 자식을 반환한다.
v에 오른쪽 자식이 없으면 오류 상태가 발생한다.
hasLeft(v):
v에 왼쪽 자식이 있는지 테스트한다.
hasRight(v):
v에 오른쪽 자식이 있는지 테스트한다.
여기서는 트리 ADT에 대한 섹션 7.1.2에서와 마찬가지로
이진 트리에 대한 특화된 업데이트 메소드를 정의하지 않다.
대신 이진 트리의 구체적인 구현 및 응용을 설명할 때
몇 가지 가능한 업데이트 메소드를 고려할 것이다.
7.3.2 자바의 이진 트리 인터페이스
저희는 이진 트리를 트리 ADT를 확장하고
이진 트리에 대해 3가지 특화된 메소드를 추가하는 추상 데이터 형식으로 모델링한다.
코드 조각 7.14에서는 이러한 접근 방식을 사용하여
정의할 수 있는 간단한 Java 인터페이스를 보여준다.
그런데, 이진 트리는 순서 트리이므로
메소드 children(v)(Tree 인터페이스에서 상속됨)에 의해
반환되는 반복 가능한 컬렉션은
v의 오른쪽 child 앞에 v의 왼쪽 child를 저장한다.
코드 조각 7.14:
이진 트리 ADT를 위한 자바 인터페이스 이진 트리.
인터페이스 이진 트리는 인터페이스 트리를 확장한다(코드 조각 7.1).
/**
* An interface for a binary tree, where each node can have zero, one,
* or two childeren.
*/
public interface BinaryTree<E> extends Tree<E> {
/** Returns the left child of a node */
public Position<E> left(Position<E> v)
throws InvalidPositionException, BoundaryViolationException;
/** Returns the right child of a node */
public Position<E> right(Position<E> v)
throws InvalidPositionException, BoundaryViolationException;
/** Returns whether a node has a left child. */
public boolean hasLeft(Position<E> v) throws InvalidPositionException;
/** Returns whether a node has a right child. */
public boolean hasRight(Position<E> v) throws InvalidPositionException;
}
7.3.3 이진 트리의 특성
이진 트리에는 높이와 노드 수 사이의 관계를 다루는 몇 가지 흥미로운 속성이 있다.
우리는 T의 레벨 d와 같은 깊이 d에 있는 트리 T의 모든 노드의 집합을 나타낸다.
이진 트리에서 레벨 0은 많아야 하나의 노드(루트)를,
레벨 1은 많아야 두 개의 노드(루트의 자식)를,
레벨 2는 많아야 네 개의 노드를 포함하는 등등이다.
(그림 7.12 참조) 일반적으로 레벨 d는 많아야 2^d의 노드를 가진다.
그림 7.12: 이진 트리 레벨의 최대 노드 수.
우리는 이진 트리의 레벨에 있는 최대 노드 수가 트리를 내려갈수록
기하급수적으로 증가하는 것을 알 수 있다.
이 간단한 관찰을 통해 이진 T의 높이와 노드 수 사이의 관계를
다음과 같은 성질을 얻을 수 있다.
이러한 특성에 대한 자세한 설명은 연습(R-7.15)으로 남겨진다.
명제 7.10: T는 비어 있지 않은 이진 트리라고 하고,
n, nE, nI, h를 각각 노드 수, 외부 노드 수, 내부 노드 수, 높이 T를 나타내면
T는 다음과 같은 성질을 갖는다:
1. h+1 ≤ n ≤ 2^(h+1) −1
2. 1 ≤ nE≤ 2^h
3. h ≤ nI≤ 2^(h-1)
4. log (n+1) − 1 ≤ h ≤ n−1.
또한 T가 적절하면 T는 다음과 같은 성질을 갖는다:
1. 2h + 1 ≤ n ≤ 2^(h+1) − 1
2. h + 1 ≤ nE ≤ 2^h
3. h ≤ nI ≤ 2^h - 1
4. log (n + 1) − 1 ≤ h ≤ (n − 1)/2.
적절한 이진 트리의 내부 노드와 외부 노드와의 관계
위의 이진 트리 속성 외에도
적절한 이진 트리의 내부 노드 수와 외부 노드 수 사이에는
다음과 같은 관계가 있다.
제안 7.11: nE개의 외부 노드와 nI개의 내부 노드가 있는
비어 있지 않은 적절한 이진 트리 T에서
ne = nI + 1이 있다.
정당화: T가 비어있을 때까지
T에서 노드를 제거하고 내부 노드 더미과 외부 노드 더미,
두 개의 "더미"로 나누어 이 명제를 정당화한다.
파일은 처음에 비어 있다.
마지막에 외부 노드 더미는 내부 노드 더미보다 하나의 노드를 더 많이 가질 것이다.
다음 두 가지 경우를 고려한다:
Case 1: T가 하나의 노드 v만을 가지면,
우리는 v를 제거하고 그것을 외부-노드 더미 위에 놓는다.
따라서, 외부-노드 더비는 하나의 노드를 가지며, 내부-노드 더미는 비어 있다.
Case 2: 그렇지 않은 경우(T에 노드가 두 개 이상 있음),
Tan (임의) 외부 노드 w와 내부 노드인 부모 v에서 제거한다.
외부 노드 파일에 w를, 내부 노드 파일에 v를 배치한다.
v에 부모 u가 있는 경우, 그림 7.13과 같이 w의 이전 형제 z와 u를 다시 연결한다.
이 작업은 내부 노드와 외부 노드를 하나씩 제거하고 트리를 적절한 이진 트리로 남긴다.
이 작업을 반복하면 결국 하나의 노드로 구성된 최종 트리가 남게 된다.
이 최종 트리로 이어지는 일련의 작업에 의해
동일한 수의 외부 노드와 내부 노드가 제거되고 각각의 파일에 배치된다.
이제 최종 트리의 노드를 제거하고 외부 노드 파일에 배치한다.
따라서 외부 노드 파일에는 내부 노드 파일보다 하나의 노드가 더 많이 있다.
그림 7.13: 제안 7.11의 정당화에 사용되는 외부 노드와 해당 부모 노드를 제거하는 작업.
일반적으로 부적절한 이진 트리와 이진 트리가 아닌 트리에 대해서는
위의 관계가 성립하지 않는다는 점에 유의하자(C-7.7).
7.3.4 이진 트리의 연결 구조
일반 트리와 마찬가지로 이진 트리 T를 구현하는 자연스러운 방법은
연결 구조(linked structure)를 사용하는 것이다.
여기서 T의 각 노드 v를 v에 저장된 요소와
v의 자식 및 부모와 관련된 위치 객체에 대한 참조를 제공하는 필드로 표시한다
(그림 7.14a 참조).
v가 T의 루트라면 v의 부모 필드는 null이다.
v에 왼쪽 자식이 없으면 v의 왼쪽 필드는 null이다.
v에 오른쪽 자식이 없으면 v의 오른쪽 필드는 null이다.
또한 T의 노드 수를 크기라는 변수에 저장한다.
그림 7.14b에 이진 트리의 연결 구조를 보여한다.
그림 7.14: 이진 트리를 표현하기 위한 노드(a)와 연결 구조(b).
이진 트리 노드의 Java 구현
이진 트리의 노드를 나타내기 위해
Java 인터페이스 BTPosition(표시되지 않음)을 사용한다.
이 인터페이스는 Position을 확장하여 메소드 요소를 상속하며
노드(setElement)에 저장된 요소를 설정하고
노드의 왼쪽 자식(setLeft 및 getLeft),
오른쪽 자식(setRight 및 getRight) 및
부모(setParent 및 getParent)를
설정 및 반환하기 위한 추가 메소드를 가지고 있다.
클래스 BTNode(코드 조각 7.15)는
v의 요소, v의 왼쪽 자식, v의 오른쪽 자식 및 v의 부모를 각각 참조하는
필드 요소, 왼쪽, 오른쪽 및 부모를 갖는 객체에 의한
인터페이스 BTPosition을 구현한다.
코드 조각 7.15: 이진 트리 노드를 구현하기 위한 보조 클래스 BTNode.
/**
* Class implementing a node of a binary tree by storing references to
* an element, a parent node, a left node, and a right node.
*/
public class BTNode<E> implements BTPosition<E> {
private E element; // element stored at this node
private BTPosition<E> left, right, parent; // adjacent nodes
/** Main constructor */
public BTNode(E element, BTPosition<E> parent,
BTPosition<E> left, BTPosition<E> right) {
setElement(element);
setParent(parent);
setLeft(left);
setRight(right);
}
/** Returns the element stored at this position */
public E element() { return element; }
/** Sets the element stored at this position */
public void setElement(E o) { element=o; }
/** Returns the left child of this position */
public BTPosition<E> getLeft() { return left; }
/** Sets the left child of this position */
public void setLeft(BTPosition<E> v) { left=v; }
/** Returns the right child of this position */
public BTPosition<E> getRight() { return right; }
/** Sets the right child of this position */
public void setRight(BTPosition<E> v) { right=v; }
/** Returns the parent of this position */
public BTPosition<E> getParent() { return parent; }
/** Sets the parent of this position */
public void setParent(BTPosition<E> v) { parent=v; }
}
연결된 이진 트리 구조의 Java 구현
코드 조각 7.16-7.18에서는 연결된 자료 구조를 사용하여
BinaryTree 인터페이스(코드 조각 7.14)를 구현하는
LinkedBinaryTree 클래스의 일부를 보여준다.
이 클래스는 트리의 크기와 트리의 루트와 관련된
BTNode 객체에 대한 참조를 내부 변수에 저장한다.
LinkedBinaryTree에는 Binary Tree 인터페이스 메소드 외에도
노드 v의 형제를 반환하는 접근자 메소드 sibling(v) 및
다음 업데이트 메소드를 포함한 다양한 다른 메소드가 있다:
addRoot(e):
새 노드 저장 요소를 생성하여 반환하고 트리의 루트를 만든다.
트리가 비어 있지 않으면 오류가 발생한다.
insertLeft(v,e):
새 노드 w 저장 요소 e를 생성하고 반환한다.
v의 왼쪽 자식으로 추가하고 w를 반환한다.
v에 왼쪽 자식이 이미 있는 경우 오류가 발생한다.
insertRight(v,e):
요소 e를 저장하는 새 노드 z를 생성하고 반환하고
z를 v의 오른쪽 자식으로 추가하고 z를 반환한다.
v에 이미 오른쪽 자식이 있는 경우 오류가 발생한다.
remove(v):
노드 v를 제거하고 해당 노드가 있는 경우
해당 노드 v를 해당 하위 노드로 교체한 후 v에 저장된 요소를 반환한다.
v에 두 개의 하위 노드가 있는 경우 오류가 발생한다.
attach(v,T1,T2):
T1과 T2를 각각 외부 노드 v의 왼쪽과 오른쪽 하위 트리로 연결한다.
v가 외부가 아닌 경우 오류 조건이 발생한다.
클래스 LinkedBinaryTree에는
빈 이진 트리를 반환하는 인수가 없는 생성자가 있다.
이 빈 트리부터 메소드 addRoot로 첫 번째 노드를 만들고
insertLeft와 insertRight 메소드 및/또는 attach 메소드를 반복적으로 적용하여
임의의 이진 트리를 만들 수 있다.
마찬가지로 remove 연산을 사용하여
임의의 이진 트리 T를 해체할 수 있으므로
궁극적으로 이러한 트리 T를 빈 이진 트리로 줄일 수 있다.
위치 v가 LinkedBinaryTree 클래스의 메소드 중 하나에 인수로 전달되면
보조 도우미 메소드인 checkPosition(v)를 호출하여 유효성을 확인한다.
트리의 전위 순회에 방문한 노드의 리스트는
재귀적 메소드 preorderPositions에 의해 구성된다.
오류 조건은 예외를 던져 InvalidPositionException, BoundaryViolationException,
EmptyTreeException 및 NonEmptyTreeException을 지정한다.
코드 조각 7.16-7.20:
Binary Tree 인터페이스를 구현하는
Linked Binary Tree 클래스이다.
/**
* An implementation of the BinaryTree interface by means of a linked structure.
*/
public class LinkedBinaryTree<E> implements BinaryTree<E> {
protected BTPosition<E> root; // reference to the root
protected int size; // number of nodes
/** Creates an empty binary tree. */
public LinkedBinaryTree() {
root = null; // start with an empty tree
size = 0;
}
/** Returns the number of nodes in the tree */
public int size() {
return size;
}
/** Returns whether a node is internal. */
public boolean isInternal(Position<E> v) throws InvalidPositionException {
checkPosition(v); // auxiliary method
return (hasLeft(v) || hasRight(v));
}
/** Returns whether a node is the root. */
public boolean isRoot(Position<E> v) throws InvalidPositionException {
checkPosition(v);
return (v == root());
}
/** Returns whether a node has a left child. */
public boolean hasLeft(Position<E> v) throws InvalidPositionException{
BTPosition<E> vv = checkPosition(v);
return (vv.getLeft() != null);
}
/** Returns the root of the tree. */
public Position<E> root() throws EmptyTreeException {
if (root == null)
throw new EmptyTreeException("The tree is empty");
return root;
}
/** Returns the left child of a node */
public Position<E> left(Position<E> v)
throws InvalidPositionException, BoundaryViolationException {
BTPosition<E> vv = checkPosition(v);
Position<E> leftPos = vv.getLeft();
if (leftPos == null)
throw new EmptyTreeException("No left child");
return leftPos;
}
/** Returns the parent of a node */
public Position<E> parent(Position<E> v)
throws InvalidPositionException, BoundaryViolationException {
BTPosition<E> vv = checkPosition(v);
Position<E> parentPos = vv.getLeft();
if (parentPos == null)
throw new EmptyTreeException("No parent");
return parentPos;
}
/** Returns an iterable collection of the children of a node. */
public Iterable<Position<E>> children(Position<E> v)
throws InvalidPositionException {
PositionList<Position<E>> children = new NodePositionList<Position<E>>();
if (hasLeft(v))
children.addLast(left(v));
if (hasRight(v))
children.addLast(right(v));
return children;
}
/** Returns an iterable collection of the tree node. */
public Iterable<Position<E>> positions() {
PositionList<Position<E>> children = new NodePositionList<Position<E>>();
if (size != 0)
preorderPositions(root(v), positions); // assign positions in preorder
return positions;
}
/** Returns an iterator of the element stored at the nodes */
public Iterator<E> Iterator() {
Iterable<Position<E>> positions = positions();
PositionList elements = new NodePositionList<E>();
for (<Position<E>> pos: positions)
elements.addLast(pos.element());
return elements.iterator(); // An iterator of elements
}
/** Replaces the element at a node */
public E replace(Position<E> v, E o)
throws InvalidPositionException {
BTPosition<E> vv = checkPosition(v);
E temp = v.element();
vv.setElement();
return temp;
}
/** Returns the sibling of a node */
public Position<E> parent(Position<E> v)
throws InvalidPositionException, BoundaryViolationException {
BTPosition<E> vv = checkPosition(v);
Position<E> parentPos = vv.getLeft();
if (parentPos != null) {
BTPosition<E> sibPos;
BTPosition<E> leftPos = parentPos.getLeft();
if (leftPos == vv)
sibPos = parentPos.getRight();
else
sibPos = parentPos.getLeft();
if (sibPos != null)
return sibPos;
}
throw new BoundaryViolationException("No sibling");
}
// Additional update methods
/** Adds a root node to an empty tree */
public Position<E> addRoot(E e) throws NonEmptyTreeException {
if(!isEmpty())
throw new NonEmptyTreeException("Tree already has a root");
size = 1;
root = createNode(e,null,null,null);
return root;
}
/** Inserts a left child at a given node */
public Position<E> insertLeft(Position<E> v, E e)
throws InvalidPositionException {
BTPosition<E> vv = checkPosition(v);
Position<E> leftPos = vv.getLeft();
if (leftPos != null)
throw new InvalidPositionException("Node already has a left child");
BTPosition<E> ww = createNode(e, vv, null, null);
vv.setLeft(ww);
size++;
return ww;
}
/** Removes a node with zero or one child. */
public E remove(Position<E> v)
throws InvalidPositionException {
BTPosition<E> vv = checkPosition(v);
Position<E> leftPos = vv.getLeft();
Position<E> rightPos = vv.getRight();
if (leftPos != null && rightPos != null)
throw new InvalidPositionException("Cannot remove node with two children");
BTPosition<E> ww; // the only child of v, if any
if (leftPos != null)
ww = leftPos;
else if (rightPos != null)
ww = rightPos;
else // v is a leaf
ww = null;
if (vv == root) { // v is the root
if (ww != null)
ww.setParent(null);
root = ww;
}
else { // v is not the root
BTPosition<E> uu = vv.getParent();
if (vv == uu.getLeft())
uu.setLeft(ww);
else
uu.setRight(ww);
if(ww != null)
ww.setParent(uu);
}
size--;
return v.element();
}
/** Attaches two trees to be subtrees of an external node. */
public void attach(Position<E> v, BinaryTree<E> T1, BinaryTree<E> T2)
throws InvalidPositionException {
BTPosition<E> vv = checkPosition(v);
if (isInternal(v))
throw new InvalidPositionException("Cannot attach from internal node");
if (!T1.isEmpty()) {
BTPosition<E> r1 = checkPosition(T1.root());
vv.setLeft(r1);
r1.setParent(vv); // T1 should be invalidated
}
if (!T2.isEmpty()) {
BTPosition<E> r2 = checkPosition(T2.root());
vv.setLeft(r2);
r2.setParent(vv); // T2 should be invalidated
}
}
/** If v is a good binary tree node, cast to BTPosition, else throw exception */
protected BTPosition<E> checkPosition(Position<E> v)
throws InvalidPositionException {
if (v == null || !(v instanceof BTPosition))
throw new InvalidPositionException("The position is invalid");
return (BTPosition<E>) v;
}
/** Creates a new binary tree node */
protected BTPosition<E> createNode(E element, BTPosition<E> parent,
BTPosition<E> left, BTPosition<E> right) {
return new BTNode<E>(element,parent,left,right); }
/** Creates a list storing the nodes in the subtree of a node,
* ordered according to the preorder traversal of the subtree. */
protected void preorderPositions(Position<E> v, PositionList<Position<E>> pos)
throws InvalidPositionException {
pos.addLast(v);
if (hasLeft(v))
preorderPositions(left(v), pos); // recurse on left child
if (hasRight(v))
preorderPositions(right(v), pos); // recurse on right child
}
연결 이진 트리 구현의 성능
이제 연결 구조 표현을 사용하는
클래스 LinkedBinaryTree의 실행 시간을 분석해 보겠다:
• 메소드 size() 및 is Empty()는
T의 노드 수를 저장하는 인스턴스 변수를 사용하며 각각 O(1) 시간이 걸린다.
• 접근자 메소드 root, left, right, sibling 및 parent는 O(1) 시간이 걸린다.
• 메소드 replace(v,e)는 O(1) 시간이 걸린다.
• 메소드 iterator()와 positions()는 트리의 전위 순회를 수행하여
(보조 메소드 preorderPositions를 사용하여) 구현된다.
순회에 의해 방문된 노드는
클래스 NodePositionList(섹션 6.2.4)에 의해 구현된 위치 리스트에 저장되며
출력 반복기는 클래스 NodePositionList의 메소드 iterator()로 생성된다.
메소드 iterator()와 positions()는 O(n) 시간이 소요되며
메소드 hasNext()와 반환된 반복자의 next()는 O(1) 시간에 실행된다.
• 메소드 children는 반환되는 반복 가능한 컬렉션을 구성하는 데
유사한 접근 방식을 사용하지만
이진 트리의 모든 노드에 대해 최대 두 개의 자식이 있으므로
O(1) 시간 내에 실행된다.
• 업데이트 메소드 insertLeft, insertRight, attach, remove는
일정한 수의 노드를 일정한 시간으로 조작하는 것이므로
모두 O(1) 시간 내에 실행된다.
n개의 노드를 가진 트리에 대해
이 데이터 구조에 의해 요구되는 공간을 고려하여
트리 T의 모든 노드에 대해
클래스 BTNode(코드 조각 7.15)의 객체가 있다는 것을 주목하자.
따라서 전체 공간 요구 사항은 O(n)이다.
표 7.2는 이진 트리의 링크된 구조 구현의 성능을 요약한 것이다.
표 7.2: 연결 구조로 구현된 n개 노드 이진 트리의 메소드에 대한 실행 시간이다.
메소드에는 iterator(), positions().iterator() 및 children(v).iterator()이
O(1) 시간에 실행되는 반복자 중 메소드 hasNext()와 next()가 있다.
공간 사용량은 O(n)이다.
| 연산 | 시간 |
| size, isEmpty | O(1) |
| iterator, positions | O(n) |
| replace | O(1) |
| root, parent, children, left, right, sibling | O(1) |
| hasLeft, hasRight, isInternal, isExternal, isRoot | O(1) |
| insertLeft, insertRight, attach, remove | O(1) |
7.3.5 이진 트리의 배열 리스트 표현
이진 트리 T의 다른 표현은 T의 노드에 번호를 매기는 방법에 기초한다.
T의 모든 노드 v에 대하여 p(v)를 다음과 같이 정의된 정수라고 한다.
• v가 T의 근이면 p(v) = 1이다.
• v가 노드 u의 왼쪽 자식이면 p(v) = 2p(u)이다.
• v가 노드 u의 오른쪽 자식이면 p(v) = 2p(u) + 1이다.
번호 부여 함수 p는
이진 트리 T에서 노드의 레벨 넘버링(level numbering)으로 알려져 있다.
이는 T의 각 레벨에 있는 노드에
왼쪽에서 오른쪽으로 증가하는 순서로 번호를 매기기 때문이다(그림 7.15 참조)
그림 7.15: 이진 트리 수준 번호 지정:
(a) 일반적인 계획; (b) 예.
레벨 넘버링 함수 p는 T의 노드 v가 인덱스 p(v)에서 S의 원소가 되도록
배열 리스트 S를 통해 이진 트리 T를 표현하는 것을 나타낸다.
앞 장에서 언급한 것처럼,
우리는 확장 가능한 배열을 통해 배열 리스트 S를 실현한다.
(섹션 6.1.4 참조)
이러한 구현은 연산에 관련된
각 노드 v와 관련된 숫자 p(v)에 대한 간단한 산술 연산을 사용하여
root, parent, left, hasleft, hasRight, isInternal, isExternal, isRoot의 메소드를
쉽게 수행할 수 있으므로 간단하고 효율적이다.
우리는 그림 7.16에서 이진 트리의 배열 리스트 표현의 예시를 보여준다.
그림 7.16: 배열 리스트 S에 의한 이진 트리 T의 표현.
n: T의 노드 수라고 하고,
pM: T의 모든 노드에 대한 p(v)의 최대값
인덱스 0의 S의 요소는 T의 어떤 노드와도 연관되지 않으므로
배열 목록 S는 크기 N = pM + 1을 갖는다.
또한 일반적으로 S는 T의 기존 노드를 참조하지 않는 빈 요소를 많이 가질 것이다.
사실 최악의 경우 N = 2n이다.
8.3절에서 우리는 N = n + 1인 "heaps"라고 불리는 이진 트리의 클래스를 볼 것이다.
따라서 최악의 경우 공간 사용에도 불구하고
이진 트리의 배열 목록 표현이 공간 효율적인 응용 프로그램이 있다.
그러나 일반적인 이진 트리의 경우
이 표현의 지수적인 최악의 경우 공간 요구 사항은 금지된다.
표 7.3은 배열 리스트로 구현된 이진 트리의 메소드의 실행 시간을 요약한 것이다.
여기에는 트리 업데이트 메소드는 포함되어 있지 않다.
표 7.3: 배열 리스트 S로 구현된 이진 트리 T의 실행 시간.
n: T의 노드 수, N: S의 크기
O(N): 공간 사용량, O(2N): 최악의 경우 O(2^n)
| 연산 | 시간 |
| size, isEmpty | O(1) |
| iterator, positions | O(n) |
| replace | O(1) |
| root, parent, children, left, right, sibling | O(1) |
| hasLeft, hasRight, isInternal, isExternal, isRoot | O(1) |
7.3.6 이진 트리의 순회
일반 트리와 마찬가지로 이진 트리 계산에도 종종 순회가 포함된다.
표현식 트리 작성
크기 n의 완전한 괄호가 있는 산술 표현식에서
수식 트리를 구성하는 문제를 생각해 보자.
(예시 7.9 및 코드 조각 7.24의 회상)
코드 조각 7.21에서는
모든 산술 연산이 이진이고 변수가 괄호가 없는 경우를 가정하여
이러한 표현식 트리를 구성하기 위한 알고리즘 buildExpression을 제공한다.
따라서 괄호가 있는 모든 하위 표현식은 중간에 연산자를 포함한다.
알고리즘은 입력된 표현식 E를 스캔하면서
스택 S를 사용하여 변수, 연산자 및 오른쪽 괄호를 찾는다.
• 변수나 연산자 x가 보이면, 우리는 단일 노드 이진 트리 T를 만들고,
그 트리의 루트는 x를 저장하고 T를 스택에 푸쉬한다.
• 오른쪽 괄호 ")"가 보이면,
우리는 부분 표현 (E1 o E2)를 나타내는 스택 S에서 상위 세 트리를 팝(pop)한다.
그런 다음 E1과 E2에 대한 트리를 하나의 트리에 연결하고,
결과적으로 생성된 트리를 S 위로 다시 밀어 넣는다.
표현식 E가 처리될 때까지 이를 반복한다.
이때 스택의 최상위 요소는 E에 대한 표현식 트리이다.
총 실행 시간은 O(n)이다.
코드 조각 7.21: 알고리즘 buildExpression.
Algorithm buildExpression(E):
Input: A fully-parenthesized arithmetic expression E = e0, e1, ..., en-1, with
each e1 being a variable, operator, or parenthetic symbol
Output: A binary tree T representing arithmetic expression E
S ← a new initially-empty stack
for i ← 0 to n - 1 do
if e1 is a variable or an operator then
T ← a new empty binary bree
T.addRoot(e1)
S.push(T)
else if e1 = '(' then
Continue looping
else {e1 = ')'}
T2 ← S.pop() {the tree representing E2 }
T ← S.pop() {the tree representing ○ }
T1 ← S.pop() {the tree representing E1 }
T.attach(T.root(), T1, T2)
S.push(T)
return S.pop()
이진 트리의 전위 순회
어떤 이진 트리도 일반 트리로 볼 수 있기 때문에
일반 트리에 대한 전위 순회(코드 조각 7.8)를
어떤 이진 트리에도 적용할 수 있다.
그러나 코드 조각 7.22에 나와 있는 것처럼
이진 트리 순회의 경우 알고리즘을 단순화할 수 있다.
코드 조각 7.22:
노드 v에 루트가 있는 이진 트리 T의 서브트리의 전위 순회를
수행하기 위한 알고리즘 binaryPreorder.
Algorithm binaryPreorder(T, v):
perform the "visit" action for node v
if v has a left child u in T then
binaryPreorder(T, u) {recursively traverse left subtree}
if v has a right child u in T then
binaryPreorder(T, u) {recursively traverse right subtree}
일반 트리의 경우와 마찬가지로 이진 트리에 대한 전위 순회의 많은 응용이 있다.
이진 트리의 후위 순회
유사하게, 일반 트리(코드 조각 7.11)에 대한 후위 순회는
코드 조각 7.23과 같이 이진 트리에 특화될 수 있다.
코드 조각 7.23:
노드 v에 루트를 둔 이진 트리 T의 하위 트리에 대한 후위 순회를
수행하기 위한 알고리즘 binaryPostorder.
Algorithm binaryPostorder(T, v):
if v has a left child u in T then
binaryPreorder(T, u) {recursively traverse left subtree}
if v has a right child u in T then
binaryPreorder(T, u) {recursively traverse right subtree}
perform the "visit" action for node v
표현식 트리 평가
표현식 트리 평가 문제는 이진 트리의 후위 순회를 이용하여 풀 수 있다.
이 문제에서는 산술식 트리,
즉 외부의 각 노드가 관련된 값을 가지고
내부의 각 노드가 관련된 산술 연산을 하는 이진 트리가 주어지는데(예 7.9 참조),
트리로 표현되는 산술식의 값을 계산하고자 한다.
코드 조각 7.24에 주어진 알고리즘 evaluateExpression은
산술 수식 트리 T의 노드 v에 루트를 둔 부분 트리와
관련된 표현식을 v에서 시작하는 T의 후위 순회를 수행하여 평가한다.
이 경우 "방문" 작업은 단일 산술 연산을 수행하는 것으로 구성된다.
산술 수식 트리는 적절한 이진 트리라는 사실을 사용한다.
코드 조각 7.24:
알고리즘은 노드 v에 루트를 둔
산술 표현 트리 T의 서브트리로 표현되는 식을 평가하기 위해
evaluateExpression을 평가한다.
Algorithm evaluateExpression(T, v):
if v is an internal node in T then
let ○ be the operator stored at v
x ← evaluateExpression(T, T.left(v))
y ← evaluateExpression(T, T.right(v))
return x ○ y
else
return the value stored at v
후위 순회의 표현식 트리 평가 응용 프로그램은
n개의 노드를 가진 이진 트리로 표현되는 산술식을 평가하기 위한
O(n)-시간 알고리즘을 제공한다.
실제로 일반적인 후위 순회와 마찬가지로
이진 트리에 대한 후위 순회는
다른 "바텀-업" 평가 문제에도 적용될 수 있다(예: 7.7의 크기 계산).
이진 트리의 중위 순회
중위 순회(inorder traversal): 왼쪽 부분 트리와 오른쪽 부분 트리의 재귀적 순회 사이의 노드를 방문한다.
이진 트리 T의 노드 v에 루트를 둔
부분 트리의 중위 순회는 코드 조각 7.25에 나와 있다.
코드 조각 7.25:
노드 v에 루트가 있는 이진 트리 T의 서브트리의 중위 순회를 수행하기 위한 알고리즘 inorder.
Algorithm inorder(T, v):
if v has a left child u in T then
binaryPreorder(T, u) {recursively traverse left subtree}
perform the "visit" action for node v
if v has a right child u in T then
binaryPreorder(T, u) {recursively traverse right subtree}
이진 트리 T의 중위 순회는
비공식적으로 "왼쪽에서 오른쪽으로" T의 노드를 방문하는 것으로 볼 수 있다.
실제로 모든 노드 v에 대하여 중위 순회는
v의 왼쪽 부분 트리에 있는 모든 노드 다음에
v의 오른쪽 부분 트리에 있는 모든 노드 앞에 v를 방문한다. (그림 7.17 참조)
그림 7.17: 이진 트리의 중위 순회.
이진 검색 트리
원소들이 순서 관계를 가지는 집합을 S라고 하자.
예를 들어, S는 정수들의 집합일 수 있다.
S에 대한 이진 탐색 트리는 다음과 같은 적절한 이진 트리 T이다
• T의 각 내부 노드 v는 x(v)로 표시된 S의 요소를 저장한다.
• T의 각 내부 노드 v에 대해
v의 왼쪽 부분 트리에 저장된 요소는 x(v)보다 작거나 같고
v의 오른쪽 부분 트리에 저장된 요소는 x(v)보다 크거나 같다.
• T의 외부 노드는 어떤 요소도 저장하지 않는다.
이진 탐색 트리 T의 내부 노드를 순서대로 순회하면
감소하지 않는 순서로 요소를 방문한다(그림 7.18 참조)
그림 7.18: 정수를 저장하는 이진 탐색 트리.
파란색 실선 경로는 36을 검색(성공)할 때 통과된다.
파란색 점선 경로는 70을 검색(실패)할 때 통과된다.
집합 S에 대해 이진 탐색 트리 T를 사용하여
루트에서 시작하여 트리 T 아래로 경로를 이동함으로써
주어진 탐색 값 y가 S에 속하는지 찾을 수 있다. (그림 7.18 참조)
각 내부 노드 v에서 탐색 값 y를 v에 저장된 요소 x(v)와 비교한다.
y = x(v)이면 v의 왼쪽 부분 트리에서 탐색을 계속한다.
y = x(v)이면 탐색이 성공적으로 종료된다.
만약 y ≥ x(v)이면 v의 오른쪽 부분 트리에서 검색이 계속된다.
마지막으로 외부 노드에 도달하면 검색이 성공적으로 종료된다.
즉, 이진 검색 트리는 이진 의사결정 트리로 볼 수 있는데,
여기서 각 내부 노드에서 질문하는 것은
해당 노드의 요소가 검색되는 요소보다 작거나 같거나 더 큰지 여부이다.
실제로 이러한 것은 이진 의사결정 트리와 정확히 일치하며,
이진 검색 트리가
적절한 이진 트리("자리 표시자" 외부 노드가 있는 경우)가 되도록
제한하는 동기를 부여한다.
이진 탐색 트리 T에서 탐색하는 실행 시간은 T의 높이에 비례한다.
명제 7.10에서 n개의 노드를 가진 적절한 이진 트리의 높이는
log(n + 1) - 1만큼 작을 수도 있고 (n - 1)/2만큼 클 수도 있음을 상기하자.
따라서 이진 탐색 트리는 높이가 작을 때 가장 효율적이다.
그림 7.18에서 이진 탐색 트리의 예제 검색 연산을 설명하고,
10.1절에서 이진 탐색 트리를 더 자세히 연구한다.
트리 그리기에 대한 중위 순회 사용
이진 트리의 그리기를 계산하는 문제에도 순서 순회를 적용할 수 있다.
다음 두 가지 규칙을 이용하여
x좌표와 y좌표를 T의 노드 v에 할당하는 알고리즘으로
이진 트리 T를 그릴 수 있다(그림 7.19 참조):
• x(v)는 T의 순서대로 이동할 때 v 이전에 방문한 노드의 수이다
• y(v)는 t의 v의 깊이이다.
이 응용 프로그램에서는 컴퓨터 그래픽에서 x좌표는 왼쪽에서 오른쪽으로,
y좌표는 위에서 아래로 증가한다는 일반적인 규칙을 취한다.
그래서 원점은 컴퓨터 화면의 왼쪽 위에 있다.
그림 7.19: 이진 트리의 순서도
이진 트리의 오일러 투어 순회
지금까지 논의한 트리 순회 알고리즘은 모두 반복자의 형태이다.
각 순회는 특정 순서로 트리의 노드를 방문하며,
각 노드를 한 번씩만 방문하는 것이 보장된다.
그러나 각 노드를 한 번만 방문해야 한다는 요구를 완화하면
위에서 제시한 트리 횡단 알고리즘을 하나의 틀로 통합할 수 있다.
그 결과 도출된 순회 방법을 오일러 투어 순회(Euler Tour Traversal)라고 하는데,
우리는 이 방법을 다음에 공부한다.
이 순회의 장점은 좀 더 일반적인 종류의 알고리즘을 쉽게 표현할 수 있다는 것이다.
이진 트리 T의 오일러 순회는
비공식적으로 T 주변의 "보행"으로 정의할 수 있으며,
T의 가장자리를 항상 왼쪽으로 유지하는 "벽"으로 간주하고
루트에서 왼쪽 자식 방향으로 이동하는 것으로 시작한다. (그림 7.20 참조)
오일러 순회는 T의 각 마디 v와 세 번 마주친다:
• "왼쪽" (v의 왼쪽 부분 트리의 오일러 투어 전)
• "아래로부터" (v의 두 부분 트리의 오일러 투어 사이)
• "오른쪽" (v의 오른쪽 부분 트리의 오일러 투어 후).
v가 외부에 있다면, 이 세 가지 "방문"은 실제로 모두 동시에 일어난다.
우리는 v에 루트를 둔 부분 트리의 오일러 투어 코드 조각 7.26을 설명한다.
그림 7.20: 오일러 투어 이진 트리의 순회.
코드 조각 7.26:
v에 루트를 둔 이진 트리 T의 부분 트리에 대한 오일러 투어.
Algorithm eulerTour(T, v):
perform the action for visiting node v on the left
if v has a left child u in T then
eulerTour(T, u) {recursively traverse left subtree of v}
perform the action for visiting node v from below
if v has a right child u in T then
eulerTour(T, u) {recursively traverse right subtree of v}
perform the action for visiting node v on the right
각 방문 조치가 O(1) 시간이 걸린다고 가정할 때,
n개의 노드 트리의 오일러 순회의 실행 시간은 분석하기 쉽다.
우리는 순회하는 동안 트리의 각 노드에서 일정한 시간을 보내기 때문에
전체 실행 시간은 O(n)이다.
이진 트리의 전위 순회는 오일러 투어 순회와 같으므로
각 노드는 왼쪽에서 마주칠 때만 "방문" 작용을 한다.
마찬가지로 이진 트리의 중위 순회와 후위 순회는 오일러 투어와 같으므로
각 노드는 아래 또는 오른쪽에서 마주칠 때만 방문 작용을 한다.
오일러 투어 운행은 전위, 중위, 후위 순회를 확장하지만
다른 종류의 순회도 할 수 있다.
예를 들어 n개의 노드를 가진 이진 트리에서
각 노드 v의 자손의 수를 계산하려고 한다고 가정한다.
우리는 카운터를 0으로 초기화함으로써
오일러 투어를 시작하고 왼쪽 노드를 방문할 때마다 카운터를 증가시킨다.
노드 v의 자손의 수를 구하기 위해
v가 왼쪽에 있을 때와 오른쪽에 있을 때의 카운터 값의 차이를 계산하고 1을 더한다.
이 간단한 규칙은 v에 루트를 둔 부분 트리의 각 노드가
왼쪽의 v의 방문과 오른쪽의 v의 방문 사이에서 계산되기 때문에
v의 자손의 수를 제공한다.
따라서 각 노드의 자손의 수를 계산하는 O(n) 시간 메소드가 있다.
오일러 투어 순회의 또 다른 응용은 표현식 트리에서
완전 괄호가 있는 산술 표현식을 인쇄하는 것이다(예: 7.9).
코드 조각 7.27에 표시된 알고리즘 printExpression은
오일러 투어에서 다음 작업을 수행하여 이 작업을 수행한다:
• "왼쪽" 작업: 노드가 내부에 있으면 "("를 인쇄한다
• "아래로부터" 작업: 노드에 저장된 값 또는 연산자를 인쇄한다
• "오른쪽" 작업: 노드가 내부에 있으면 ")"를 인쇄한다.
코드 조각 7.27: v에 루트를 둔 산술 표현 트리 T의 서브트리와
관련된 산술 표현식을 출력하기 위한 알고리즘.
Algorithm printExpression(T, v):
if T.isInternal(v) then
print "("
if T.hasLeft(v) then
printExpression(T, T.left(v))
if T.isInternal(v) then
print the operator stored at v
else
print the value stored at v
if T.hasRight(v) then
printExpression(T, T.right(v))
if T.isInternal(v) then
print ")"
7.3.7 템플릿 메소드 패턴
위에서 설명한 트리 순회 방법은
실제로 흥미로운 객체 지향 소프트웨어 설계 패턴인 템플릿 메소드 패턴의 예이다.
템플릿 메소드 패턴은 특정 단계를 재정의하여
특정 애플리케이션에 특화될 수 있는 일반적인 계산 메커니즘을 설명한다.
템플릿 메소드 패턴에 따라
이진 트리의 일반적인 오일러 순회를 구현하는 알고리즘을 설계한다.
이 알고리즘은 templateEulerTour라고 하며 코드 조각 7.28에 나와 있다.
코드 조각 7.28:
템플릿 메소드 패턴을 따르는 노드 v에 루트를 둔
이진 트리 T의 하위 트리에 대한 오일러 투어이다.
Algorithm templateEulerTour(T, v):
r ← new object of type TourResult
visitLeft(T, v, r)
if T.hasLeft(v) then
r.left ← templateEulerTour(T, T.left(v))
visitBelow(T, v, r)
if T.hasRight(v) then
r.right ← templateEulerTour(T, T.right(v))
visitRight(T, v, r)
return r.out
메소드 templateEulerTour는 노드 v에서 호출할 때
순회의 다른 단계에서 여러 다른 보조 메소드를 호출한다. 즉
• TourResult 타입의 지역 변수 r을 만든다.
이것은 계산의 중간 결과를 저장하는 데 사용되고 왼쪽, 오른쪽 및 오른쪽 필드가 있다.
• 보조 메소드 visitLeft(T,v,r)를 호출하여 왼쪽의 노드와 관련된 계산을 수행한다.
• v에 왼쪽 자식이 있는 경우에는
v의 왼쪽 자식을 재귀적으로 호출하고 반환된 값을 r.left에 저장한다
• visitBelow(T, v, r)에서 보조 메소드를 호출한다.
이 메소드는 아래에서 노드를 접하는 것과 관련된 계산을 수행한다
• v에 오른쪽 자식이 있는 경우에는
오른쪽 자식을 재귀적으로 호출하여 반환된 값을 r.right에 저장한다
• 보조 메소드 visitRight(T, v, r)를 호출한다.
이 메소드는 오른쪽 노드와 관련된 계산을 수행한다
• r.out을 반환한다.
메소드 templateEulerTour는 오일러 투어의 템플릿 또는 "스켈레톤"으로 볼 수 있다.
(코드 조각 7.28 참조)
자바 구현
코드 조각 7.29에 표시된 Java 클래스 EulerTour는
템플릿 메소드 패턴을 사용하여 Euler tour 순회를 구현한다.
재귀 순회는 메소드 eulerTour에 의해 수행된다.
eulerTour에 의해 호출된 보조 메소드는 빈 자리 표시자이다.
즉, 이 메소드는 빈 본문을 가지거나 null로 반환된다.
클래스 EulerTour는 추상적이므로 인스턴스화할 수 없다.
여기에는 execute라는 추상적 메소드가 포함되어 있으며,
이 메소드는 EulerTour의 구체적인 하위 클래스에 지정되어야 한다.
필드가 left, right 및 out인 클래스 TourResult가 표시되지 않다.
코드 조각 7.29:
이진 트리의 일반적인 오일러 투어를 정의하는 자바 클래스 EulerTour.
이 클래스는 템플릿 방법 패턴을 실현하며
흥미로운 계산을 얻기 위해 전문화되어야 한다.
/**
* Template for algorithms traversing a binary tree using an Euler
* tour. The subclasses of this class will redefine some of the
* methods of this class to create a specific traversal.
*/
public abstract class EulerTour<E, R> {
protected BinaryTree<E> tree;
/** Execution of the traversal. This abstract method must be
* specified in a concrete subclass. */
public abstract R execute(BinaryTree<E> T);
/** Initialization of the traversal */
protected void init(BinaryTree<E> T) { tree = T; }
/** Template method */
protected R eulerTour(Position<E> T) {
TourResult<R> r = new TourResult<R>();
visitLeft(v, r);
if (tree.hasLeft(v))
r.left = eulerTour(tree.left(v)); // recursive traversal
visitBelow(v, r);
if (tree.hasRight(v))
r.left = eulerTour(tree.right(v)); // recursive traversal
visitRight(v, r);
return r.out;
}
// Auxiliary methods that can be redefined by subclasses:
/** Method called for the visit on the left */
protected void visitLeft(Position<E> v, TourResult<R> r) {}
/** Method called for the visit on the below */
protected void visitBelow(Position<E> v, TourResult<R> r) {}
/** Method called for the visit on the right */
protected void visitRight(Position<E> v, TourResult<R> r) {}
}
클래스인 EulerTour 자체는 유용한 계산을 수행하지 않는다.
그럼에도 불구하고 이를 확장하고
빈 보조 메소드를 재정의하여 유용한 작업을 수행할 수 있다.
산술 수식 트리를 사용하여 이 개념을 설명한다(예 7.9 참조).
산술 수식 트리가 각 노드에서
ExpressionTerm 타입의 객체를 갖는다고 가정한다.
클래스 ExpressionTerm에는
(변수의 경우) ExpressionVariable과
(연산자의 경우) ExpressionOperator 하위 클래스가 있다.
다시 클래스 ExpressionOperator에는
AdditionOperator와 MultiplicationOperator와 같은
산술 연산자의 하위 클래스가 있다.
메소드 ExpressionTerm의 값은 해당 하위 클래스에 의해 무시된다.
변수의 경우 변수의 값을 반환한다.
연산자의 경우 연산자를 피연산자에 적용한 결과를 반환한다.
연산자의 피연산자는 메소드 setOperands의 ExpressionOperator로 설정된다.
코드 조각 7.30에서 클래스 ExpressionTerm, ExpressionVariable,
ExpressionOperator 및 AdditionOperator를 보여준다.
코드 조각 7.30:
산술 수식의 변수, 일반 연산자 및 덧셈 연산자에 대한 클래스이다.
/** Class for a term (operator or variable) of an arithmetic expression. */
public class ExpressionTerm {
public Integer getValue() { return 0; }
public String toString() { return new String(""); }
}
/** Class for a variable of an arithmetic expression. */
public class ExpressionVariable extends ExpressionTerm {
protected Integer var;
public ExpressionVariable(Integer x) { var = x; }
public void setVariable(Integer x) { var = x; }
public Integer getValue() { return var; }
public String toString() { return var.toString(); }
}
/** Class for an operator of an arithmetic expression. */
public class ExpressionOperator extends ExpressionTerm {
protected Integer firstOperand, secondOperand;
public void setOperands(Integer x, Integer y) {
firstOperand = x;
secondOperand = y;
}
}
/** Class for the addition operator of an arithmetic expression. */
public class AdditionOperator extends ExpressionOperator {
protected Integer getValue() {
return (firstOperand + secondOperand); // unboxing and then autoboxing
}
public String toString() { return new String("+"); }
}
코드 조각 7.31 및 7.32에서는
이진 트리에 저장된 산술 식을 평가하고 인쇄하는 클래스 EvalueExpressionTour와
EulerTour를 전문으로 하는 PrintExpressionTour를 보여준다.
클래스 EvaluateExpressionTour는
다음 계산을 통해 보조 방법 visitRight(T, v, r)를 재정의한다:
• v가 외부 노드인 경우 r.out을 v에 저장된 변수의 값과 같게 설정한다
• 그렇지 않으면 (v는 내부 노드),
r.left 및 r.right를 v에 저장된 연산자와 결합하고
r.out을 연산의 결과와 동일하게 설정한다.
클래스 PrintExpressionTour는
코드 조각 7.27에 표시된 의사 코드 버전의 접근 방식에 따라
visitLeft, visitBelow 및 visitRight 메소드를 재정의한다.
코드 조각 7.31: 산술 표현 트리의 표현식을 평가하기 위해
오일러 투어를 전문으로 하는 클래스 EvaluateExpressionTour.
/** Class for a term (operator or variable) of an arithmetic expression. */
public class ExpressionTerm {
public Integer getValue() { return 0; }
public String toString() { return new String(""); }
}
/** Compute the value of an arithmetic expression tree. */
public class EvaluateExpressionTour extends EulerTour<ExpressionTerm, Integer> {
public Integer execute(BinaryTree<ExpressionTerm> T) {
init(T); // calls method of superclass
return eulerTour(tree.root()); // returns the value of the expression
}
protected void visitRight(Position<ExpressionTerm> v, TourResult<Integer> r) {
ExpressionTerm term = v.element();
if (tree.isInternal(v)) {
ExpressionOperator op = (ExpressionOperator) term;
op.setOperands(r.left, r.right);
}
r.out = term.getValue();
}
}
코드 조각 7.32: 산술 표현 트리와 관련된 표현을 인쇄하기 위해
오일러 투어를 전문으로 하는 클래스 PrintExpressionTour.
/** Priht out the expression stored in an arithmetic expression. */
public class PrintExpressionTour extends EulerTour<ExpressionTerm, String> {
public String execute(BinaryTree<ExpressionTerm> T) {
init(T);
System.out.print("Expression: ");
eulerTour(T.root());
System.out.println();
return null; // nothing to return
}
protected void visitLeft(Position<ExpressionTerm> v, TourResult<Integer> r) {
if (tree.isInternal(v)) System.out.print("("); }
protected void visitBelow(Position<ExpressionTerm> v, TourResult<Integer> r) {
System.out.print(v.element()); }
protected void visitLeft(Position<ExpressionTerm> v, TourResult<Integer> r) {
if (tree.isInternal(v)) System.out.print(")"); }
}'프로그래밍 공부 > Data Structure' 카테고리의 다른 글
| 9장 맵과 딕셔너리(1) (1) | 2023.12.31 |
|---|---|
| 8장 우선순위 큐 (4) | 2023.12.31 |
| 7장 트리(1) (2) | 2023.12.29 |
| 6장 리스트와 반복자 (1) | 2023.12.22 |
| 5장 스택과 큐 (1) | 2023.12.20 |