공부 기록

[자료구조] 이진 트리

by 너나나

2022/자료구조 + 알고리즘

이진 트리

: 모든 노드가 최대로 두 개의 자식 노드를 갖는 순서화된 트리

  1. 각 노드가 최대 2개의 자식을 갖는다.
  2. 각 노드가 자식을 왼쪽 자식 또는 오른쪽 자식으로 분류한다.
  3. 왼쪽 자식이 오른쪽 자식보다 먼저 오도록 순서화되었다.

각 노드가 0개 또는 2개의 자식을 가지면 이진 트리가 프로퍼(proper)하다고 한다. 경우에 따라 이러한 트리를 풀(full) 이진 트리라고 한다. => 프로퍼 이진 트리에서는 모든 내부 노드는 정확히 두 개의 자식을 가진다!!

 

산술식 트리(arithmetic expression tree)

(2 x (a - 1)) + (3 x b)

외부 노드: 변수 or 상수

내부 노드: +, -, x, /

+, -, x, / 의 연산자는 실질적으로 두 개의 피연산자를 가짐

=> 산술식은 프로퍼(proper) 이진 트리! 물론 -x 같은 단일 연산자를 허용한다면 improper 이진 트리를 가질 수 있음

결정 트리(decision tree)

내부 노드: yes/no로 답할 수 있는 질문

외부 노드: 결정

 

이진 트리 특성

트리 T에서 같은 깊이 d를 갖는 모든 노드의 집합을 T의 레벨 d라고 한다!

레벨 0은 하나의 노드(루트)를 가짐

레벨 1은 최대 두 개의 노드를 가짐!

... => 레벨 d는 최대 2^d개의 노드를 가짐!!!

 

이진 트리를 위한 링크드 구조

만약 v가 T의 루트이면 부모 노드로의 포인터는 NULL이다. 만약 v가 외부노드이면 v의 자식들을 가르키는(left, right) 포인터가 NULL이다.

이진 트리를 표현하는 링크드 자료 구조의 예

C++ 코드로 작성해보자!!

struct Node {	// 트리의 노드
    Elem elt;	// 원소 값
    Node* par;	// 부모
    Node* left;	// 왼쪽 자식
    Node* right;	// 오른쪽 자식
    Node() : elt(), par(NULL), left(NULL), right(NULL);	// 생성자
};
class Position {		// 트리에서의 위치
private:
	Node* v;			// 노드를 가리키는 포인터
public:
    Position(Node* _v = NULL): v(_v) {}	// 생성자
    Elem& operator*() {	// 원소를 반환
    	return v -> elt; }
    Position left() const { 
    	return Position(v->left); }	// 왼쪽 자식 반환
    Postion right() const {
    	return Position(v->right); }	// 오른쪽 자식 반환
    Position parent() const {
    	return Position(v->par);}	// 부모 반환
    bool isRoot() const {
    	return v->par == NULL; }	// 루트인지
    bool isExternal() const {
    	return v->left == NULL && v->right == NULL; }	// 외부 노드인지
    friend class LinkedBinaryTree;	// 트리를 접근할 수 있게 한다
};
typedef std::lift<Position> PositionList;	// 위치의 리스트
typedef int Elem;
class LinkedBinaryTree {
protected:
    // Node 선언을 여기에
public:
    // Position 선언을 여기에
public:
    LinkedBinaryTree() : _root(NULL), n(0);	// 생성자
    int size() const { return n; }	// 노드의 개수
    bool empty() const { return size() == 0; }	// 트리가 비었는지
	Position root() const { return Position(_root); }	// 루트를 구함
    PositionList positions() const {	// 노드의 리스트
    	PositionList pl;
        preorder(_root, pl);	// 전위 순회
       	return PositionList(pl);	// 결과 리스트 반환
    }
    void addRoot(){	// 빈 트리에 루트 추가
    	_root = new Node;
        n = 1;
    }
    void expandExternal(const Position& p) {	// 외부 노드를 확장
    	Node* v = p.v;	// p의 노드
        v->left = new Node;	// 새 왼쪽 자식을 추가
       	v->left->par = v;	// v가 부모
        v->right = new Node;	// 새 오른쪽 자식을 추가
        v->right->par = v;	// v가 부모
        n += 2;	// 노드 개수는 2 증가
    }
    Position removeAboveExternal(const Position& p){	// p와 부모를 삭제
    	Node* w = p.v;
        Node* v = w->parent;	// p의 노드와 부모를 구함
        Node* sib = (w == v->left ? v->right : v->left);	// 형제를 구함
        if (v == _root) {
            _root = sib;	// 부모가 루트인 노드였다면 루트를 자기 형제로 바꿈
            sib->par = NULL;
        }
        else {
            Node* gpar = v->par;	// v의 조부모
            if (v == gpar->left) gpar->left = sib;	// 부모 자리에 p의 형제를 넣음
            else gpar->right = sib;
            sib->par = gpar;
        }
        delete w; delete v;
        n -= 2;	// 제거된 노드의 메모리를 반환
        return Position(sib);	// 노드 개수를 2 감소
    }
protected:
    void preorder(Node *v, PositionList& pl) const {	// 전위 순회
    	pl.push_back(Position(v));	// 이 노드를 추가
    	if (v->left != NULL)	// 왼쪽 서브트리를 순회
    	    preorder(v->left, pl);
        if (v->right != NULL)	// 오른쪽 서브를트리를 순회
            preorder(v->right, pl);
    }
private:
    Node* _root;
    int n;

};

