The paper presents a computationally efficient run-time partitioning and load-balancing scheme for the Distributed Adaptive Grid Hierarchies that underlie adaptive mesh-refinement methods. The partitioning scheme yields an efficient parallel computational structure that maintains locality to reduce communications. Further, it enables dynamic re-partitioning and load-balancing of the adaptive grid hierarchy to be performed cost-effectively. The run-time partitioning support presented has been implemented within the framework of a data-management infrastructure supporting dynamic distributed data-structures for parallel adaptive numerical techniques. This infrastructure is the foundational layer of a computational toolkit for the Binary Black-Hole NSF Grand Challenge project.