It is not a "gift" in the US tax sense. Employer gifts are almost always taxable income in the US. There are exceptions for certain fringe benefits, but something from your employer that is either cash or has a direct cash value is basically never tax-free as a "gift." Shares in a publicly traded corporation have a readily knowable price, so this is like a cash bonus. It's a share bonus, even if they call it a gift.
These publications might help:
My guess would be they think this is US-connected income and yes, they are withholding taxes to pay the IRS. Maybe they do not think it is US-connected income, but they need to be careful because they do not know if any of their non-US employees will be US tax residents for 2019, so they withhold out of caution.
You should consider filing a US income tax return first quarter of 2020. That would be IRS Form 1040NR (this link is to the 2018 form; you need to wait for the 2019 form to be published). If your employer withheld too much tax, you can get a refund. I'm not sure why they want to withhold 45%. I thought the typical rate was 30%.
I think it would be appropriate to ask your employer if they can help you understand the withholding. They might have a standardized explanation they forward to you or they might get a person to respond specifically to you. In either case, I would avoid being confrontational or difficult and definitely avoid accusing them of being wrong. Just ask them to help you understand so you are able to correctly fill out your US tax return Form 1040NR.
If you have co-workers or colleagues at the same company who are also non-US residents and non-US citizens, you might be able to ask them about it if they are also getting share bonuses.
I would also lower your expectations. It is possible that this is appropriately taxable in the US, if it counts as an employee bonus from a US corporation. Maybe they are withholding just because they do not know if you are a US tax resident, in which case you might get a refund. But maybe they know of a reason this counts as US-source income, in which case you would be taxed. So you should not expect to get all your money refunded. Sorry, maybe your employer can give you better guidance.