Java集合核心内容之二叉树,大厂越来越注重基础了,建议收藏

时间:2021-6-19 作者:admin

Java集合核心内容之二叉树,大厂越来越注重基础了,建议收藏

  数组查询的效率很高但是添加和删除的效率会很低,链表的添加和删除的效率很高但是查询的效率又很低,这时有没有更好的选择方案呢?这时二叉树出现了。

二叉树

1 相关概念

  ​ 二叉树:每个子节点只有两个节点的树,每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。
Java集合核心内容之二叉树,大厂越来越注重基础了,建议收藏
二叉查找树也称为有序二叉查找树,满足二叉查找树的一般性质,是指一棵空树具有如下性质:

  1. 任意节点左子树不为空,则左子树的值均小于根节点的值

  2. 任意节点右子树不为空,则右子树的值均大于于根节点的值

  3. 任意节点的左右子树也分别是二叉查找树

  4. 没有键值相等的节点

二叉树又分为:完美二叉树,完全二叉树,完满二叉树

完美二叉树:又称为满二叉树,除了叶子节点之外的每一个节点都有两个孩子节点,每层都被完全填充Java集合核心内容之二叉树,大厂越来越注重基础了,建议收藏
完全二叉树:除了最后一层之外的其他每一层都被完全填充,并且所有的节点都保持向左对齐
Java集合核心内容之二叉树,大厂越来越注重基础了,建议收藏

完满二叉树:除了叶子节点之外的每一个节点都有两个孩子节点。
Java集合核心内容之二叉树,大厂越来越注重基础了,建议收藏

2 遍历操作

  二叉树中的遍历规则有如下三种:

中序遍历:所谓的中序遍历就是先访问左节点,再访问根节点,最后访问右节点,即左-根-右遍历

先序遍历:所谓的前序遍历就是先访问根节点,再访问左节点,最后访问右节点,即根-左-右遍历(前序)

后序遍历:所谓的后序遍历就是先访问左节点,再访问右节点,最后访问根节点。即左-右-根遍历
Java集合核心内容之二叉树,大厂越来越注重基础了,建议收藏查找最小值:沿着根节点的左子树一路查找,直到最后一个不为空的节点,该节点就是当前这个树的最小节点

查找最大值:沿着根节点的右子树一路查找,直到最后一个不为空的节点,该节点就是当前这个树的最大节点

查找前驱节点:小于当前节点的最大值

查找后继节点:大于当前节点的最小值Java集合核心内容之二叉树,大厂越来越注重基础了,建议收藏

3 删除节点

  二叉树中的删除节点:本质上是找前驱节点或者后继节点来替代

  • 叶子节点直接删除
  • 只有一个子节点的用子节点替代(本质上就是找的前驱节点或者后继节点,左节点就是前驱节点,右节点就是后继节点)
  • 有两个子节点的,需要找到替代节点(替代节点就是前驱节点或者后继节点)

4 查找局限性

​    一个二叉查找树是由n个节点随机构成,所以,对于某些情况,二叉查找树会退化成一个有n个节点的线性链.如下图

Java集合核心内容之二叉树,大厂越来越注重基础了,建议收藏

AVL

  BST存在的问题是,树在插入的时候会导致倾斜,不同的插入顺序会导致数的高度不一样,而树的高度直接影响了树的查找效率。最坏的情况所有的节点都在一条斜线上,这样树的高度为N。基于BST存在的问题,平衡查找二叉树(Balanced BST)产生了。平衡树的插入和删除的时候,会通过旋转操作将高度保持在LogN。其中两款具有代表性的平衡术分别为AVL树(高度平衡树,具备二叉搜索树的全部特性,而且左右子树高度差不超过1)和红黑树。

  AVL树是如何实现平衡的呢?,具体是通过左旋或者右旋来实现的。具体如下图:
Java集合核心内容之二叉树,大厂越来越注重基础了,建议收藏

  虽然AVL可以解决二叉树所存在的问题,但是AVL树要求太过严格,左旋和右旋的开销会比较大,这时出现了红黑树,只要求黑色节点平衡即可。下篇我们介绍红黑树!

声明:本文内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎进行举报,并提供相关证据,工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。