1. 그냥 이진 트리가 아니라, 이진 탐색 트리를 말씀하시는 것 같네요. 그냥 이진 트리라고만 하면 단순히 한 노드에 자식이 최대 둘 있는 트리를 말해서 노드를 탐색해나가는 규칙이 따로 정해져있지 않습니다.
2. 이진 탐색 트리의 경우 삽입/삭제/찾기 연산 각각에 대해 모두 평균 시간복잡도는 O(logN), 최악의 시간복잡도는 O(N)입니다. log^2N은 어디서 나온 건지 모르겠네요.
3. "logN번" 이라고 단정지어서 말씀하시는데 절대 딱 잘라서 말하면 안 됩니다. "O(logN)번" 이라고 적절한 기호를 씌워서 표현해야 합니다. 이 둘은 분명한 차이가 있고, 그를 이해하지 못하셨기 때문에 지금과 같은 혼동을 하시는 겁니다. 접근 표기법에 대해 알아보세요.

이진트리 ( 최대 자식노드가 2개까지 존재하는 트리 ) 
일반적인 트리의 탐색시간은 O(N)입니다. (traversal 했을 시 기준)

이진트리에서 왼쪽 자식으로 내려갈지, 오른쪽 자식으로 내려갈지 탐색에 대한 기준이 있다면 이를 이진 탐색트리 라고 합니다.

이진탐색트리는 트리의 높이만큼의 시간이 소요되므로 탐색의 시간복잡도는 O(h) (h= 트리의 높이) 입니다.
일반적으로 이진트리의 삽입 삭제 탐색 수행시간은 H 와 밀접한 연관을 가지고 있습니다. 

이로인해 트리의 높이를 최대한 줄여 트리가 균형을 잡히게하여  h 를 logN에 바운드 시킨 이진탐색 트리를 균형있는 이진 탐색 트리 ( balanced binary search tree) 라고합니다.

BBST(balanced binary search tree) 의 대표적인 예로 AVL Tree, RedBlack Tree 가 있습니다.

임의의 key 값에 대한 삽입, 삭제, 탐색  O(logN) 을 지원하는 BBST는 사전 자료구조 를 구현하는 좋은 방법 입니다. 

이로인해 임의의 key에 대한 삽입, 삭제, 탐색을 지원하는 stl의 set, map 은 BBST의 일종인 RedBlackTree로 이루어졌습니다.

또한 질문자 님께서 고민하시는 부분은 일반적으로 점급 표기법 (빅 O 표기법) 은 증가율에 대한 표현법입니다.

정확한 계산으로  logN이 되어야 한다는 것이 아니라 N이 아무리 커져도 증가율이 logN 그래프의 모양을 띈다는 의미입니다.

따라서 primitive operatiaon 의 총 수를 inpuit data N에 대한 수학 표현식으로 나타낸 후 ,

최고차항만 나타내는 방식으로 표현합니다.

이러한 점근 표기법을 쓰는 이유는 컴퓨터가 처리할 data가 많아질 시를 어떻게 성능이 달라질지를 고려하기위한 방식입니다.

따라서 input data가 적을 시에는 시간복잡도가 높더라도 단순한 알고리즘을 선택하는게 오히려 효율적일 수 있습니다.

(실예로 stl의 sort는 data의 수에 따라 퀵소트(조건 만족시 O(NlogN)), 인설션소트(O(N^2)), 힙소트(O(NlogN)) 의 조합으로 동작하게 구현되어 있습니다)

단 시간복잡도가 높은 알고리즘은 data가 점차 많아지면 시간복잡도가 보다 낮은 알고리즘보다 성능이 저하될 수 밖에 없습니다.

한마디로 빅오표기법은 input data N에 대한 그래프 모양을 나타낸 방식으로 생각하시면 편하실 겁니다.

최고차항만 나타낼 시 계수를 제외하고 나타냅니다.

예를들어 Input N에 대하여 연산의 수를 계산해보았을 시

7N + 2LogN 이라는 식이 나왔을 때

O(N)으로 표현한 다는 것입니다.

계수를 제외하는 이유는 계수가 아무리 커도 data N이 많아졌을 때, 계수는 의미가 없어집니다.

결국 그래프의 모양은 O(N)인 경우 1차함수의 모양으로 시간은 N과 비례하는 식으로 늘어난다는 것이죠.

10000N 과 N^2 있을 시, N이 10000만 넘어가게되면 바로 N^2 의 성능이 더 떨어질 테고 N이 더욱 커질때의 증가율은 10000N과 N^2은 엄청난 차이이죠.
몇 가지 case를 생각해보시면 빅오표기법의 의미를 이해하시는데 도움이 되실겁니다.

특히 logN 과 N의 차이를 생각해보시면 ( ( O(N) vs O(logN) ) or ( O(N^2) vs O(NlogN) ) 에서 log부분에 계수를 매우 크게 넣고 생각해보세요)
점근표현식을 이해하기 좋으실 것입니다.