Kerry Mills song Red Wing is actually about an Indian maid and is sometimes performed as an instrumental and sometimes as a song. There are several fiddle tunes going by the name of Red Bird. Here is a link to a nice one on youtube;

Red Bird

Clark Kessinger's version of Red Bird is one of my favorites.

There is also a tune called Oklahoma Red Bird.

Getting into modern songs; The Beatles' Blackbird is a good one.