자료구조 강좌 소스 코드
양아름님께서 이 강좌를 듣고 너무나 정리를 잘 해주셔서 강의 교안을 거의 그대로 사용합니다.
5, 9, 4, 14, 19, 23, 7, 11, 8, 2, 16
insert()
5입장에서 11을 넣으려고 할 때, 9와 14에게 위임한 뒤, 11을 추가할 수 있다. 14에게 위임할 때, 왼쪽을 찾으려고 했더니 왼쪽이 없는 상황이다. 11을 넣고자 하는 상황에 왼쪽이 비어있다는 것을 인지한다.
#insert(node, value) {
if (node.value > value) {
// 상위 값보다 넣으려고 하는 값이 작으면, 왼쪽
if (node.left) {
// 왼쪽에 값이 있으면, 왼쪽에 있는 값에게 처리를 넘김
this.#insert(node.left, value);
} else {
// 만약 왼쪽이 비어있다면? 왼쪽에 추가
node.left = new Node(value);
}
} else {
// 상위 값보다 넣으려고 하는 값이 크면, 오른쪽
if (node.right) {
// 오른쪽에 값이 있으면, 오른쪽에 있는 값에게 처리를 넘김
this.#insert(node.right, value);
} else {
// 만약 오른쪽이 비어있다면? 오른쪽에 추가
node.right = new Node(value);
}
}
}
search()
return
해줘야한다.#insert()
재귀함수와 동일한 조건의 틀을 가진다.
return
을 해줘야하는 부분만 다르다.null
을 return
하는지 )remove()
조건 : 제거하려는 값(
value
)과 트리 내부의 존재하는 값(node.value or root
)이 동일한 경우
leaf
일 경우
결과 : null
을 return
한다.
자식 Node
가 1개일 경우
2-1. 왼쪽 Node
만 있을 경우
결과 : (오른쪽 Node
가 없을 경우) 왼쪽 Node
를 return
한다.
2-2. 오른쪽 Node
만 있을 경우
결과 : (왼쪽 Node
가 없을 경우) 오른쪽 Node
를 return
한다.
자식 Node
가 2개일 경우
만약, 어떠한 값을 제거한다면? ( root
를 제거한다면 )
3-1. 자신의 왼쪽 Node
로부터 오른쪽 Node
중 가장 큰 수가 root
자리로 오게된다.
3-2. 그 후, root
자리로 온 숫자의 자리로 원래 root
였던 수가 들어간다.
3-3. 그리고 제거된다.
풀이.
Node
를 변수에 담아준다.Node
를 찾아야한다. (node.left.right.right.right
)while()
문을 사용한다.Node
가 있을 때까지 )Node
를 만든 왼쪽 Node
변수에 담는다.Node
와 찾은 오른쪽 가장 큰 수 Node
를 바꿔준다.node.value
)을 변수(temp
)에 담는다.node.value = 왼쪽 Node를 담은 변수의 value
)Node
를 담은 변수의 value
값에 변수temp
을 담는다.node.left
에 담아 재귀함수를 호출한다.node
를 return
한다.조건 : 제거하려는 값(
value
)과 트리 내부의 존재하는 값(node.value or root
)이 동일하지 않은 경우
Node
에게 물어본다.Node
에 재귀함수를 호출한다.Node
에 재귀함수를 호출한다.node
를 return
한다.예외처리 :
null
을return
한다.
leaf
일 경우 ( 자식 Node
가 0개일 경우 or 트리에 Node
가 하나일 때 삭제하는 경우 )
return node
가 왜 필요한가 ? 꼭 ! 정리한 이미지, 코드, 트리보고 흐름파악
keypoint
key
와 value
가 골고루 분포하도록.)key
값과 capa
값을 나눠서 나머지 값을 구하는 법이 가장 간단한 hash
함수 구현법이다.