参照物 一文读懂 AVL 树(7)

}

Node * AVL::find(int key)

{

return find_real(key, header->left);

}

void AVL::erase(int key)

{

header->left = erase_real(key, header->left);

}

void AVL::print()

{

in_order(header->left);

cout << endl;

}

int main()

{

AVL avl;

// test "insert"

avl.insert(7);

avl.insert(2);

avl.insert(1); avl.insert(1);

avl.insert(5);

avl.insert(3);

avl.insert(6);

avl.insert(4);

avl.insert(9);

avl.insert(8);

avl.insert(11); avl.insert(11);

avl.insert(10);

avl.insert(12);

avl.print(); // 1 2 3 4 5 6 7 8 9 10 11 12

// test "find"

Node * p = nullptr;

cout << ((p = avl.find(2)) ? p->key : -1) << endl; // 2

cout << ((p = avl.find(100)) ? p->key : -1) << endl; // -1

// test "erase"

avl.erase(1);

avl.print(); // 2 3 4 5 6 7 8 9 10 11 12

avl.erase(9);

avl.print(); // 2 3 4 5 6 7 8 10 11 12

avl.erase(11);

avl.print(); // 2 3 4 5 6 7 8 10 12

return 0;

}

起初构造的 AVL 树为下图：

总结

和二叉查找树相比，AVL 树的特点是时间复杂度更稳定，但缺点也是很明显的。

插入操作中，至多需要一次恢复平衡操作，递归回溯的量级为 O(logn)。有一点需要我们注意，在对第一个失衡结点进行恢复平衡后，递归回溯就应该立即停止（因为失衡结点的父亲及其祖先们肯定都是处于平衡状态的）。

但让 "递归的回溯" 中途停止，不好实现，所以我上面的编码程序都不可避免的会继续回溯，直到整棵树的根结点，而这些回溯都是没有必要的。（谢谢 LLL 的提醒，若在结点中增设父亲结点，就可以解决递归回溯的问题）

删除操作中，若存在失衡，则至少需要一次恢复平衡操作，递归回溯的量级亦为 O(logn)。与插入操作不同，当对第一个失衡结点恢复平衡后，它的父亲或者是它的祖先们也可能是非平衡的（见下图，删除 1），所以删除操作的回溯很有必要。

没有参照物对比的探讨是没有意义的，所以此文就止于此吧，有兴趣的朋友可以看下我后面《红黑树》及《AVL 树与红黑树的对比》的文章。

参考文献

维基百科. AVL 树.

GeeksforGeeks. AVL Tree | Set 1 (Insertion).

GeeksforGeeks. AVL Tree | Set 2 (Deletion).