ch.7 Tree 자료구조

7.1 General Trees

Tree : 비선형 자료구조의 하나 (Non-linear Data structure)

tree를 사용하면 list, vector, sequence와 같은 linear data structure들을 사용할 때보다 더 빠른 알고리즘의 구현을 가능케 하기 때문이다.

Definition of 'Tree' : 트리는 원소들을 계층적으로 저장하는 추상 데이터 타입(Abstract Data Type)이다.

트리는 또한 자료에 대해 자연스러운 조직을 제공하므로 결과적으로 파일 시스템, 그래픽 사용자 환경, 데이터베이스, 웹 사이트, 그리고 다른 컴퓨터 시스템 등에서 어디에나 존재하는 구조가 되었다.

생산성 전문가들이 말하는 비선형적인(non-linear) 생각이 무엇인지 항상 명확한 것은 아니지만, 트리가 비선형적이라고 말할 때, 우리는 시퀀스 상의 두 오브젝트 사이의 단순한 전후관계보다는 좀 더 풍부한 조직 관계를 의미한다.

어떤 object들은 다른 object들의 상위에, 어떤 object들은 다른 object들의 하위에 있을 수 있도록 트리에서의 관계는 **계층적(hierarchical)**이다.

7.1.1 Tree Definitions and Properties

top element를 제외한 모든 element는 하나의 parent(부모) element와 0 또는 여러개의 childrent(자식) element를 가지고 있다.

root : 우리는 일반적으로 가장 높은 위치에 그려지고 아래에 연결된 다른 원소들을 갖는 top element를 tree의 root라고 부른다.

Formal Tree Definition

정규적으로? 형식적으로, tree T는 아래와 같은 속성들을 따르며, 각 element들이 parent-child의 관계로 저장되는 node들의 집합이다.

• 만약 tree T가 비어있지 않다면, T는 T의 root라고 불리는 특별한 노드 r을 가진다. root는 parent가 없다.
• root가 아닌 각 node v는 하나의 parent node w를 갖는다. parent node w를 갖는 모든 node들은 w의 child라고 한다.

Tree의 재귀적 정의 Recursive Definition of Tree

위 정의에 따르면 tree는 empty일 수 있다. = 트리는 아무 노드도 없을 수 있다.

이러한 관례를 따라, 우리는 tree를 recursively(재귀적으로) 정의할 수 있다.

=⇒ 트리 T는 empty이거나, T의 root node인 r과 r의 자식들을 root로 가지는 다른 tree들의 집합으로 구성될 수 있다.

Other Node Relationships

siblings : 동일한 parent를 가진 childrent node들을 siblings(형제) 라고 한다.

external : node v가 children이 없으면 v는 external이다. external nodes는 leaves라고도 부른다. (leaf)

internal : node v가 children이 하나라도 있으면 v는 internal이다.

ancestor & descendant :

• node u는 node v의 ancestor(조상)이다. ⇒ u=v이거나, u가 v 부모의 조상일 때
• 그 때, node v는 node u의 descendant(후손)이다.

edge & path

• edge of tree T : a pair of noeds(u, v) such that u is the parent of v, or vice versa
• a path of T : sequence of nodes such that any two consecutive nodes in the sequence form an edge. path는 sequence of node들인데, 여기서 인접한 두 노드는 edge를 형성한다.

Ordered Trees

각 node의 child들을 위한 linear ordering(선형 순서)가 정의되어 있다면, 즉, 한 노드의 child를 첫 번째, 두 번째, 세 번째 등으로 식별할 수 있다면 그 **tree가 ordered(순서화)**되었다고 한다.

7.1.2 Tree Functions

Tree ADT는 tree의 node들에 원소(element)를 저장한다.

node들은 우리의 implementations의 internal aspects이므로 node에 직접적으로 접근하는 것을 허락하고 싶지 않다!!

대신에 tree의 각 node와 연관된(associated) position object를 사용하여 node에 public access를 한다.

