My iCloud deleted some of my pictures and videos, how can I get them back?

In addressing the first part of your post, I suggested checking the Recently Deleted folder because photos remain there for a period of 30 days then are permanently deleted (iCloud: Delete photos from My Photo Stream).

As for the second part, I do agree that one should be able to free space from their iPhone while being assured their photos/videos remain in iCloud however iCloud wasn't designed that way unfortunately meaning that folks will have to consider using a third party service, e.g. Dropbox, Flickr, Google Photos. The most you, and others can do, is suggest it to Apple at http://www.apple.com/feedback/ and hopefully it'll change in future.

@Zinacef if you delete photos from the photos app on your phone they are automatically deleted from ICloud...unless and I believe they are in folders they are safe but are harder to retreive meaning you have to email them individually because your iphone cant handle the folder size even in an email ...but their msy be hope .....if you look in the folders they catagories like last import and burst but you may get lucky because sometimes they are in a folder called recently deleted. This is also on your iphone, but often i will delete it all on my phone but it somethimes temains in the ivloud version and im sure you know to enter your Apple Id and password and check it out...if you have iCloud Drive they could be in a folder in there but that all depe on your icloud space...i pay for extra storage and its cheep but nothing gets deleted for lack of space...if you are low ...it could have tried to downlo into your Icloud drive on in your finder on you computer or if you have an iphone with drive see if they are there...Im not a complete genius with this stuff but thst is the knowledge i have been seeing in experience...thats also why people have complaints about the cloud, it is a double egde sword that it changes together ......some people dont want pics on their phone from five years ago but dont want to erase them but that is how the new photo app is supposed to work .....its great if you want changes to acresume and your moving from a phone to a computer the changes show up so you dont need to modify twice but with pics its not so wonderful because on our phones are sometimes limited...apple would be and id capable to have folder to tap into and just AirDrop to your phone...its simple to me...as long as the iphone is synced with you device

You can also try going to iCloud.com and then select Photos. At the top right where your name is, click the dropdown menu, and select iCloud Settings. When that page loads, look at the bottom left side under Advanced and you can restore from there.

You could check the Recently Deleted folder to see if they're in there. If not, they may be gone permanently.