Device for sorting data elements in a binary tree and ATM spacer including such a device

摘要

A sorting equipment for data elements uses a memory which is organised as a binary tree. The tree has (n) stages with (2n-1) nodes and any stage (q) includes nodes (2q to 2q+1-1). The tree is controlled such that for any given node (i) the nodes 2i and 2i+1 either don't contain a key or it is superior or equal to that of the given node (i). The means of controlling the tree comprise successive controllers (21q) which are associated with corresponding tree stages (20q) and interface pipeline registers (26q) which transmit modifications to the contents of the tree along the stages and permit parallel working of the controllers.