This paper treats with a local-planning algorithm that is suited for real-time re-planning in unknown urban environments on small UAVs with limited computational power. The Finite Receding-Horizon Incremental-Sampling Tree (RHIST) incrementally builds a tree of cubic Bezier-spline paths within a sphere in the vicinity of the plant. To facilitate a distance optimized traverse of complex environments, the tree connection strategy employs samples on the sphere that are connected in an optimal fashion with respect to the current plant state. This enables the planner to achieve locally optimal paths as opposed to the nonoptimal nearest neighbor strategy of the well-known RRT-algorithm. Robustness against unknown but bounded position disturbances is achieved by enclosing spline paths with Oriented Bounding Boxes (OBBs), whose magnitude is dependent on the current position deviation of the plant. As a substitute of an underlying mass-point model, flight path constraints are accounted for on the spline. An approximation of the load factor serves as flight envelope protection through the consideration of the path-following controller structure even for off-path cases. Simulation results and Hardware-in-the-Loop (HiL) testbed results demonstrate the performance in urban environments and the real-time capability of the RHIST algorithm.