二叉查找树,红黑树 B-树学习笔记整理(部分类容来自网络)
注意:(二叉查找/排序/搜索树,红黑树,平衡二叉树)的时间复杂度T(n)=O(lgn)默认是以2为底的.
二叉查找/搜索/排序树BST(binary search /sort tree)(可以指对一个树的操作,也可以指满足某种结构的树)
或者是一颗空树
或者是具有下列性质的二叉树:
1.若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值
2.若它的右子树不为空,则右子树上所有节点的值均大于它根节点的值.
3.它的左子树,右子树也分别为二叉排序树.
(这种结构的树便于更好的对树进行查找(一次排除一半的树),删除,修改,添加.)
平衡二叉树(Self-balancing binary search tree)自平衡二叉树,又被称为AVL树(有别于AVL算法)
它是一棵空树
或它的左右两个子树的高度差(平衡因子) 的绝对值不超过1
且左右两个子树都是一棵平衡二叉树
同时,平衡二叉树必定是二叉搜索树,反之则不一定.
平衡因子(平衡度): 节点的平衡因子是节点的左子树的高度减去右子树的高度(或反之定义)
平衡二叉树:每个节点的平衡因子都为1,-1,0,的二叉排序树.或者说每个节点的左右子树的高度最多差1的二叉排序树.
平衡二叉树的目的是为了减少二叉查找树层次,提高查找速度.同时也是为了避免二叉查找树出现极端现象(比如上图中那个红色的二叉查找树.它是树,却不得不一一遍历找到指定节点.)
平衡二叉树的常用实现方法有AVL,红黑树,替罪羊树,Treap,伸展树等.
红黑树
R-B Tree,全称是Red-Black Tree. 又称为 "红黑树", 它是一种平衡二叉树,红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)
红黑树的特性
1.每个节点或者是黑色,或者是红色.
2.根节点是黑色
3.每个叶子节点(NIL)是黑色.[注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
4.如果一个节点是红色的,则它的子节点必须是黑色的.
5.从一个节点到该节点的子孙节点的所有路径包含相同的黑节点.(确保了没有一条路径会比其他路径长出两倍.因而,红黑树是相对接*衡的二叉树)
红黑树的应用比较广泛,主要用来存储有序的数据,它的时间复杂度为O(longN),效率非常高.
它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的;它可以在O(long N)时间内做查找,插入,和删除.这里的n是树中元素的数目.
例如,Java集合中的TreeSet和TreeMap, C++STL中的set,map,以及linux虚拟机内存的管理,都是通过红黑树去实现的.
B树(balanced tree)
平衡树和二叉平衡树的区别
1.与二叉平衡树相比,是多叉的.
2.可以降低树的深度,提高查找效率.
B树应文件系统的要求而发展起来的,大量数据存放在外村中,通常存放在硬盘中.
由于是海量数据,不可能一次调入内存.因此,要多次访问外存.但是硬盘的驱动受机械运动的制约,速度慢.
所以,主要矛盾变为减少防外存次数,在1972年由R.Bayer和E.Macreight,提出用B树作为索引组织文件,提高访问速度,减少时间
B+树.
在B-树的基础上,为叶子节点增加链表指针,所有关键字都在叶子节点出现,非叶子节点作为叶子节点的索引.
B+树总是到叶子节点命中.
数据库的索引的默认数据结构就是采用B+树.
B*树
是B+树的变体,在B+树的非根和非叶子节点再增加指向兄弟的指针.