AVL

AVL(balance binary tree)#

  • AVL树本质上还是一棵二叉搜索树; AVL树的任何子树仍然是AVL树; 每个节点的左右子节点的高度之差的绝对值最多为1

AVL Imbalance#

  • 节点失衡, 节点左子树与右子树高度差大于1

LL#

  • 发生条件: 插入新节点, 节点失衡, 左子树比右子树高2, 造成失衡的子节点是左子树
  • 调整方式: 右旋

LR#

  • 发生条件: 插入新节点, 节点失衡, 左子树比右子树高2, 造成失衡的子节点是右子树
  • 调整方式: 左子树左旋, 转化为LL失衡, 再右旋

RR#

  • 发生条件: 插入新节点, 节点失衡, 右子树比左子树高2, 造成失衡的子节点是右子树
  • 调整方式: 左旋

RL#

  • 发生条件: 插入新节点, 节点失衡, 右子树比左子树高2, 造成失衡的子节点是左子树
  • 调整方式: 右子树右旋, 转化为RR失衡, 再左旋

_left_rotate# 

static ngx_inline void
bst_left_rotate(bst_node_t **root, bst_node_t *sentinel,
    bst_node_t *node)
{
    bst_node_t  *temp;

    temp = node->right;
    node->right = temp->left;

    if (temp->left != sentinel) {
        temp->left->parent = node;
    }

    temp->parent = node->parent;

    if (node == *root) {
        *root = temp;

    } else if (node == node->parent->left) {
        node->parent->left = temp;

    } else {
        node->parent->right = temp;
    }

    temp->left = node;
    node->parent = temp;
}

_right_rotate# 

static ngx_inline void
bst_right_rotate(bst_node_t **root, bst_node_t *sentinel,
    bst_node_t *node)
{
    bst_node_t  *temp;

    temp = node->left;
    node->left = temp->right;

    if (temp->right != sentinel) {
        temp->right->parent = node;
    }

    temp->parent = node->parent;

    if (node == *root) {
        *root = temp;

    } else if (node == node->parent->right) {
        node->parent->right = temp;

    } else {
        node->parent->left = temp;
    }

    temp->right = node;
    node->parent = temp;
}