왜 노드를 (역순으로) 추가하면 비효율적 인 검색이 가능합니까?

Question

나는 시험을 준비하고 나는 다음과 같은 질문에 발견 한 :

10,9,8,7,6,5,4,3

:

데이터는 다음과 같은 순서로 추가 할 것 인 경우에 발생 될 이진 검색 트리를 그리기

결과 검색에 적합한 트리가 적합하지 않은 이유는 무엇입니까?

내 답변 : 다음 첫 번째 레벨의 왼쪽 서브 트리 값으로 구를 추가 우리는 루트 노드와 같은 값 10 시작할 BST를 만들 때 내가 생각했던 것

. 그런 다음 9를 왼쪽 하위 트리에 8 등등. 왜 이렇게하면 검색에 비효율적인지 알 수 없습니다. 어떤 아이디어? 값이 감소하는 순서로, 그들이 각 레벨에서 왼쪽에 첨가 취득되므로

Answer 1

실질적 대신 BST의 바람직한 O (logN)로, O (N)를 검색하는 데 걸리는 링크 된 목록을 함께 떠나는 .

그리기 : 그냥 일련의 노드가 될 것이기 때문

   10 
      /
      9 
     /
      8 
     /
     7 
    /
     6 
    /
    5 
/
    4 
/
3 

Answer 2

이것은, 링크 된 목록을 만들 것입니다; 무겁게 불균형 한 나무입니다.

당신은 red-black trees을 보일 것입니다. 그것들은 같은 시간 복잡성을 가지고 있지만, 노드 주위를 끊임없이 이동하여 항상 삼각형 모양을 형성합니다. 이것은 나무 균형을 유지합니다.

Answer 3

노드가 항상 이전 노드의 왼쪽 서브 트리에 추가됩니다 때문 비효율적이다. 검색 결과가 항상 왼쪽에있을지라도 결과를 찾을 때까지 목록의 모든 노드를 검사하여 실제로 루프를 통해 검색되는 목록을 갖는 것보다 더 많은 계산을 수행하게 만듭니다.