이진 트리의 갱신 함수들

removeAboveExternal(p)

  • expandExternal(p): 두 개의 새로운 외부 노드를 생성하면서, 그들을 각각 p의 왼쪽과 오른쪽 자식 노드로 만들어 외부 노드 p를 내부 노드 p로 변환한다. 만약 p가 내부 노드이면 에러가 발생한다.
  • removeAboveExternal(p): 외부 노드 p를 부모 q와 함께 제거하고 q 대신 p의 형제(sibling)으로 대체한다. 만약 p가 내부 노드이거나 p가 루트이면, 이 연산자는 에러 조건을 생성한다.

 

이진 트리를 위한 벡터 기반 구조

이진 트리 T를 표현하기 위한 간단한 구조는 T의 노드들에 번호를 매기는 방법에 기초한다. T의 모든 노드 v에 대해서 f(v)는 다음과 같이 정수로서 정의된다!

  • 만약 v가 T의 루트이면, p(v) = 1
  • 만약 v가 노드 u의 왼쪽 자식이면, f(v) = 2f(u)
  • 만약 v가 노드 u의 오른쪽 자식이면, f(v) = 2f(u) + 1

 

이진 트리 순회

  • 이진 트리의 전위 순회 
    Algorithm binaryPreorder(T, p):
    perform the "visit" action for node p
    if p is an internal node then
    	binaryPreorder(T, p.left())	 왼쪽 서브트리를 재귀적으로 순회
        binaryPreorder(T, p.right()) 오른쪽 서브트리를 재귀적으로 순회​
    일반 트리에 대한 전위 순회와 같다!! 여기서 p는 루트 노드이다.
  • 이진 트리의 후위 순회 
    Algorithm binaryPostorder(T, p):
    if p is an internal node then
    	binaryPostorder(T, p.left())	왼쪽 서브트리를 재귀적으로 순회
        binaryPostorder(T, p.right())	오른쪽 서브트리를 재귀적으로 순회
    perform the "visit" action for the node p​
    얘도 일반 트리에 대한 후위 순회와 같다.
  • 산술식 평가 
    Algorithm evaluateExpressiont(T, p):
    if p is an internal node then
    	x <- evaluateExpression(T, p.left())
        y <- evaluateExpression(T, p.right())
        let o be the operator associated with p
        return x o y
    else
    	return the value stored at p
    산술식 평가 문제(expression evaluation problem)을 해결하기 위해 후위 순회를 사용할 수 있다. p가 외부 노드라면 값이 들어있을 거니까 그대로 리턴하고 내부 노드라면 +, -, x, / 같은 연산자가 들어있을꺼니까 얘의 왼쪽 자식에서 리턴된 값과 오른쪽 자식에서 리턴된 값을 연산해서 리턴해준다!
  • 중위 순회(inorder): 한 노드의 왼쪽 서브트리에 대해 순회하고 그 노드를 방문하고 오른쪽 서브트리에 대해 순회한다. 그러니까 중위순회는 왼쪽 자식들 -> 루트 -> 오른쪽 자식들 이다!! 일반적으로 우리가 산술식을 표현할 때 2 x 4 이런식으로 상수 or 변수 - 연산자 - 상수 or 변수 이렇게 쓰는데 이게 바로 중위 표기법이다!!! 왼쪽 자식들 방문 -> 루트(연산자) 방문 -> 오른쪽 자식들 방문 인 것!! 
    Algorithm inorder(T, p):
    if p is an internal node then
    	inorder(T, p.left())	왼쪽 서브트리를 재귀적으로 순회
    perform the "visit" action for node p
    if p is an internal node then
    	inorder(T, p.right())	오른쪽 서브트리를 재귀적으로 순회​
    중위 순회를 사용하면 노드에 적힌 순서대로 방문한다!! 왼쪽 자식들 -&gt; 루트 -&gt; 오른쪽 자식들 순으로!!

 

