链表/二叉树/平衡二叉树/红黑树

链表/二叉树/平衡二叉树/红黑树

当你还不能对自我说这天学到了什么东西时,你最好就不要去睡觉

最近也在看HashMap相关的东西,你知道的这基本是面试必问的东西;据说很多兄弟都是败在了HashMap的夺命连环问上的,然后铭心自问发现自己也说不清楚;那怎么办呢?当然是硬着头皮上呗,在研究HashMap的原理前,我们是需要了解链表、二叉树、平衡二叉树、红黑树这些数据结构的;特别说明下,本文只是为了说清楚各种数据结构的概念及特点,对于更深层次的算法探究这里不作扩展!

链表

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的;

它的数据结构如下图所示(注意:这里的指针实际上指的是存储的对next节点数据的引用地址!)

链表

从图中,我们可以了解到:

  • 链表在物理结构上是不连续的
  • 它是大小是不确定的,链表的大小可以动态的按需分配的
  • 对于尾节点来说,它的指针为null
  • 在数据结构上来说,它是连续的,通过指针连续,故没有内存空间的浪费

链表的优点:

  • 增,删节点效率高;因为只需要改变前面节点和当前节点的指针就可以了
  • 链表在物理结构上是不连续的,所以对内存的利用率是极高的(内存就像一个杯子,链表这种结构每个节点就相当于一粒粒沙子,只要有点空间都可以利用,即它不要求连续的大空间)
  • 链表的大小可以动态增减,可以做到灵活扩展

链表的缺点:

  • 查询效率低;当查询某个节点,因为它是散乱分布的;并不知道每个节点的具体位置,所以不得不遍历获取!

上图所示的只是一个单链表,其实链表还有很多种,例如双向链表,循环单链表,循环双链表等;对于链表的更多知识,请参考博客:数据结构--基于java的链表实现

二叉树

二叉树是一种每个节点最多只有两个分支节点的树形的数据结构,它的数据结构如下图所示:

二叉树

从图中,我们可以了解到:

  • 二叉树每个节点最多两个子节点
  • 处于顶层的是根节点;处于同一层的,同一个父节点的是兄弟节点
  • 没有子节点的是叶节点(叶子就是末梢了,不会再长出新的东西来)

二叉树的子节点,又可以称为左子节点和右子节点;二叉树的优点是增删查都快,缺点是算法复杂;

平衡二叉树

了解平衡二叉树之前,我们需要知道 二叉查找树,二叉查找树是一种有特殊规范的二叉树,二叉查找树又被称为二叉搜索树、有序二叉树、排序二叉树;

那什么样的树才叫二叉查找树呢?看下图:

二叉查找树

上图就是一个标准的二叉查找树,它符合以下的规范:

  • 若任意节点的左子树不为空,则左子树的值均小于它根节点的值;
  • 若任意节点的右子树不为空,则右子树的值均大于它根节点的值;
  • 任意节点的左子树,右子树都为二叉查找树(开始套娃了,哈哈);

那么什么叫平衡二叉树呢?为啥非得要说清楚二叉查找树再说平衡二叉树呢?

其实所谓的平衡二叉树是指改进的二叉查找树,为了减少二叉查找树的深度,平衡二叉树将二叉查找树的节点平均的分布;一般而言,随着树的深度提高查询的平均复杂度就会提高,因此为了实现更好的查询效率就提出了平衡二叉树的这一数据结构!

如下图,我们看下非平衡二叉树和平衡二叉树的区别:

非平衡二叉树&平衡二叉树

其实平衡二叉树比二叉查找树多了个平衡的特点,它体现在:平衡二叉树的任意节点的左子树高度和右子树高度差值都不能大于1;

这里需要说明一个平衡因子的概念:我们将二叉树上节点的左子树深度减去右子树深度的值称为平衡因子BF(Balance Factor),那么平衡二叉树上所有节点的平衡因子只可能是-1,0,1;只要二叉树上有一个节点的平衡因子的绝对值大于1,则该二叉树就是不平衡的;

那么当扩展到N个节点来看,平衡二叉树优势明显;它显著的减少了查询的深度,从而提高了查询的效率;

红黑树

了解了平衡二叉树后,我们再来看下什么样的树叫红黑树;如下图所示:

红黑树

红黑树除了具有二叉查找树的基本特点外,还具有以下几个特点:

  • 各节点是红色或黑色,根节点是黑色
  • 所有的叶子节点都是空节点(NIL节点)且是黑色
  • 每个红色的节点都必须有两个黑色的子节点(每个叶子节点到根节点的路径上不能有连续的两个红色节点)
  • 每个节点到该节点下的子孙节点的所有路径上,包含同等数目的黑色节点

红黑树的优点:相对于普通的二叉树来说,普通的二叉树可能退化为链表的形式,那么时间复杂度会退化到O(n);而红黑树是一种在平衡二叉树上又添加了新特点的树形结构,它的高度趋近于log2n,它的添加删除查询的时间复杂为O(log n)。

红黑树是一种自平衡的平衡二叉树,它保持自平衡和红黑树特点的方式是:变色,左旋和右旋;

对比AVL树

AVL树也是一种自平衡树(本质也是一种二叉排序树,二叉搜索树,只是在此之上增加了平衡的特点),它和红黑树的不同在于,它增加了节点高度的属性,保存了各个节点的高度信息(以确保各节点的平衡因子绝对值不大于1);而红黑树也包含了AVL的特性,只是实现不同,它增加了红黑属性的定义,更加简单的确保了树的再平衡计算,并且相比较每个节点记录高度信息来说,节省了内存;

小结:关于链表,二叉树,平衡二叉树,红黑树的概念及其理解就先总结到这里;后面我们将继续了解,HashMap的底层实现,接下来就是扒源码啦。

更多的数据结构知识,推荐经典书籍《大话数据结构》