树的类型不少,此篇简要对树进行描述,脑中有个整体概念,细节分篇再研究
树(Tree)是n(n>=0)个结点的有限集。
在任意一棵非空树中:
(1)有且仅有一个特定的称为根(Root)的结点;
(2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...,Tn,其中每个集合本身又是一棵树,并称为根的子树(SubTree)
结点:如上图,每一个圈圈我们就称为树的一个结点
二叉树(Binary Tree)是n(n>=0)个结点的有限集合。该集合可能是空的(空二叉树),也可能由 一个根结点和该根结点的左子树和右子树组成。左右子树不相交,而且都是二叉树
除最后一层无任何子节点外,每一层上的所有结点都有两个子结点。也可以这样理解,除叶子结点外的所有结点均有两个子结点。节点数达到最大值,所有叶子结点必须在同一层上
若设二叉树的深度为h,除第 h 层外,其它各层 (1~(h-1)层) 的结点数都达到最大个数,第h层所有的结点都连续集中在最左边,这就是完全二叉树
之前讲过的《堆排序》 就是依赖完全二叉树结构
二叉查找树(Binary Search Tree),又被称为二叉搜索树
(1)若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2) 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3) 任意节点的左、右子树也分别为二叉查找树;
(4) 没有键值相等的节点
复杂度分析:它和二分查找一样,插入和查找的时间复杂度均为O(logn),但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候,树没有保持平衡
平衡二叉搜索树,又被称为AVL树
由于普通的二叉查找树会容易失去”平衡“,极端情况下,*二叉查找树会退化成线性的链表,导致插入和查找的复杂度下降到 O(n) *,所以,这也是平衡二叉树设计的初衷。
具有以下性质:
红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的,他称之为"对称二叉B树",它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n是树中元素的数目
平衡二叉树的插入/删除操作带来的旋转操作可能会达到logn次
红黑树的插入操作最多进行两次旋转、删除操作最多进行三次旋转
B树是一种平衡的多路查找树,结点最大的孩子数目称为B树的阶(Order),是为磁盘存储而专门设计的一类平衡搜索树
b-tree分为用“阶”的定义和用“度”的定义,度和阶都是描述子节点的数量的
这是B树存储在硬盘的逻辑结构图。
其中根节点中17,35在称为关键字(key) ,实际中往往附带更多复杂类型数据。
可以看出一个节点包含 keys ChildNotePointer 2部分信息
这是个典型的b树结构,初始因子为1000,高度仅为3的b树,就可以存储1002001000的数据了
假设要查询最后一个数据:
B树的节点,在硬盘里表现为:柱面里的页(page)或盘块(block),如果把索引持久化到内存,只需要一次就够了
B+树是B-树的变体,也是一种多路搜索树:
B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找
B树:有序数组+平衡多叉树
B+树:有序数组链表+平衡多叉树
B+树的关键字全部存放在叶子节点中,非叶子节点用来做索引,而叶子节点中有一个指针指向一下个叶子节点。做这个优化的目的是为了提高区间访问的性能。而正是这个特性决定了B+树更适合用来存储外部数据
B*树是对B+树进行的又一次的升级。在B+树的非根和非叶子结点再增加指向兄弟的指针
在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;
在这比如说当你进行插入节点的时候,它首先是放到兄弟节点里面。如果兄弟节点满了的话,进行分裂的时候从兄弟节点和这个节点各取出1/3,放入新建的节点当中,这样也就实现了空间利用率从1/2到1/3。
B树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点
B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点; 所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;
B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;
B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;
B-树学习笔记
浅谈算法和数据结构: 十 平衡查找树之B树,而这篇博文里有B树和B+树插入元素的过程GIF图,超赞,有助于对B树和B+树的理解!
从B树、B+树、B*树谈到R 树(这篇文章作者也是好厉害,其博客访问量达千万)