중위 순회를 이용한 트리 그리기

이진 트리를 그리는 문제에 중위 순회를 적용할 수 있다.

위의 사진과 동일한 트리인데 x, y 좌표축을 이용해 좌표로 노드를 표현했다. 여기서 x 좌표는 중위 순회를 사용했을 때의 노드 방문 순서이고 y축은 노드의 깊이이다. 그래서 다음 두 가지 규칙을 이용하여 T의 노드 p에 대한 x-y 좌표를 할당하는 아고리즘을 가지고 이진 트리 T를 그릴 수 있다.

  • x(p)는 T의 중위 순회에서 p 이전에 방문된 노드의 수와 같다.
  • y(p)는 T 내에서 p의 깊이와 같다.

 

이진 트리의 오일러 투어 순회(Euler Tour Traversal)

저번 포스팅부터 지금까지 본 트리 순회 알고리즘은 모두 반복자의 형태이다. 각 순회는 특정한 순서로 트리의 노드들을 방문하며, 각 노드에 대해 정확하게 한 번씩 방문하는 것을 보장한다!! 각 노드가 정확히 한 번씩 방문된다는 요구 조건을 완화함으로써 주어진 트리 순회 알고리즘들을 단일의 프레임워크에 통합할 수 있다. 이 통합된 순회 함수를 오일러 투어 순회라고 부른다. 이 순회의 장점은 일반적인 종류의 알고리즘들을 쉽게 표현할 수 있다는 것이다. 오일러 투어 순회는 T 주위의 산책(walk)으로 간단하게 정의할 수 있다. 트리 주변을 아래 사진처럼 산책 하는데 이때 T의 각 노드 p는 오일러 투어에 의해 세번 만나게 된다. 트리 주변에 선을 긋게 되면 아래 사진의 L, B, R 부분 이렇게 세 번 방문하게 된다!!

이렇게!!

  • 왼쪽으로 (p의 왼쪽 서브 트리의 오일러 투어 전에)
  • 아래로 (p의 두 개의 서브 트리들의 오일러 투어 사이에 즉 왼쪽 서브 트리를 방문한 후에)
  • 오른쪽으로 (p의 오른쪽 서브 트리의 오일러 투어 후에)

이때 p가 외부 노드이면 이 세 개의 방문은 동시에 발생한다!!

Algorithm eulerTour(T, p):
    perform the action for visiting node p on the left
    if p is an internal node then
    	recursively tour the left subtree of p by calling eulerTour(T, p.left())
    perform the action for visiting node p from below
    if p is an internal node then
    	recursively tour the right subtree of p by calling eulerTour(T, p.right())
    perform the action for visiting node p on the right

이진 트리의 전위 순회는 각 노드를 왼쪽에서 만날 때 방문(visit) 동작을 실행하도록 하는 오이러 투어 순회와 동일한 연산 과정을 거친다.

마찬가지로 중위 순회와 후위 순회는 각 노드를 각각 아래로부터 또는 오른쪽에서 만날 때 방문 동작을 갖도록 한 오일러 투어 순회와 동일한 연산 과정을 거친다. 

참고 문헌

[1] Michael T. Goodrich, Roberto Tamassia, Davaid M. Mount, C++로 구현하는 자료구조와 알고리즘, WILEY, 2013.

저작자표시

'2022 > 자료구조 + 알고리즘' 카테고리의 다른 글

[자료구조] 힙  (0) 2022.01.18
[자료구조] 우선순위 큐  (0) 2022.01.16
[자료구조] 트리 순회 알고리즘 (전위, 후위)  (0) 2022.01.12
[자료구조] 분석 도구  (0) 2022.01.06
[자료구조] 링크드 리스트  (1) 2022.01.06

블로그의 정보

공부 기록

너나나

활동하기

티스토리툴바