Tree(트리)
트리나 링크드리스트나 뭐 그게 그거다.
루트노드가 딸랑 주어지고 트리를 구석구석 효율적으로 탐색하면서 주어진 과제를 수행하는게 트리면접문제의 99%이다. 이 트리를 탐색하는데 크게 두가지 방법이 있는데 반복을 이용하는 너비우선탐색(BFS)과 재귀를 이용한 깊이우선탐색(DFS)이다.
BST(이진탐색트리)
미국으로 진출하고 싶은 프로그래머의 입국자격. 면접문제로 나오는 트리는 그냥 이진탐색트리라고 생각하면 될정도로 많이 나온다.(
고한다) 이게 BST인지 유효성을 검증한다던가
모든 부모노드의 값이 왼쪽 자식트리에 있는 값보다는 크고 오른쪽 트리에 있는 값보다는 작은 형태의 트리.(중복된 노드가 없어야 한다.) 형태를 보기만해도 재귀적인느낌이 강한트리.
강점은 트리내에 N개의 노드가 있을때 어떤 값을 찾는다해도 O(logN) 의 시간복잡도를 갖는다는 것이다.
하지만 이렇게 단순한 작업을 하기위해 트리를 쓴다는건 말도 안되고(대단하신 해쉬맵님은 숫자가 천억개라도 O(1)라는걸 기억하자) 이것을 바탕으로 여러 멋진것들을 만든다고 한다.
너비우선탐색(BFS)
큐를 기반으로 탐색한다.
def BFS(root)
q = queue.Queue()
q.put(root)
while q.qsize() > 0:
node = q.get()
if node:
#doSomething
q.pull(node.left)
q.pull(node.right)
BFS의 적당한 예
어떤 트리가 있는데 완전트리가 아니다(어디는 존나깊고 어디는 존나얕다) 가장얕은곳에 있는 노드를 알고싶을 경우
실습 : 트리의 모든 노드 출력하기
import queue
class Node():
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def addToEnd(new, current):
if new > current.val:
if current.right is None:
current.right = Node(new)
else:
addToEnd(new, current.right)
else:
if current.left is None:
current.left = Node(new)
else:
addToEnd(new, current.left)
def printTree(node):
q = queue.Queue()
q.put(node)
q.put(Node(-1))
allLines = []
currLine = []
while q.qsize() > 0:
node = q.get()
if node is None:
continue
if node.val == -1:
if q.qsize() > 0:
allLines.append(currLine)
currLine = []
q.put(Node(-1))
else:
currLine.append(node.val)
q.put(node.left)
q.put(node.right)
return allLines
root = Node(10)
addToEnd(15,root)
addToEnd(5,root)
addToEnd(9,root)
addToEnd(4,root)
addToEnd(11,root)
addToEnd(16,root)
printTree(root);
# => [[10], [5, 15], [4, 9, 11, 16]]
깊이우선탐색(DFS)
트리를 공부하는 이유. 가장깊은곳까지 내려갔다 오는 방식. 재귀적으로 탐색한다. 순서에 따라서 3가지로 나뉘는데 일단 생략.
def DFS(node)
#doSomething
if node == 리프노드:
#doSomething
return
DFS(node.left)
DFS(node.right)