TADM2E 3-6
From Algorithm Wiki
Modify insert and delete: Pointers to successor and predecessor can be found in O(log n) time upon insertion. Store these in the Node. predecessor(void * pcNode) and successor(void * pcNode) take O(1). Upon deletion of Node, successor of the predecessor becomes the predecessor of the successor.
