In search trees with relaxed balance, updating and rebalancing have been uncoupled such that rebalancing can be controlled separately. Re- cently, it has been shown how an advanced update such as an insertion of an entire tree into a relaxed multi-way structure can be implementation efficiently. This indicates a similar result for binary trees by a naive interpretation of Small multi-way tree nodes as binary configurations. However, this would Imply that nodes must be connected by level links, which significantly devi- Ates from the usual structural implementations of binary trees. In this paper, We show that it is possible to define binary schemes which are both natural And efficient.
展开▼
