[자료구조] 트리 - 탐색 트리

728x90

반응형

 

 

 

🙆‍♂️ 이진 탐색 트리

---

탐색트리는 탐색을 위한 트리 기반의 자료 구조입니다.

이진 탐색 트리란 효율적인 탐색을 위한 이진트리 기반의 자료구조.

 

위와 같이 정렬할 수 있음.

 

힙트리와 이진탐색트리의 차이점

힙트리 : 최댓값이나 최솟값을 빠르게 검색하기 위한 목적

이진탐색트리 : 특정 값을 빠르게 탐색하기 위한 목적

#binary search tree
class BSTNode:
    def __init__(self, key, value):
        self.key=key
        self.value=value
        self.left=None
        self.right=None

 

연산

탐색연산

logn의 연산속도를 갖음.

def search(n,key):
    if n==None:
        return None
    elif n.key == key:
        return n
    elif n.key > key:
        return search(n.left, key)
    elif n.key < key:
        return search(n.right, key)

def search_max(n):
    while n != None and n.right !=None:
        n = n.right
    return n

def search_min(n):
    while n != None and n.left !=None:
        n = n.left
    return n

 

삽입연산

def insert(root,n):
    if n.key < root.key:
        if root.left is None:
            root.left = n
            return True
        else:
            return insert(root.left,n)
    elif n.key > root.key:
        if root.right is None:
            root.right = n
            return True
        else:
            return insert(root.right,n)
    else:
        return False

 

 

삭제연산

case 1 : 단말 노드 삭제

def delete_case1(parent,n,root):
    if parent is None:
        root = None
    else:
        if parent.left == n:
            parent.left=None
        else:
            parent.right = None
    return root

 

case 2 : 자식이 하나인 노드 삭제

def delete_case2(parent,n,root):
    if n.left is not None:
        child = n.left
    else:
        child = n.right
    
    if n == root:
        root = child
    else:
        if n is parent.left:
            parent.left = child
        else:
            parent.right = child
    return root

 

case 3 : 두 개의 자식을 가진 노드 삭제 

def delete_case3(parent,n,root):
    succ_p = n
    succ = n.right
    while succ.left != None:
        succ_p = succ
        succ = succ.left
        
    if succ_p.left == succ:
        succ_p.left = succ.right
    else:
        succp.right = succ.right
    n.key = succ.key
    n.value = succ.value
    return root

 

전체 코드

def delete_all(root,key):
    if root == None:
        return None
    
    parent = None
    node = root
    while node is not None and node.key is not key:
        parent = node
        if key < node.key:
            node = node.left
        else:
            node = node.right
    if node == None:
        return None
    if node.left == None and node.right == None:
        root = delete_case1(parent,node,root)
    elif node.left == None or node.right == None:
        root = delete_case2(parent,node,root)
    else:
        root = delete_case3(parent,node,root)
        
    return root

 

 

맵(map)

원하는 탐색키를 가진 레코드 값을 찾는 자료구조

파이썬의 dictionary와 같음.

class BSTMap():
    def __init__(self):
        self.root = None
    def isEmt(self): return self.root == None
    def search(self,key):
        return search(self.root,key)
    def findMax(self):
        return search_max(self.root)
    def findMin(self):
        return search_min(self.root)
    def insert(self, key, value=None):
        n = BSTNode(key,value)
        if self.isEmt():
            self.root=n
        else:
            insert(self.root, n)
    def inorder(self,n):
        if n is not None:
            self.inorder(n.left)
            print(f'({n.key},{n.value})',end=" ")
            self.inorder(n.right)
    
    def levelorder(self,n):
        import queue  
        q = queue.Queue()
        q.put(n)
        while q.empty() == False:
            next_n = q.get()
            if next_n is not None:
                print(f'({next_n.key},{next_n.value})',end=" ")
                q.put(next_n.left)
                q.put(next_n.right)
            
    def display_sort(self):       #오름차순 출력(중위 순회)
        print("MAP : ",end=" ")
        self.inorder(self.root)
        print()
        
    def display_tree(self):       #트리 레벨을 출력
        print("MAP-lv : ",end=" ")
        self.levelorder(self.root)
        print()
        
    def delKey(self,key):
        self.root = delete_all(self.root, key)
            
b_map = BSTMap()
key_data = [35,18,68,7,26,99,3,12,22,30]
for key in key_data:
    b_map.insert(key)

b_map.display_sort()
b_map.display_tree()

print("key 26 : ",b_map.search(26))
print("key 26 : ",b_map.search(28))
print(b_map.findMax().key)

b_map.delKey(18)
b_map.display_sort()
b_map.display_tree()

 

🙆‍♂️ 균형 이진 탐색 트리

---

AVL 균형이진탐색트리

모든 경우에 log n 시간복잡도를 보장합니다.

균형 인수가 1~ -1이 넘어가면 안됩니다.

균형인수는 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이입니다.

 

 

회전 방법

1. LL 회전 방법

def rotateLL(A):
    B=A.left
    A.left = B.right
    B.right = A
    return B

2. RR 회전 방법

def rotateRR(A):
    B=A.right
    A.right = B.left
    B.left = A
    return B

3. RL 회전 방법

def rotateRL(A):
    B = A.right
    A.right = rotateLL(B)
    return rotateRR(A)

4. LR 회전 방법

def rotateLR(A):
    B = A.left
    A.left = rotateRR(B)
    return rotateLL(A)