Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 »  数据结构标签

AVL树

AVL树是一种自平衡的二叉查找树(Balanced Binary Tree),由于其任意节点的左右子树的高度差至多为一,查找、插入、删除等操作的复杂度在平均和最坏情况下都是O(log n)。AVL树和红黑树都是平衡的二叉查找树,但二者有一些细微的区别,本文将详细讲解AVL树的原理与实现,并且部分实现过程参照了红黑树,具体可以参考 红黑树

继续阅读»

红黑树

二叉查找树可以方便地维护一个动态集合,实现快速的添加、删除以及查询操作。但仅仅当树的高度较低时执行速度较快,当树的高度增加甚至变得极度不平衡时,各种操作的性能急剧下降。红黑树(Red-Black Tree,RBT)是一种平衡的二叉查找树,能在最坏情况下仍然获得较好的时间复杂度。目前C++ STL中包括set、multiset、map、multimap等多种数据结构内部都使用了红黑树或者其变体进行实现。
本文参考算法导论中红黑树章节,将详细介绍红黑树的原理及其在C/C++中的具体实现代码。注意,红黑树的思想及实现跟普通的二叉查找树关系非常大,如果你对二叉查找树还不是非常熟悉,建议先阅读此文:二叉查找树 http://noalgo.info/603.html

继续阅读»

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论