A logical balanced tree structure can be overlaid on a peer-to-peer (P2P) network to support both exact match and range queries. Load balancing mechanisms are needed for handling skew problems in a tree-structured network. Traditional load balancing operations, such as sequentially probing for helper nodes and readjusting the tree structure after moving a node, may incur high costs. This research develops two new parallel load balancing strategies: vicinity load balancing and virtual group load balancing. The former adopts parallel transmission techniques to distribute the load of an overloaded node over a set of neighboring nodes, and the latter redirects the load of an overloaded node to a lightly loaded region. Simulation results indicate that these strategies are efficient not only in time and message, but also in the work load of participant nodes.