최악의 경우에도 로그 n이 되도록하는게 중요해서 사람들이 연구를 굉장히 많이했으

Search하게되면 트리 높이에 비례해서 시간이걸려

<aside> 💡 트리 모양이 어케되느냐에 의존하기 때문에 트리 모양을 균형이 잡힌 모양으로 만드는게 필요한것같다는거야

</aside>

그럼 어떻게 균형잡힌 모양으로 만들지?

균형이 잡혔다는건 뭐지?

루트기준으로 봤을때 누가봐도 왼쪽은 좀 많고 오른쪽은 좀 적죠

그럼이거 루트를 바꿀 수밖에 없어

완전한 얘기는 아니야 하지만 아이디어를 줄 수있을거야

루트 기준으로 지금뭔가 왼쪽이 무겁다는 생각이 드는건 사실이지

루를 바꾸지 않으면 균형을 맞출수가 없다는거야. 그런데 루트를 뭐로 바꿀거냐면 4를 루트로 바꿀거야

그럼 여기서 문제는 차일드가 3개가되죠?

이러면 바이너리 트리가 아니게됨

근데 보면 6이 원래 왼쪽 차일드4가 있었는데

4가 올라가면서 부모가 되어버렸어.그래서 결국은 왼쪽차일드가 없죠

그럼 자리가 비었으니까 5를 왼쪽 차일드로 가져다 붙이자는 겁니다

이러고나니까 오!

루트에 있는 값이 달라졌고 그다음에 오른쪽에 3개 왼쪽에 3개 좀 맘에 드는 모양으로 바꿔졌죠