This could be either Geijera parviflora (Australian Willow) or Acacia salicina (Willow Acacia). They are both from Australia and have similar appearance. Here is what Mountain States Wholesale Nursery says about them.

Australian Willow (Geijera parviflora) Native to Australia, this medium sized evergreen tree reaches to 35' by 30'. Olive green leaves are narrow to 2" long and droopy. It is very adapted to arid areas typically surviving with as little as 6" of annual rainfall. It is deep rooted and adapted to high temperatures as well as long periods of drought. The main inner branches are composed of strong, wind resistant wood and are directed upward while outer smaller branches are somewhat pendulous. Young trees have an oval shape while older, more weeping giving it a Weeping Willow like effect. It does cast light shade allowing other plants to grow beneath it. It is not tolerant of poorly drained sites.

Willow acacia (Acacia salicina) will be much easier to find at nurseries. Mountain States says "This evergreen Australian native has grey-green narrow foliage and an upright but pendulous growth habit. It may reach a mature size of about 40' tall by 20' wide. Fragrant, creamy white puffball flowers may appear anytime during the year. Frequently this tree is irrigated too often and shallowly, resulting in rapid growth, poor rooting and loss to high winds. It requires deep, well-drained soil and good water management to create a strong anchoring root system. After establishment, very little additional irrigation is necessary. Pruning to thin the canopy reduces wind resistance. Hardy to 20 °F."

I am not sure if this would apply to Tucson, but the Australian Willow (Geijera parviflora)was planted heavily in the Tempe area in the 1980s. The trees were beautiful and seemed to thrive. Then in the late 1990s and continuing after that a blight or something struck and has killed off many of them. I lost the two that I had. I don't know how wide spread this problem is. I replaced my dead trees with an Arizona Rosewood and an Emerald Green paloverde, which are both very nice.