201608-04 图解:二叉搜索树算法(BST) 72 VIEW 一、树 & 二叉树 树是由节点和边构成,储存元素的集合。节点分根节点、父节点和子节点的概念。 如图:树深=4; 5是根节点;同样8与3的关系是父子节点关系。 .... Read More >
201607-26 浅谈算法和数据结构: 十 平衡查找树之B树 60 VIEW 前面讲解了平衡查找树中的2-3树以及其实现红黑树。2-3树种,一个节点最多有2个key,而红黑树则使用染色的方式来标识这两个key。 维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n).... Read More >
201607-26 浅谈算法和数据结构: 八 平衡查找树之2-3树 45 VIEW 前面介绍了二叉查找树(Binary Search Tree),他对于大多数情况下的查找和插入在效率上来说是没有问题的,但是他在最差的情况下效率比较低。本文及后面文章介绍的平衡查找树的数据结构能够保证在最差的情况下也能达到lgN的效率,要实现这一目标我们需要保证树在插入完成之后始终保持平衡状态,.... Read More >
201607-26 浅谈算法和数据结构: 七 二叉查找树 58 VIEW 前文介绍了符号表的两种实现,无序链表和有序数组,无序链表在插入的时候具有较高的灵活性,而有序数组在查找时具有较高的效率,本文介绍的二叉查找树(Binary Search Tree,BST)这一数据结构综合了以上两种数据结构的优点。 二叉查找树具有很高的灵活性,对其优化可以生成平.... Read More >