insertion of a key into a wavl tree is performed by performing a search for the external node where the key should be added, replacing that node by an internal node with data item and two external-node children, and then rebalancing the tree. the rebalancing step can be performed either top-down or bottom-up, but the bottom-up version of rebalancing is the one that most closely matches avl trees.