'트리' 태그의 글 목록

트리의 좋은 모습은 "균형 잡힌" 트리이다. "균형 잡혔다"는 뜻은 자식 노드가 한쪽 방향으로 치우치지 않고 깊이가 비슷한 상황을 이야기한다. 이진 탐색 트리에서 삽입된 노드가 균형을 깨뜨리는 경우가 발생한다. 그럴 때 우리는 트리를 회전 시켜줘야한다. 회전에서 Left 회전과 Right 회전이 있다. 오른쪽 자식의 오른쪽 sub 트리가 문제일 때 : L회전 왼쪽 자식의 왼쪽 sub 트리가 문제일 때 : R회전 L회전은 오른쪽 자식을 부모 노드로 하고 부모 노드를 자식의 왼쪽 자식으로 편입하는 것이다. R회전은 반대로 왼쪽 자식을 부모 노드로 하고 부모 노드를 자식의 오른쪽 자식으로 편입하는 것이다. 이번에는 조금 더 복잡한 경우를 보자. 오른쪽 자식의 왼쪽 sub 트리가 문제일 때 : RL회전 왼쪽 자..