이진탐색트리, 자가균형트리

이진탐색트리

• ==이진탐색트리는 왼쪽자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진트리입니다. 삽입 검색 삭제가 모두 트리 높이인 logN~N만큼의 시간복잡도를 가집니다. 하지만 편향될 위험이 있어서 자가 균형트리를 사용합니다.
• 왼족 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진트리
  • 삽입, 검색 = 높이만큼의 시간복잡도 == logN ~ N(편향된 이진탐색트리)

자가균형트리

• == 자가균형트리는 편향된 이진탐색트리의 문제를 개선해서 편향을 줄인것이 자가 균형 트리 입니다. AVL, readblack tree가 있습니다