세상의 모든 Software 지식을 정리

*BFS-> 스택을 이용

특징: -사전 순 배열 시간복잡도: 가정: 균형트리일 경우 삽입: O(logN) 삭제: O(logN) 탐색: O(logN) 단점: 한곳으로 쏠릴 수 있다. 삭제의 경우: 1. 자식이 두 개인 경우 - 왼쪽자식에서 가장 큰 값을 가지고 오는경우와 - 오른쪽자식에서 가장 작은 값을 가지고 오는 경우 두가지가 가능하다 그렇다면 무엇을 선택하는게 좋을까? 내 생각은 두 서브트리중 더 작은 갯수의 서브트리를 선택하는 것이 낫다고 생각한다. 아마도 탐색 횟수가 줄어들기 때문에, 근데 장기적 관점에서 보면 한쪽으로 쏠린 서브트리의 자식갯수를 줄이는게 더 좋을 수 있지 않을까? ---> 이 경우 두 서브트리의 균형을 맞추기 위해 , 두 서브트리가 대칭을 이루기 위한 StdRandom.beronuii 로 접근한다. L/(L+R)로 접근. 응용: 이진트리의 경우에서 자식노드의 갯수를 3,4... 늘리는 경우를 B트리라 한다.