Win Tree

Win Tree는 Binary Tree의 일종으로, Leaf Node끼리 비교 후 작은값이 승자로 부모노드가 되는 Tree입니다.

 

8개 Element에 대한 추상화된 Win Tree

Heap과 유사해 보이지만, 실질적으로 Distinct한 Element는 Leaf Node만큼만 있다는 것을 알 수 있습니다.

 

이때, 각 Leaf Node에 이미 Sort된 List를 연결하면, 다수의 List를 하나로 정렬하는 것이 가능합니다.

 

각 Leaf Node에 정렬된 List를 연결한 모습을 추상화

이제, Win Tree에서 Top Node에 위치한 값을 Orderd List에 넣고, 해당 Leaf Node의 다음 값을 가지고 옵니다.

 

Win Tree를 이용해서 다수의 List를 정렬

이런 방식으로 모든 List가 Empty가 될 때 까지 반복을 진행하면, Leaf Node에 붙어있던 모든 List가

 

하나로 통합된 Ordered List로 통합되게 됩니다.

 

각 Element를 삽입할 때 모든 원소를 비교하는것이 아니라, Tree의 Depth 만큼만 비교하면 되기 때문에

 

효율적인 통합정렬 알고리즘이라고 할 수 있겠습니다.

 

Python으로 구현된 Win Tree와 Win Tree를 이용한 통합정렬 소스코드입니다 :)

import math

class win_tree:
    def __init__(self, DT_list):
        self.ori_data = DT_list
        self.list_count = len(self.ori_data)
        #save temporay win tree for sort
        self.result_list = []
        self.ordered_list = []
        self.max_len = 0
        self.start_index = 0
        
    
    def make_result_list(self):
        n = 0
        while True:
            if pow(2,n)>=self.list_count:                
                break
            else:
                n = n+1
        #make complete binary Tree list        
        for self.start_index in range(pow(2,n-1)):
            if (pow(2,n-1) -1 + self.start_index)*2+1 < (pow(2,n-1) -1 + self.start_index) + self.list_count:
                pass
            else:
                break
        self.start_index = pow(2,n-1) -1 + self.start_index
        self.result_list = [9999]*(self.start_index + self.list_count)
        for i in range(self.list_count):
            self.result_list[-i-1] = self.ori_data[-i-1][0]
            del(self.ori_data[-i-1][0])
        self.max_len = len(self.result_list)
            
    
    def merge_sort(self):        
        #make first time Win Tree(Full Element Compare)
        for i in range(len(self.result_list)):                      
            if self.result_list[math.floor(((self.max_len - i -1) -1)/2)] == 9999:
                if math.floor(((self.max_len - i -1)-1)/2)*2+2 > self.max_len-1:
                    if math.floor(((self.max_len - i -1)-1)/2)*2+1 < self.max_len-1:
                        self.result_list[math.floor(((self.max_len - i -1)-1)/2)] = self.result_list[math.floor(((self.max_len - i -1)-1)/2)*2+1]                    
                elif self.result_list[math.floor(((self.max_len - i -1)-1)/2)*2+1] < self.result_list[math.floor(((self.max_len - i -1)-1)/2)*2+2]:
                    self.result_list[math.floor(((self.max_len - i -1)-1)/2)] = self.result_list[math.floor(((self.max_len - i -1)-1)/2)*2+1]
                else:
                    self.result_list[math.floor(((self.max_len - i -1)-1)/2)] = self.result_list[math.floor(((self.max_len - i -1)-1)/2)*2+2]
        self.ordered_list = self.ordered_list + [self.result_list[0]]
        for i in range(self.list_count):            
            if self.result_list[-i-1] == self.result_list[0]:
                self.result_list[-i-1] = self.ori_data[-i-1][0]
                del(self.ori_data[-i-1][0])
                break        
        #after make full win tree, just compare only remove node
        while True:
            index = self.max_len - i -1
            while True:
                if math.floor((index-1)/2)<0:
                    break
                else:
                    if self.result_list[math.floor((index-1)/2)*2 +1]<self.result_list[math.floor((index-1)/2)*2 +2]:
                        self.result_list[math.floor((index-1)/2)] = self.result_list[math.floor((index-1)/2)*2 +1]
                    else:                    
                        self.result_list[math.floor((index-1)/2)] = self.result_list[math.floor((index-1)/2)*2 +2]                    
                index = math.floor((index-1)/2)            
            for i in range(self.list_count):                            
                if self.result_list[-i-1] == self.result_list[0]:
                    #if the original list is empty, fill 9999 at leafnode
                    if len(self.ori_data[-i-1]) == 0:
                        self.result_list[-i-1] = 9999
                    else:
                        self.result_list[-i-1] = self.ori_data[-i-1][0]
                        del(self.ori_data[-i-1][0])
                    break
            if self.result_list[index]== 9999:
                break
            else:
                self.ordered_list = self.ordered_list + [self.result_list[0]]
            

        
import random
import copy
#Generate random ordered list, number of leaf node
test_data = []
for _ in range(6):
    DT_list = [random.randint(0,100) for i in range(7)]    
    DT_list.sort()
    test_data = test_data + [DT_list]

test = win_tree(test_data)
#make win_tree frame
test.make_result_list()
#make Integrated Ordered List
test.merge_sort()
#validate the ordered List
test.ordered_list
[2, 2, 5, 10, 12, 15, 15, 17, 18, 23, 24, 25, 28, 32, 34, 34, 34, 38, 38, 39, 41, 44, 46, 48, 51, 51, 55, 58, 60, 64, 65, 68, 68, 76, 76, 79, 84, 85, 85, 87, 89, 94]