Skip to main content
forgot to close quotes
Source Link
jbapple
  • 3.4k
  • 17
  • 21

It sounds like you're looking for a binary search tree with the working-set property; this is a good bit weaker than dynamic optimality. In fact, there are no known binary search trees with dynamic optimality, according to Iacono's "In pursuit of the dynamic optimality conjectureconjecture" from June 2013.

But, if you're looking for the simpler working-set property, you're in luck! The working-set property is that the time to access an item $x$ is proportional to the log of the number of items accessed since $x$ was last accessed.

There are a variety of structures with the working-set property. There is even one that is a binary tree, meets both the logarithmic worst-case bound and the working-set property in the worst-case, not just the amortized case: Bose et al's "Layered Working-Set Trees".

It sounds like you're looking for a binary search tree with the working-set property; this is a good bit weaker than dynamic optimality. In fact, there are no known binary search trees with dynamic optimality, according to Iacono's "In pursuit of the dynamic optimality conjecture from June 2013.

But, if you're looking for the simpler working-set property, you're in luck! The working-set property is that the time to access an item $x$ is proportional to the log of the number of items accessed since $x$ was last accessed.

There are a variety of structures with the working-set property. There is even one that is a binary tree, meets both the logarithmic worst-case bound and the working-set property in the worst-case, not just the amortized case: Bose et al's "Layered Working-Set Trees".

It sounds like you're looking for a binary search tree with the working-set property; this is a good bit weaker than dynamic optimality. In fact, there are no known binary search trees with dynamic optimality, according to Iacono's "In pursuit of the dynamic optimality conjecture" from June 2013.

But, if you're looking for the simpler working-set property, you're in luck! The working-set property is that the time to access an item $x$ is proportional to the log of the number of items accessed since $x$ was last accessed.

There are a variety of structures with the working-set property. There is even one that is a binary tree, meets both the logarithmic worst-case bound and the working-set property in the worst-case, not just the amortized case: Bose et al's "Layered Working-Set Trees".

Source Link
jbapple
  • 3.4k
  • 17
  • 21

It sounds like you're looking for a binary search tree with the working-set property; this is a good bit weaker than dynamic optimality. In fact, there are no known binary search trees with dynamic optimality, according to Iacono's "In pursuit of the dynamic optimality conjecture from June 2013.

But, if you're looking for the simpler working-set property, you're in luck! The working-set property is that the time to access an item $x$ is proportional to the log of the number of items accessed since $x$ was last accessed.

There are a variety of structures with the working-set property. There is even one that is a binary tree, meets both the logarithmic worst-case bound and the working-set property in the worst-case, not just the amortized case: Bose et al's "Layered Working-Set Trees".