Apparently, since 1.4.2, the game is spawning everything everywhere. Have seen desert temples in taiga, villages in the middle of the ocean, witches huts in deserts, and desert villages in the middle of a snowy mountain.

Just an hour ago, I found a witches hut in the middle of the ocean.