[자료구조] 9,10 주차 노트 (AVL, Red-Black Tree, B-Tree, Hash 테이블)

KOCW에서 제공하는 고려대학교 유용재 교수님의 자료구조 강의를 수강한 후, 정리한 글입니다. 

http://www.kocw.net/home/cview.do?cid=b216fbe96107c9ea

 

주제

• 9주차 균형을 고려한 여러가지 Tree
• 10주차 Hash Table을 이용한 데이터 적재

# AVL Tree

class Node:
    def __init__ (self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 0

class AVL:
    def __init__ (self):
        self.root = None

    def height(self, node):
        if node == None:
            return -1
        else:
            return node.height
    
    def balance_factor(self, node):
        return self.height(node.left) - self.height(node.right)
        
    def insert_data(self, data):
        self.root = self.insert(self.root, data)
    
    def insert(self, node, data):
        if node == None:
            return Node(data)
        if node.data < data:
            node.right = self.insert(node.right, data)
        if node.data > data:
            node.left = self.insert(node.left, data)
            
        node.height = max(self.height(node.left), self.height(node.right)) +1
        
        if self.balance_factor(node) > 1:
            if self.balance_factor(node.left) > 0:
                node = self.LL(node)
            else:
                node = self.LR(node)
        if self.balance_factor(node) < -1:
            if self.balance_factor(node.right) > 0:
                node = self.RL(node)
            else:
                node = self.RR(node)
                
        return node
    
    # 1) 유형
    def LL(self, node):
        new = node.left
        node.left = new.right
        new.right = node
        node.height = max(self.height(node.left), self.height(node.right)) +1
        new.height = max(self.height(new.left), self.height(new.right)) +1
        return new

    # 2) 유형    
    def RR(self, node):
        new = node.right
        node.right = new.left
        new.left = node
        node.height = max(self.height(node.left), self.height(node.right)) +1
        new.height = max(self.height(new.left), self.height(new.right)) +1
        return new
        
    # 3) 유형
    def LR(self, node):
        new = node.left.right
        node.left.right = new.left
        new.left = node.left
        node.left = new.right
        new.right = node
        new.left.height = max(self.height(new.left.left), self.height(new.left.right)) +1
        new.right.height = max(self.height(new.right.left), self.height(new.right.right)) +1
        new.height = max(self.height(new.left), self.height(new.right)) +1
        return new
    
    # 4) 유형
    def RL(self, node):
        new = node.right.left
        node.right.left = new.right
        new.right = node.right
        node.right = new.left
        new.left = node
        new.left.height = max(self.height(new.left.left), self.height(new.left.right)) +1
        new.right.height = max(self.height(new.right.left), self.height(new.right.right)) +1
        new.height = max(self.height(new.left), self.height(new.right)) +1
        return new



new_tree = AVL()
new_tree.insert_data(5)
new_tree.insert_data(2)
new_tree.insert_data(1)
new_tree.insert_data(3)
new_tree.insert_data(4)
print("new_tree")
print(new_tree.root.data)
print(new_tree.root.left.data)
print(new_tree.root.right.data)
print(new_tree.root.right.left.data)
print(new_tree.root.right.right.data)

new_tree_2 = AVL()
new_tree_2.insert_data(1)
new_tree_2.insert_data(2)
new_tree_2.insert_data(3)
new_tree_2.insert_data(5)
new_tree_2.insert_data(4)
print("new_tree_2")
print(new_tree_2.root.data)
print(new_tree_2.root.left.data)
print(new_tree_2.root.right.data)
print(new_tree_2.root.right.left.data)
print(new_tree_2.root.right.right.data)

# 실행 결과
new_tree
2
1
4
3
5
new_tree_2
2
1
4
3
5