HashMap - 자바코드 뜯어보기(putTreeVal, removeTreeNode, untreeify)

1.putTreeVal

레드-블랙 트리 형식의 노드를 추가함과 동시에 연결리스트 관점에서의 순서도 같이 할당한다.

TreeNode는 연결리스트와 레드-블랙 트리의 형태가 합쳐진 하나의 형태로 생각하기보다는

연결리스트, 레드-블랙 트리의 모습을 각각 가지고 있는 형태로 이해된다.

1-1. find

마지막 else if 구문은 같은 오른쪽 자식부터 재귀하며 순회한다.

 

처음엔 마지막 else if 문에 순회 대신 putTreeVal, treeify 처럼 tieBreakOrder 메서드를 사용하여 dir값을 반환 해 재귀하여 순회하는 대신 더 쉽게 값을 찾을 수 있지 않을까? 라고 생각했었지만

스텍오버플로우에 질문하고 받은 답변으로 생각해보았을 때,

Question about comparing Java's HashMap `find` method and `tieBreakOrder` - Stack Overflow

Question about comparing Java's HashMap `find` method and `tieBreakOrder`

애초에 tieBreakOrder는 원본해시값을 비교하므로 내가 가진 key가 내부에 저장된 key와 완전히 동일한 원본해시를

가질 확률이 높지 않으므로 불가능하다. 

 

 

2. removeTreeNode

연결리스트의 순서를 제거하고

제거하려는 노드가 successor 가 필요한 노드인지, 아닌지를 판별하고 삭제 속성을 적용시킨 후 노드를 제거한다.

여기서 트리노드의 크기가 너무 작아지면 untreeify를 호출해

TreeNode(레드-블랙 트리) -> Node(연결리스트) 로 변환한다.

2-1. balanceDeletion

레드-블랙 트리의 삭제 case 들을 적용한다.

 

3. untreeify

기존의 TreeNode를 순회하면서 각각의 TreeNode를 이용해 Node 구현체를 생성하고 서로 연결하여

Node 연결리스트를 반환한다.

 

---

 

이전의 treeify를 정리 할 때 TreeNode의 형태가 연결리스트와 레드-블랙 트리의 구조가 결합된 모습이라는 것은 알았으나

머릿속에서는 그 형태가 모호했는데, 이번 정리를 통해서 TreeNode의 형태를 조금 더 명확하게 이해할 수 있었고,

참조와 인스턴스의 관계성에 대해서 좀 더 이해할 수 있는 기회가 되었다.