cf) 이러한 이유 때문에 우리 ADT의 public interface를 논의할 때, 함수에 대한 인수(argument)가 노드가 아니라 position이라는 것을 강조하기 위해 변수로 p를 사용한다. 그러나 이들 두 object가 밀접하게 연결되어 있기 때문에, 그들의 구분이 애매하여 트리에서는 position과 node라는 용어를 같이 사용한다.

(use the terms "position" and "node" interchangeably for trees)

• dereferencing operator ("*")를 operator overloading 하여 사용한다.
  • Ex) position variable p가 주어지면 associated element는 *p로 접근
• position의 collections를 저장하면 유용하다. 예를들면, 트리에서 어떤 노드의 children을 그런 list로 표현할 수 있다. ⇒position list를 tree positions를 element로 갖는 리스트로 정의한다.

tree position의 진정한 힘 : tree에서 인접 원소에 접근할 수 있는 능력

tree T의 position p가 주어지면 다음과 같은 함수들을 정의한다.

p.parent() : p의 parent를 반환. p가 root이면 error

p.children() : p의 children을 포함하는 position list를 반환한다.

p.isRoot() : p가 root이면 true를 return. 아니면 false를 return

p.isExternal() : p가 external node이면 true를 아니면 false를 return

만약 tree가 ordered(순서화) 되었다면, p.childrent()이 반환하는 list는 p의 child node에 대해 순서대로 접근하는 것을 제공한다. 만약 p가 external node이면 p.children()은 empty list를 반환

Tree 자신은 다음 함수들을 제공한다.

size() : 트리 내 노드의 개수를 반환

empty() : 트리가 empty면 True를, 아니면 False를 반환

root() : 트리의 root에 대한 position를 반환한다. ; tree가 empty이면 error

positions() : 트리의 모든 node의 position list를 반환

7.1.3 A C++ Tree Interface

본 절에서는 트리 ADT를 위한 비정규적인(informal) C++ interface를 설명한다.

우선 Tree에서 위치를 나타내는 클래스 position을 위한 informal C++ interface를 프로그램 코드 7.1에 제시한다.

// Code Fragment 7.1 : An informal interface for a position in a tree (not a complete C++ class)

 

template <typename E>     //base element type E로 
template class Position<E> {     // a node position 
	public: 
    	E& operator*(); //get element. E type을 reference로 반환. operator overloading 
        Position Parent() const; // get parent. parent node의 position을 반환 
        PositionList children() const; //get node's children; child node들을 list 형태로 반환 
        bool isRoot() const; // root node? 
        bool isExternal() const; // external node?
};

다음으로, 프로그램 코드 7.2에 informal(비정규적인) C++ interface를 제시하였다.

 

interface를 가능한 한 간단히 하기 위해, 에러 처리는 무시하였다; 따라서 예외 선언(throwing exception)하지 않았다.

 

template <typename E> // base element type E class Tree<E> { // templated class Tree public: // public types class Position; //a node position class PositionList; //a list of positions 이런 타입을 갖는 다는 거야? 아니면 nested class declaration인거야? public: // public functions int size() const; // number of nodes bool empty() const; // is tree empty? Position root() const; //get the root=> root의 position 반환 ( copy return ) PositionList positions() const; // get the positions of all nodes => position list 형태로 반환

template <typename E> // base element type E 
class Tree<E> { // templated class Tree 
	public: // public types 
    	class Position; //a node position 
        class PositionList; //a list of positions 이런 타입을 갖는 다는 거야? 아니면 nested class declaration인거야? 
    public: // public functions 
        int size() const; // number of nodes 
        bool empty() const; // is tree empty? 
        Position root() const; //get the root=> root의 position 반환 ( copy return ) 
        PositionList positions() const; // get the positions of all nodes => position list 형태로 반환
};

여기서 우리는 PositionList 클래스를 위한 interface를 formally 정의하지 않았지만, PositionList가 standard List ADT일 것이라고 가정한다.

즉, 우리 코드 예제에서 PositionList가 base type이 Position 오브젝트인 STL List 로 구현되었다고 가정.

좀더 구체적으로는 "std::list<Position>" 사용

특히 PositionList가 Iterator type을 제공한다고 가정하고, 다음 예들에서는 단순히 Iterator라고 부른다.