# 이진트리
# 최대 두개의 자식을 ㄱ라지고 있는 자료구조 입니다.
# 자식 노드는 보모 노드에 대한 참조를 포함할수 있습니다.
# 트리의 루트 노드는 모든 노드의 조상입니다.
# 노드 차수 : 자식 수
# 경로 : 한 노드(부모)로부터 다른 노드(자식)에 이르는 노드의 순서
# 경로 길이 : 간선의 수,만일 시작노드와 끝노드가 같다면 경로의 길이는 0
# 형제 노드 : 부모가 같은 노드
# 외부 노드 : 자식이 없는 노드(차수가 0인 노드)
# 내부 노드 : 자식이 있는 노드(차수가 0이 아닌 노드)
# 노드의 깊이 : 루트 노드에서 ㄴ어떤 노드로 가는 경로의 길이, 루트 노드의 높이는 0
# 노드 레벨 : 루트 노드에서 어떤 노드로 가는 길이 + 1
# 루트 노드의 레벨은 1입니다.
# 같은 레벨을 가지고 있는 집합을 레벨이라고 부른다.
# 노드의 높이 : 한 노드와 단말 노드 사이의 최대 경로 길이
# 크기 : 모든 노드의 수
# 이진 트리의 종류
# 포화 이진 트리 : 모든 내부의 노드가 두개 자식 노드를 가지면서
# 모든 말단 노드가 같은 깊이 또는 같은 레벨을 가진다.
# 완전 이진 트리 : 마지막 레벨을 제외한 모든 레벨이 완전히 채워져
# 있고, 마지막 레벨의 모든 말단 노드는 왼쪽에 있다.
# 이진 트리의 차수 구하는 법
# 노드의 차수는 최대 2
# 트리에 m개의 내부 노드가 있고
# 각 내부 노드에 두개의 자식 노드가 있다고 가정합니다.
#트리에 n개의 말단 노드가 있다면 트리의 차수는 n - 1
# 2m= n + m - 1
# m = n - 1
def solution(progresses, speeds):
answer = []
time = 0
count = 0
while len(progresses) > 0:
if (progresses[0] + time* speeds[0]) >= 100:
progresses.pop(0)
speeds.pop(0)
count += 1
else:
if count > 0:
answer.append(count)
count = 0
time += 1
answer.append(count)
return answer
solution([95, 90, 99, 99, 80, 99], [1, 1, 1, 1, 1, 1])
>>>[1, 3, 2]# 이진트리 구현하는 가장 쉬운 방법은
# 리스트를 사용하는 것이라서
# 루트 노드 와 두개의 하위 리스트가 있는 리스트
# 루트 노드 왼쪽에 서브 트리를 추가하려면 루튼 노드의 두번째 위치에 새로운 리스트를 삽입합니다.
def BinaryTreeList(r):
return [r, [], []]
def insertLeft(root, newBranch):
t = root.pop(1)
if len(t) > 1:
root.insert(1, [newBranch, t, []])
else:
root.insert(1, [newBranch, [], []])
return root
def insertRight(root, newBranch):
t = root.pop(2)
if len(t) > 1:
root.insert(2, [newBranch, [], t])
else:
root.insert(2, [newBranch, [], []])
return root
def getRootVal(root):
return root[0]
def setRootVal(root, newVal):
root[0] = newVal
def getLeftChild(root):
return root[1]
def getRightChild(root):
return root[2]
def main():
r = BinaryTreeList(3)
insertLeft(r, 4)
insertLeft(r, 5)
insertRight(r, 6)
insertRight(r, 7)
print(getRootVal(r))
print(getLeftChild(r))
print(getRightChild(r))
if __name__ == "__main__":
main()
# 리스트를 사용한 트리에서는
# 노드의 검색, 추가 작업이 비효율적입니다.
>>>
3
[5, [4, [], []], []]
[7, [], [6, [], []]]# 클래스를 이용한 이진트리를 만들어 줍니다.
# NodeBT
# BinaryTree
class Height(object):
def __init__(self):
self.height = 0
class NodeBT(object):
def __init__(self, value=None, level=1):
self.value = value
self.level = level
self.left = None
self.right = None
def __repr__(self):
return "{}".format(self.value)
def _add_next_node(self, value, level_here=2):
new_node = NodeBT(value, level_here)
if not self.value:
self.value = new_node
elif not self.left:
self.left = new_node
elif not self.right:
self.right = new_node
else:
# 노드 왼쪽 오른쪽 둘다 자식이 있다면
# 왼쪽 자식 노드의 새로운 노드를 추가합니다.
self.left = self.left._add_next_node(value, level_here+1)
return self
def _search_for_node(self, value):
# 전위 순회(pre-order)
if self.value == value:
return self
else:
found = None
if self.left:
found = self.left._search_for_node(value)
if self.right:
found = found or self.right._search_for_node(value)
return found
def _is_leaf(self):
# 왼쪽과 오른쪽 모두 자식이 없는 노드
return not self.right and not self.left
def _get_max_height(self):
heightr, heightl = 0, 0
if self.right:
heightr = self.right._get_max_height() + 1
if self.left:
heightl = self.left._get_max_height() + 1
return max(heightr, heightl)
def _is_balanced(self, height=Height()):
lh = Height()
rh = Height()
if self.value is None:
return True
l, r = True, True
if self.left :
l = self.left._is_balanced(lh)
if self.right:
r = self.right._is_balanced(rh)
height.height = max(lh.height, rh.height)+ 1
if abs(lh.height - rh.height) <= 1:
return l and r
return False
def _is_bst(self, left=None, right=None):
if self.value:
if left and self.value < left:
return False
if right and self.value > right:
return False
l, r = True, True
if self.left:
l = self.left._is_bst(left, self.value)
if self.right:
r = self.right._is_bst(self.value, right)
return l and r
else:
return True
class BinaryTree(object):
def __init__(self):
self.root = None
def add_node(self, value):
if not self.root:
self.root = NodeBT(value)
else:
self.root._add_next_node(value)
def is_leaf(self, value):
node = self.root._search_for_node(value)
if node :
return node._is_leaf()
else:
return False
def get_node_level(self, value):
node = self.root._search_for_node(value)
if node:
return node.level
else:
return False
def is_root(self, value):
return self.root.value == value
def get_height(self):
return self.root._get_max_height()
def is_balanced(self):
return self.root._is_balanced()
def is_bst(self):
return self.root._is_bst()
# 1 -레벨 1
# 2 3 -레벨 2
# 4 5 -레벨 3
# 6 7 -레벨 4
# 8 9 -레벨 5
# 속성
# 노드의 개수 : n = 9
# 내부 노드의 수 : 8
# 루트 노드 : 1
# 최대 깊이 또는 높이 : 4
# 균형 트리인가? 아니오
# 이진탐색트리? 아니오
if __name__ == "__main__":
bt = BinaryTree()
for i in range(1, 10):
bt.add_node(i)
print("8은 말단 노드 입니까 ?", bt.is_leaf(8))
print("8의 레벨은 ?", bt.get_node_level(8))
print("10은 루트 노드?",bt.is_root(10))
print("1은 루트 노드?",bt.is_root(1))
print("트리의 높이 ?", bt.get_height())
print("이진 탐색 트리 ?", bt.is_bst())
print("균형 트리 ?", bt.is_balanced())
>>>
8은 말단 노드 입니까 ? True
8의 레벨은 ? 5
10은 루트 노드? False
1은 루트 노드? True
트리의 높이 ? 4
이진 탐색 트리 ? False
균형 트리 ? False# 각 노드에는 값과 두 자식 노드에 대한 포인터가있습니다.
# 선택적으로 부모의 포인터를 저장할수 있습니다.
# 각 노드의 값은 왼쪽 하위 트리의 모든 항목보다 크고
# 오른쪽 하위 트리의 모든 항목보다 작습니다.
# = 이진 탐색 트리 규칙 =
# 노드의 왼족 하위 트리에는 노드의 값보다 작은 값의 노드만 존재
# 노드의 오른쪽 하위 트리에는 노드의 값보다 큰 값의 노드만 존재
# 왼쪽과 오른쪽 하위 트리 모두 이진 탐색 트리
# 중복 노드가 없어야 한다.
# 위에서 만든 BinaryTree를 슈퍼클래스 삼아서 만들면 된다.
# 다음과 같은 이진트리를 만들어 주세요
# 6 ----> 레벨 1
# 4 8 ----> 레벨 2
# 2 5 7 9 ----> 레벨 3
# 1 3 ----> 레벨 4
# 속성
# 노드의 개수 = 9
# 분기의 수 = 8
# 루트 노드 = 6
# 최대 깊이 또는 높이 = 3
# 균형트리 ? True
# 이진 탐색 트리 ? True
class NodeBST(NodeBT):
def __init__(self, value=None, level=1):
self.value = value
self.level = level
self.left= None
self.right = None
def _add_next_node(self, value, level_here=2):
new_node = NodeBST(value, level_here)
if value > self.value:
self.right = self.right and self.right._add_next_node(value, level_here + 1) or new_node
elif value < self.value:
self.left = self.left and self.left._add_next_node(value, level_here + 1) or new_node
else:
print("중복 노드를 허용하지 않습니다.")
return self
def _search_for_node(self, value):
if self.value == value:
return self
elif self.left and value <self.value:
return self.left._search_for_node(value)
elif self.right and value > self.value:
return self.right._search_for_node(value)
else:
return False
class BinarySearchTree(BinaryTree):
def __init__(self):
self.root = None
def add_node(self, value):
if not self.root:
self.root = NodeBST(value)
else:
self.root._add_next_node(value)
if __name__ == "__main__":
bt = BinarySearchTree()
# for i in range(1, 10):
for i in [6, 4, 8, 2, 5, 7, 9, 1, 3]:
bt.add_node(i)
print("8은 말단 노드 입니까 ?", bt.is_leaf(8))
print("8의 레벨은 ?", bt.get_node_level(8))
print("10은 루트 노드?",bt.is_root(10))
print("1은 루트 노드?",bt.is_root(1))
print("트리의 높이 ?", bt.get_height())
print("이진 탐색 트리 ?", bt.is_bst())
print("균형 트리 ?", bt.is_balanced())
>>>
8은 말단 노드 입니까 ? False
8의 레벨은 ? 2
10은 루트 노드? False
1은 루트 노드? False
트리의 높이 ? 3
이진 탐색 트리 ? True
균형 트리 ? True# 자가 균형 트리
# 모든 하위 트리의 높이 차이가 1 이하인 트리를 말합니다.
# 노드와 삽입 연산이 일어날때 자동으로 트리의 균형이 유지되지 않습니다.
# 편향 트리 라고 합니다.
# 우리가 배울 자가 균형 트리는
# 삽입과 삭제 연산이 일어날때 자동으로 균형 트리를 유지해줍니다.
# 균형을 유지하기 위해서 균형도라는 왼쪽 오른쪽 하위 트리의 높이 차이를 이용합니다.
# * 노드 분할 및 병합
# - 노드의 자식은 두개를 초과하지 못하며, 노드가 많으면 두개의 하위로 나눕니다.
# * 노드 회전
# - 간선을 전환합니다. x가 y의 부모이면 y를 x의 부모로 만들고, x는 y의 자식중 하나로 만듭니다.
# AVL 트리
# 왼쪽 오른쪽 하위 트리높이가 1보다 클수 없는 자체 균형 조건을 가진 이진 탐색 트리
# 트리에 노드를 추가하거나 삭제할때 마다 자가 균형조정 메서드를 호출하면 AVL 트리를 구현할수 있ㅎ습니다.
# 이 메서드는 보통 노드가 추가 삭제 될때마다 트리의 높이를 계속 확인하면서 동작하게 됩니다.
# 좀더 정확하게 말을 하면 균형도를 맞추기 위해서 오른족 또는 왼쪽으로 [회전]합니다
# 회전 하는 순서
# 1) 이전에 구현한 이진 탐색 트리와 같이 재귀 함수를 사용해서 상향ㅅ힉으로 구현
# 2) 현재 노드는 새로 삽입될 노드의 조상 노드중 하나이므로 노드가 삽입될때
# 조상 노드의 높이를 조정한다.
# 3) 현재 노드의 균현도를 계산합니다( 현재 노드의 왼족 하위 트리 높이 - 현재 노드의 오른쪽 하위 트리 높이)
# 4) 트리의 균형도가 맞지 않을 경우 [회전]
# 4-1) 균현도가 1보다 큰경우 LL케이스, LR 케이스
# - 새 노드의 값이 현재 노드의 왼족 노드의 값보다 작다면 LL
# - R 회전을 수행합니다.
# - 새 노드의 값이 현재 노드의 왼쪽 노드의 값보다 크다면 LR
# - LR 회전을 수행합니다.
# * LR 회전 ? 왼쪽 노드 L회전 -> R 회전
# 4-2_ 균형도가 -1보다 작을 경우 RR케이스, RL 케이스
# - 새 노드의 값이 현재 노드의 오른쪽 보다 크다면 RR,
# - L 회전을 수행합니다.
# - 새 노드의 값이 현재 노드의 오른쪽보다 작다면 RL,
# - RL 회전을 수행합니다.
# * RL 회전 ? 오른쪽 노드 R 회전 -> L 회전
반갑습니다