넘치게 채우기

https://www.acmicpc.net/problem/5639BOJ - 이진 검색 트리문제 유형: 트리, 재귀, dfs, 이진탐색트리(BST)문제 난이도: Gold IV시간 제한: 1초메모리 제한: 256MB 문제이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, ..

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/description/leetcode - Binary Search Tree to Greater Sum Tree문제 유형 : 이진트리, 이진탐색트리, dfs문제 난이도 : Medium 문제Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.As a reminder, a ..

https://leetcode.com/problems/find-mode-in-binary-search-tree/description/ Find Mode in Binary Search Tree - LeetCode Can you solve this real interview question? Find Mode in Binary Search Tree - Given the root of a binary search tree (BST) with duplicates, return all the mode(s) [https://en.wikipedia.org/wiki/Mode_(statistics)] (i.e., the most frequently occurred element leetcode.com leetcode -..

레드블랙트리의 삭제의 순서는 다음과 같다: 1. 삭제할 노드를 찾는다 2. 삭제할 노드의 자식이 a. 둘인 경우 - 없앨 노드의 오른쪽 서브트리의 가장 왼쪽 노드(또는 왼쪽 서브트리의 가장 오른쪽 노드)로 노드를 바꾸고, 그 잎 노드를 없애준다. b. 하나인 경우 - 삭제되는 노드의 부모노드와 자식노드를 연결시킨다. c. 없는 경우 - 노드를 없애주면 된다. 여기까지는 이진탐색트리의 노드제거와 같다. 3. 삭제되는 노드의 색깔이 빨간색인 경우, 여전히 레드블랙트리의 규칙을 만족하므로 삭제가 완료된다. 그러나, 삭제되는 노드의 색이 검은색인 경우, 그 자리를 대체하는 노드를 검은색으로 칠한다. 여기서, 대체하는 노드 역시 검은색인 경우, 이중 흑색노드가 생긴다. 그럼, 이중 흑색노드를 어떻게 해결하냐? C..

레드-블랙 트리는 스스로 균형을 잡는 자가 균형 이진 탐색 트리(Self - Balancing Binary Search Tree)이다. 레드-블랙 트리에는 다음과 같은 조건들이 있다: 모든 노드는 빨간색 혹은 검은색이다. 루트 노드는 검은색이다. 리프 노드(NIL : Null Leaf)는 검은색이다. 빨간 노드의 자식 노드는 검은색이다(No Double Red, 빨간 노드가 연속으로 있을 수 없다) 어떤 노드에서 리프 노드까지 가는 검은 노드의 개수는 같다. + 레드-블랙 트리에서, 어떤 노드의 두 자녀가 같은 색이면 부모와 두 자녀의 색을 바꿔도 5번 규칙이 성립된다. ++ 추가되는 노드는 무조건 빨간색 노드이다. 5번 규칙을 충족시키기 위해서이다. 레드-블랙 트리의 높이 레드-블랙 트리의 높이 중에는..

이진 탐색 트리? 이진 탐색 트리는 다음과 같은 조건이 있다: 같은 key값을 가지는 노드는 없다. 루트노드의 왼쪽 서브트리는 루트노드보다 작은 값들만 있어야 한다. 루트노드의 오른쪽 서브트리는 루트노드보다 큰 값들만 있어야 한다. 루트노드의 서브트리들 모두 이진 탐색 트리여야 한다. 이 조건들로, 이진 탐색 트리를 순회할 때 에는 보통 중위 순회를 이용한다. 이진 탐색 트리에는 세 가지 연산이 있다. 탐색(Search) 삽입(Insert) 삭제(Delete) 탐색 만약, 루트와 같은 값을 가진다면, 탐색을 멈춘다. 루트가 없는 경우 역시 탐색을 멈춘다. 만약, 루트보다 작은 값을 가진다면 왼쪽 서브트리에서, 더 큰 값을 가지면 오른쪽 서브트리에서 재귀한다. 구현 def _search(self, root..