스레드 이진트리 Threaded Binary Tress
스레드 이진 트리 : 스택을 이용하지 않고 포인터를 이용해 순회의 시간을 단축시키는 방식 (중위 순회 Inorder Traversal를 기본으로 한다)
-
n노드 이진 트리의 연결 표현
-
총 링크 수 : 2n (노드 하나마다 링크가 두개 씩 있으니까)
: n-1개의 노드만 들어오는 링크를 가지고 있다
: n+1개는 링크가 필요없는데 가지고 잇는 것 (널 링크 가지고 있다) -
0 링크 (null링크) 수 : n + 1 (binary tree의 특성에 의해)
→ 이진트리의 연결표현을 잘 살펴보면 실제 포인터보다 더 많은 널 링크가 있다! 안쓰는 링크가 아까우니 잘 써보자 ~
Thread 스레드
-
0 링크 필드에다가 다른 노드를 가리키는 포인터를 넣을 것이다 (다른 노드를 가리키는 포인터로 대치)
-
말단 노드 (leaf node)만 스레드가 될 수 있다 (child가 없는 노드들)
-
if p->rightChile == 0, p -> rightChild = p의 중위 후속자 (successor) 에 대한 포인터 -
if p->leftChild = 0, p -> leftChild = p의 중위 선행자 (precedor)에 대한 포인터
: Inorder traversal로 순서 따라갈 수 있어야 한다 ! HDIBEAFCG
-
노드 구조
스레드인지 노드인지 알기 위해 1bit 짜리 flag를 만들자 !
(스레드 : 빈 포인터를 가지고 inorder 후속자나 선행자를 포인팅하고 있는 것)leftThread == false : leftChild ← 포인터
leftThread == true : leftChild ← 스레드
righttThread == false : rightChild ← 포인터
rightThread == true : righttChild ← 스레드 -
헤드 노드를 달아보자
Inorder상 가장 왼쪽 노드의 leftChild 및 가장 오른쪽 노드의 rightChild가 가리키게 함
만약 empty하면 헤드 자체를 포인팅하게 만든다
: 헤드가 포함된 이진트리가 완성되는 것!
Inorder Traversal of a Threaded Binary Tree (LVR)
: 스택을 사용하지 않고 중위 순회가 가능 (Inorder Traversal)
: 중위 순회의 후속자 (Inorder successor)
x→rightThread == true 이면 x → rightChild
x→rightThread == false 이면 오른쪽 자식의 왼쪽 자식 링크를 따라가서 leftThread ==ture인 노드
- 스레드 이진 트리에서 중위 후속자를 Inorder successor를 찾는 함수
T* ThreadedInorderIterator::Next(){
ThreadedNode<T> *temp = currentNode -> rightChild;
// temp는 rightChild를 일단 따라가봐라
if(!currentNode->rightThread) // rightThread가 false면
while(!temp->leftThread) // 스레드가 아니니까 제일 처음에 나오는 걸 찾아라 (Inorder 순회를 할 때)
temp = temp->leftChild;
currentNode = temp;
if (currentNode == root) // 끝까지 왔구나
return 0; // 돌아가자
else return & currentNode->data; // 현재 데이터가 이거야 ~ 하고 돌려준다.
}- Inserting a Node into a Threaded Binary Tree
-
inserting r as the right child of a node s 노드 s의 오른쪽 child로 r 삽입하기 !
: insert하고싶으면 → 스레드를 유지를 해야겠네? → s에 오른쪽 child로 r을 넣어보자 → r의 left 스레드는 s가 되어야 한다 (= r은 s를 포인팅 해야 한다)
: 원래 s가 있던 자리를 밀어내고 r
-
삽입하는 상황을 알고리즘으로 구현하면 template<class T>
void ThreadedTree<T>::InsertRight(ThreadedNode<T> *s, ThreadedNode<T> *r){
r->rightChild = s->rightChild; // s의 오른쪽 child를 r의 오른쪽 child로 복사해 넣고
r->rightThread = s->rightThread; // s의 오른쪽 스레드를 r의 오른쪽 스레드로 복사해 넣고
r->leftChild = s; // r의 left child에 s를 넣고 (????)
r->leftThread = true; // 원래 없던 r의 left child가 true가 된다 (=leftChild가 스레드이다)
s->rightChild=r; // s의 rightChild는 r이 된다
s->rightThread = false; // s의 rightThread는 r이니까 false가 된다
if(!r->rightThread){ // 만약 r의 rightThread가 false이면 오른쪽 child가
ThreadedNode<T> *temp = InorderSucc(r);
}
}