哈希AVL树的查找

    哈希AVL树的查找和哈希表类似，唯一的区别就是哈希表是找到bucket序号后按链表的顺序进行查找，而哈希AVL树则是找到bucket序号后进行AVL树的查找。下面通过在图6-15所示中的哈希AVL树中查找数值17来介绍哈希AVL树的查找过程。

    首先将17除以8，余数为1，得到bucket序号为1，从序号为1的bucket中开始查找，第1个位置为节点9，9小于17，因此再查找节点9的右节点，为节点17，就找到了要找的节点。查找过程如图6-16中的粗线所示。

图6-16  哈希AVL树的查找过程图

    从查找过程可以看出，当某个bucket中存放的数据非常多时，也就是哈希表中的某个bucket冲突数据非常多时，采用哈希AVL树方式存放这些冲突数据对查找效率会有明显的提高。

    哈希AVL树的插入

    哈希AVL树的插入需要先找到bucket位置，然后在bucket指向的AVL树中进行插入，下面还是以图6-15中的数据为例来介绍哈希AVL树的插入过程。

    假设要按17，11，20，9，14，1， 22， 25的顺序在哈希AVL树中进行插入，插入过程如下。

    步骤1：插入节点17，17除以8余1，因此插入在位置1上，如图6-17所示。

图6-17  插入节点17之后的情况

    步骤2：插入节点11和节点20，11除以8余3，节点11插入在位置3上，20除以8余4，节点20插入在位置4上，如图6-18所示。

图6-18  插入节点11、节点20之后的情况

    步骤3：再插入节点9，9除8余1，因此也需要插入在位置1上，由于位置1上已有节点17，而9比17小，因此节点9插入在节点17的左边，如图6-19所示。

图6-19  插入节点9之后的情况

    步骤4：插入节点14，14除以8余6，因此将节点14插入在位置6上，如图6-20所示。

图6-20  插入节点14之后的情况

    步骤5：插入节点1，1除以8余1，因此将节点1插入在位置1上，但由于位置1原来有节点17和9，按AVL树的插入操作，需要做一次右旋操作来进行平衡，如图6-21所示。

图6-21  插入节点1之后的情况

    步骤6：插入节点22，22除以8余6，因此插入在位置6上，但由于位置6上原来已有节点14，所以将节点22插入在节点14的右边，如图6-22所示。

图6-22  插入节点22之后的情况

    步骤7：插入节点25，25除8余1，因此插入在位置1上，由于原来已有数据，将节点25插入在AVL树的最右边，如图6-23所示。

 图6-23  插入节点25之后的情况

    哈希AVL树的删除

    下面通过从图6-23所示的哈希AVL树中删除节点1来介绍哈希AVL树的删除过程。

    步骤1：先用1除以8余1，因此从bucket数组中的第1个位置开始查找，找到后将节点1删除掉，删掉的部分如图6-24中的虚线所示。

图6-24  删除节点1之后的情况

    步骤2：删除掉节点1后，由于节点9的左右高度差为2，要调整AVL树的平衡，需要做一次左旋操作，删除后的结果如图6-25所示。

图6-25  删除节点1之后进行左旋调整平衡后的情况