Lock-free, constant update-time concurrent tree data-structures?
$O(1)$ doesn't help in and of itself.  In a lock-free data structure there needs to be a single atomic instance when your data structure appears to change.  All the representation invariants need to be in force both immediately before and immediately after that atomic instant.

This means that if you are doing a modification to the data structure the important characteristic is that you can do all the mods on a private data structure and then swap in the modifications in a single atomic instruction.

Lock-freedom is usually easiest when your data structures are immutable (purely functional).  You simply keep a global pointer to the current version of the data structure.  Readers don't need to lock anything.  Modifications to the data-structure are effected by swapping the global pointer to one immutable data structure to another.

For example: if you have a purely functional tree balanced tree you:


Record the current global pointer to the root of the tree.
Create a new tree that inserts or deletes a node.  (This is logarithmic in time and space in the number of nodes currently in the tree, and involves creating new nodes from the modification point up to the root, and just pointing everything new at the old parts of the previous version of the data structure.)
Atomically compare and swap the global pointer to the root.  (Note that this might fail if another modification has happened between the time you recorded the old root pointer and now.  If this happens you go back to step 1 and try again.  This is so-called "optimistic concurrency control.")


Note that the most important part is what I said above about needing to maintain representation invariants.  It is usually not sufficient to have an algorithm that atomically makes a change in the middle of the tree.  Why?  For example: you might have a reader thread that is in the process of doing a preorder traversal of the tree.  If you modify a node that is an ancestor of the node they are currently reading then you are going to invalidate preconditions that they thought they had enforced.  The reader needs to be able to work with the data structure exactly as it was before you made your change, or exactly as it will be after you've made your change.  Not something in between.

Edit: As @Raphael pointed out there are techniques for making mutable data structures lock-free.  A proof by construction that this can always be done is: As long as you have a single global pointer to the "top" of your data structure, even if it is mutable you can always copy the entire data structure, make your mods to the copy, and then, using optimistic concurrency control, try to compare-and-swap the pointer to your newly minted data structure in for the original.  The beauty of functional tree-based data structures is that they keep the cost of copying down at $O(log(N))$ of a size $O(N)$ data structure.