이진 트리 탐색.

탐색 방법론.

어떻게 적을까 하다가 너무 잘되있는 블로그를 찾음.

http://blog.naver.com/PostView.nhn?blogId=4717010&logNo=60209820587&parentCategoryNo=4&categoryNo=&viewDate=&isShowPopularPosts=true&from=search

특징.

1. 이미 입력된 자료가 정렬되어 있다던지, 작은 값과 큰 값이 번갈아 나오는 경우에는 시간 복잡도가 순차 탐색과 같아진다.

# -*- encoding: cp949 -*-
import time
import random
import Queue
    
N = 10000
 
class Dict:
    class node:
        def __init__(self,k,ll,rr):
            self.key = k
            self.l = ll
            self.r = rr
    def __init__(self,max):
        self.z = self.node(0,0,0)
        self.z.l = self.z
        self.z.r = self.z
        self.head = self.node(0,0,self.z)
    def search(self, search_key):
        x = self.head.r
        while x!= self.z:
            if x.key == search_key: 
                return x.key
            if x.key > search_key:
                x = x.l
            else: x = x.r
        return -1
    def insert(self, v):
        p = self.head
        x = self.head.r
        while x != self.z:
            p = x
            if x.key == v: return
            if x.key > v:
                x = x.l
            else: x = x.r
        x = self.node(v,self.z,self.z)
        if p.key > v: p.l = x
        else: p.r = x

def init(key, search_key):
    temp = [0 for i in range(N+1)]
    for i in range(1,N+1):
        key[i] = i
        search_key[i] = i
    for i in range(1,N+1):
        index = random.randint(1,65536)%N + 1
        if temp[index]==0:
            temp[index] = key[i]
        else:
            while temp[index] != 0:
                index = (index%N) + 1
            temp[index] = key[i]
    for i in range(1,N+1):
        key[i] = temp[i]
 
def main():
    d = Dict(N+1)
    key = [0 for i in range(N+1)]
    search_key = [0 for i in range(N+1)]
    init(key,search_key)
    for i in range(1,N+1):
        d.insert(key[i])
    start_time = time.time()
    for i in range(1,N+1):
        result = d.search(search_key[i])
        if result==-1 or result != search_key[i]:
            print u'탐색 오류.'
    print u'이진 트리 탐색의 실행 시간 (N = {} ): {}'.format(N,time.time()-start_time)
    print u'탐색 완료.'
 
 
if __name__=='__main__':
    main()