이진 '탐색' 트리 : 정렬된 트리
- 노드의 왼쪽 서브트리: 노드의 값보다 작은 값들을 지닌 노드들
- 노드의 오른쪽 서브트리: 노드의 값과 같거나 큰 값들을 지닌 노드들
이진탐색트리의 장점 -> 탐색의 시간 복잡도가 O(logN)이다.
- 자가 균형 이진 탐색 트리
: 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진탐색 트리
왼쪽 노드에 비해 오른쪽 노드가 높이를 가능한 작게 유지한 트리다. 즉 오른쪽 트리가 자가 균형 이진 탐색 트리다.
균형트리와 불균형트리의 성능차이는 매우 크다. 노드 갯수가 증가할수록 성능 차이는 커진다.
자가 균형 이진 탐색 트리의 대표적 예로 AVL 트리, 레드-블랙 트리가 있다.
<자가 균형 이진탐색트리 주요 알고리즘>
- 정렬된 배열로 자가 균형(또는 높이 균형) 이진탐색 트리 만들기 ☆☆☆
문제: leetcode.com/problems/convert-sorted-array-to-binary-search-tree/
재귀구조를 이용하여 작성해보았다.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
def recursive(lst):
if not lst:
return
i = len(lst)// 2
node = TreeNode(lst[i])
node.left = recursive(lst[:i])
node.right = recursive(lst[i+1:])
return node
return recursive(nums)
트리 순회(Tree Traversal) :
그래프 순회의 한 형태로, 트리 자료구조에서 각 노드를 정확히 한번 방문하는 과정을 말한다.
이진트리에서 dfs는 노드의 방문 순서에 따라 3가지로 구분.
1. 전위 순회(pre-order) - NLR
2. 중위 순회(in-order) - LNR
3. 후위 순회(post-order) - LRN
( L = 현재 노드의 왼쪽 서브트리, R= 현재 노드의 오른쪽 서브트리, N=현재 노드 자신)
각각이 무엇인지 예제 코드를 통해 알아보자.
class Node:
def __init__(self,val=0,left=None,right=None):
self.val = val
self.left = left
self.right = right
def bst(lst): ## list --> binary search tree(height balanced)
if not lst:
return
i = len(lst)//2
node = Node(lst[i])
node.left = bst(lst[:i])
node.right = bst(lst[i+1:])
return node
# Traversal can be implemented relatively easily by using a recursive function.
# All three traversals are similar and simple.
def preorder(node):
if not node:
return
print(node.val)
preorder(node.left)
preorder(node.right)
def inorder(node):
if not node:
return
inorder(node.left)
print(node.val)
inorder(node.right)
def postorder(node):
if not node:
return
postorder(node.left)
postorder(node.right)
print(node.val)
char_list = ['a','b','c','d','e','f','g','h','i']
my_node = bst(char_list) # list to bst
preorder(my_node) # e-c-b-a-d-h-g-f-i
inorder(my_node) # a-b-c-d-e-f-g-h-i
postorder(my_node) # a-b-d-c-f-g-i-h-e
그래프와 순회 결과를 간단히 정리하면 위와 같아진다. 각각 익혀서 쓰임새에 맡게 잘 쓰도록 하자!!
+) 3가지 순회중 두 가지를 알면 이진 트리를 복원할 수 있다고 한다.
## 순회 문제 예시 ##
자기보다 큰 수 합계: leetcode.com/problems/binary-search-tree-to-greater-sum-tree/
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
sum =0
def bstToGst(self, root: TreeNode) -> TreeNode:
def recur(node):
if not node:
return
node.right = recur(node.right)
self.sum += node.val
node.val = self.sum
node.left = recur(node.left)
return node
return recur(root)
전위, 중위 순회 결과로 이진트리 구축하기
leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
def dfs(lst):
if not lst:
return
mid = preorder.pop(0)
idx = lst.index(mid)
node = TreeNode(mid)
node.left = dfs(lst[:idx])
node.right = dfs(lst[idx+1:])
return node
root = dfs(inorder)
return root
댓글