[Data Structure] Tree - 기본 정의 및 용어 && Python 리스트로 트리 표현하기

Tree

---

목적

1. tree 자료구조가 무엇인지 이해하고, 어떻게 사용되는지 이해한다.

2. 어떻게 tree가 map 자료구조로 실행되는지 본다.

3. tree를 리스트를 통해 실행한다.

4. 클래스와 레퍼런스를 이용해서 tree르 실행하여본다.

5. 재귀적 자료 구조로서 tree를 실행한다.

6. 힙을 이용하여서, Priority Queue로 실행하여 본다.

특징

1. tree 자료구조는 root와 그것의 leaves를 가지고 있다.

2. tree의 특성

1. 계층화

2. 한 node의 children은 또 다른 node의 children과 독립적이다.

3. 각각의 node는 unique 하다.

4. subtree를 더 아래 level의 계층에 영향을 주지 않고, tree의 다른 position으로 옮길 수 있다.

용어

1. Node

   • tree의 메인 파트이다. 추가적인 정보를 가지는데, payload라고 부른다.

2. Edge

   • 두개의 node를 연결짓는 역할을 한다.

3. Root

   • tree의 root는 incoming edge만 있는 유일한 node이다.

4. Path

   • edge로 연결된 node의 정렬된 list를 말한다.

5. Children

   • 같은 node로 부터 incoming edge를 가진 node 집합을 children이라 한다.

6. Parent

   • 한 node는 모든 node의 parent이고, outgoing edge로 연결되어 있다.

7. Sibling

   • 같은 parent 안의 children을 sibling 이라고 한다.

8. Subtree

   • subtree는 node와 edge의 모음인데, parent와 그 parent의 모든 자손들로 이루어져 있다.

9. Leaf Node

   • Children이 없는 node

10. Level

    • root node로부터 특정 node 까지의 edge의 개수

11. Height

• tree의 height는 tree의 maximum level을 말한다.

정의

1. node 끼리 연결짓는 node와 edge 모음으로 구성된다.

   • tree의 node 중 하나는 root node 이다.

   • root를 제외한 모든 node n은 하나의 다른 node p의 edge에 의해 연결되는데, 여기서 p는 n 의 상위 node이다. - root 만 parent node가 없다.

   • root에서 각 node로의 경로는 모두 unique 하다.

   • tree에서 각 node가 최대 2개의 children을 가지면 이것을 binary tree 라고 한다.

2. tree는 empty 이거나 root만 있거나 root에 subtree가 있을 수 있다. root의 각 subtree는 parent의 root로 연결되어 있다.

Tree를 Python 리스트로 표현하기

---

다음과 같은 Tree가 있을 때, 이것을 리스트로 표현하면 다음과 같다.

myTree = [ 'a',
          ['b',
                ['d',[],[]],
                ['e',[],[]]
          ],
          ['c',
                ['f',[],[]],
                []
          ]
        ]

위의 리스트로 표현된 tree는 다음과 같은 특징을 가진다.

1. list indexing으로 subtree에 접근 할 수 있다.

2. Nice한 특징 중 하나는 subtree를 표현하는 리스트 구조가 tree으 지어의를 고수하면서 구조자체가 재귀적으로 반복되는 것이다.

3. 또 다른 Nice한 특징은 많은 subtree를 가진 Tree로써, 일반화 될 수 있다는 것이다.

myTree = ['a', ['b', ['d',[],[]], ['e',[],[]] ], ['c', ['f',[],[]], []] ]
print(myTree)
print('left subtree = ', myTree[1])
print('root = ', myTree[0])
print('right subtree = ', myTree[2])
​
​
#결과
['a', ['b', ['d', [], []], ['e', [], []]], ['c', ['f', [], []], []]]
left subtree =  ['b', ['d', [], []], ['e', [], []]]
root =  a
right subtree =  ['c', ['f', [], []], []]
​

Binary Tree를 위와 같은 방식으로 공식화 해서 함수로 나타내면 다음과 같다.

def BinaryTree(r):
    return [r, [], []]
​
def insertLeft(root, newBranch):
    t = root.pop(1) #root list를 말함
    if len(t) > 0: #값이 존재하면,
        root.insert(1, [newBranch, t, []])
    else:
        root.insert(1, [newBranch,[],[]])
​
def insertRight(root, newBranch):
    t = root.pop(2) #root list를 말함
    if len(t) > 0: #값이 존재하면,
        root.insert(2, [newBranch, t, []])
    else:
        root.insert(2, [newBranch,[],[]])
​
def getRootVal(root):
    return root[0]
​
def setRootVal(root, newVal):
    root[0] = newVal
​
def getLeftChild(root):
    return root[1]
​
def getRightChild(root):
    return root[2]

r = BinaryTree(3) #3을 루트로 가지는 Binary Tree를 생성
insertLeft(r,4) #root의 LeftChild로 4를 넣는다.
insertLeft(r,5) #root의 LeftChild로 5를 넣는다.
insertRight(r,6) #root의 RightChild로 6를 넣는다.
insertRight(r,7) #root의 RightChild로 7를 넣는다.
l = getLeftChild(r)
print(l)
​
setRootVal(l,9)
print(r)
insertLeft(l,11)
print(r)
print(getRightChild(getRightChild(r)))
​
#결과
​
[5, [4, [], []], []]
[3, [9, [4, [], []], []], [7, [], [6, [], []]]]
[3, [9, [11, [4, [], []], []], []], [7, [], [6, [], []]]]
[6, [], []]

Exercise

Q-53: Given the following statments:

x = BinaryTree('a')
insertLeft(x,'b')
insertRight(x,'c')
insertRight(getRightChild(x),'d')
insertLeft(getRightChild(getRightChild(x)),'e')

Which of the answers is the correct representation of the tree?

(A) ['a', ['b', [], []], ['c', [], ['d', [], []]]] (B) ['a', ['c', [], ['d', ['e', [], []], []]], ['b', [], []]] (C) ['a', ['b', [], []], ['c', [], ['d', ['e', [], []], []]]] (D) ['a', ['b', [], ['d', ['e', [], []], []]], ['c', [], []]]

Write a function buildTree that returns a tree using the list of lists functions that looks like this:

def buildTree():
    r = BinaryTree('a')
    insertLeft(r, 'b')
    insertRight(r, 'c')
    insertRight(getLeftChild(r), 'd')
    insertLeft(getRightChild(r), 'e')
    insertRight(getRightChild(r),'f')
    
    return r
​
ttree = buildTree()
​
# 결과 확인
​
print(getRootVal(getRightChild(ttree)) == 'c') # True
print(getRootVal(getRightChild(getLeftChild(ttree))) == 'd') # True
print(getRootVal(getRightChild(getRightChild(ttree))) == 'f') # True