如何改造AVL树以实现O(1)时间复杂度查询后继与前驱

核心实现逻辑是在原有AVL树的结构基础上，额外维护一个有序双向链表，所有树节点同时属于AVL树和双向链表两个结构，双向链表的节点顺序和AVL树的中序遍历顺序完全一致，这样就能直接通过指针读取获得前驱、后继节点。

具体改造细节 #

• 节点结构改造
  在原有AVL树节点的val、left、right、height属性基础上，新增两个指针：prev指向当前节点的前驱节点，next指向当前节点的后继节点，伪代码定义如下：

struct AVLNode {
    int val;
    int height;
    struct AVLNode *left;
    struct AVLNode *right;
    struct AVLNode *prev; // 前驱指针
    struct AVLNode *next; // 后继指针
};

• 插入操作改造
  执行原有AVL树的插入逻辑定位到插入位置时，同步确定新节点的前驱和后继：

  1. 若新节点作为父节点的左子节点插入：新节点的后继为父节点，前驱为父节点原本的前驱节点，同步更新对应节点的prev/next指针即可
  2. 若新节点作为父节点的右子节点插入：新节点的前驱为父节点，后继为父节点原本的后继节点，同步更新对应节点的prev/next指针即可
     注意：AVL树的旋转操作只会调整树的拓扑结构，不会改变节点的中序遍历顺序，因此旋转过程不需要修改双向链表的任何指针，不会增加额外复杂度

• 删除操作改造
  执行原有AVL树的删除逻辑之前，先将要删除的节点从双向链表中摘除：将待删节点的prev->next指向待删节点的next，将待删节点的next->prev指向待删节点的prev，再执行后续的AVL删除、旋转逻辑即可，同样不需要处理旋转过程的链表指针。

• 目标操作实现
  两个目标操作可以直接通过读取节点指针实现，时间复杂度严格O(1)：

  • Successor操作直接返回node->next，若返回空则说明当前节点是树的最大值节点
  • Predecessor操作直接返回node->prev，若返回空则说明当前节点是树的最小值节点

额外说明 #

该改造方案仅在插入、删除操作中增加了常数次指针修改操作，不会改变AVL树原有插入、删除O(log n)的时间复杂度，仅增加了常数级的空间开销。

内容的提问来源于stack exchange，提问作者user10082181