기말 대비 모각코

오늘은 화일 처리 과목 중에 tree의 한 종류인 avl 을 구현 하기로 했다
완전 균형 BST (Completely balanced BST)
– 모든 노드에 대해, 양쪽 서브트리의 높이를 같게 만듬.
 트리의 최대 경로 길이를 최소화
– 즉, 각 노드의 삽입 혹은 삭제 때마다, 트리가 균형을
유지하도록 전체 트리를 재균형시킴.
 삽입/삭제 연산 시간이 너무 커서 비현실적임.
o 높이 균형 BST (Height-balanced BST)
– 전체 트리를 재균형시키지 않고, 트리가 “거의” 균형을
유지하도록 탐색 트리의 형태를 제어
– 즉, 삽입/삭제가 균형을 깨면, 트리를 부분적으로 재균형시킴.
 회전(rotation)
 삽입/삭제 연산 시간이 비교적 짧음.
이와 같이 avl은 다른 bst와 비교했을때 균형을 이루는 트리를 만들 수 있다

def insertAVL(T, newkey):
p = T
q = None
x = None
f = None
stack = []
while (p != None):

    # Newkey 삽입할 장소를 탐색
    if(newkey == p.key): 
        # 장소 탐색중 이미 key값이 존재한다면 그대로 트리를 리턴
        print(f'i {newkey} : The key already exists')
        return T
    q = p
    # 탐색중 지나가는 노드들은 전부 mir 배열에 추가
    stack.append(q)
    if (newkey < p.key): p = p.left
    else: p = p.right
# 새로운 노드생성
newNode = getNode()
newNode.key = newkey
# q의 자식으로 노드삽입
if (T==None): T = newNode
elif(newkey < q.key): q.left = newNode
else: q.right = newNode
# 노드 생성으로인한 노드들의 높이, 노드갯수 설정
while (len(stack) != 0):
    q = stack.pop()
    q.height = max(height(q.left), height(q.right)) + 1
    q.node = noNodes(q)
    q.bf = q.left.height - q.right.height
    if (1 < q.bf or q.bf < -1):
        if (x == None):
            x = q
            f = stack[-1]
if (x == None): return T
rotationType = ""
rotationType = checkBalance(T, key, rotationType, p, q)
if (1<x.bf):
    if(x.left.bf <0):
        rotateTree(T, rotationType, p, q) # LR
    else:
        rotateTree(T, rotationType, p, q) # LL
else:
    if(x.right.bf > 0):
        rotateTree(T, rotationType, p, q) # RL
    else:
        rotateTree(T, rotationType, p, q) # RR
return T
이것은 avl의 삽입 알고리즘을 구현해 보았다