首页 > 其他分享 >面试中可能问到的几种树结构(二叉树,平衡二叉树,红黑树,B树和B+树)

面试中可能问到的几种树结构(二叉树,平衡二叉树,红黑树,B树和B+树)

时间:2024-03-16 19:00:30浏览次数:21  
标签:结点 树结构 查询 关键字 查找 二叉树 红黑树 节点

二叉树的概念

二叉树是一种树形结构,其特点是每个结点至多只有两棵子树( 即二叉树中不存在度大于2的结点),并且二叉树的子树有左右之分,其次序不能任意颠倒。

平衡二叉树概念

平衡二叉树,是二叉树的一种变形,左子树的深度和右子树的深度不能超过一。

红黑树概念

红黑树是一种自平衡的二叉查找树,是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明,在当时被称为平衡二叉 B 树(symmetric binary B-trees)。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的红黑树。红黑树具有良好的效率,它可在 O(logN) 时间内完成查找、增加、删除等操作。

B-Tree树概念

 1.首先每个子节点最多只有m个子节点(m是树的阶)。

2.除根节点外,每个非叶子节点具有至少有 m/2(向下取整)个子节点

3.非叶子节点的根节点至少有两个子节点。

4.有k颗子树的非叶节点有k-1个键,键按照递增顺序排列。

5.叶节点都在同一层中。

什么是B树的阶?

B树中一个子节点的最大节点数,用m表示,例如途中右边{13.16.19}的子树有四个所以m为4.

为什么会存在B树?

1.2 B树出现的目的
B树的出现是为了弥补不同的存储级别之间的访问速度上的巨大差异,实现高效的 I/O。平衡二叉树的查找效率是非常高的,并可以通过降低树的深度来提高查找的效率。但是当数据量非常大,树的存储的元素数量是有限的,这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B树是解决这个问题的很好的结构。

 B+树

一颗m阶的B+树满足如下条件:

  • 每个节点最多只有m个子节点。
  • 除根节点外,每个非叶子节点具有至少有 m/2(向下取整)个子节点。
  • 非叶子节点的根节点至少有两个子节点。
  • 有k颗子树的非叶节点有k个键,键按照递增顺序排列。
  • 叶节点都在同一层中。

B+树为什么比B树更适合数据库的索引查询

1)B+树的磁盘读写代价更低

B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了;

2)B+树查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当;

3)B+树便于范围查询(最重要的原因,范围查找是数据库的常态)

B树在提高了IO性能的同时并没有解决元素遍历的我效率低下的问题,正是为了解决这个问题,B+树应用而生。B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的,而B树不支持这样的操作或者说效率太低。

补充:B树的范围查找用的是中序遍历,而B+树用的是在链表上遍历。

标签:结点,树结构,查询,关键字,查找,二叉树,红黑树,节点
From: https://blog.csdn.net/weixin_63746255/article/details/136764874

相关文章

  • leedcode-翻转二叉树
    自己写的:classSolution:definvertTree(self,root:Optional[TreeNode])->Optional[TreeNode]:#创建一个新的TreeNode以存储反转后的树newroot=TreeNode()#如果输入的根节点为空,则返回空ifnotroot:......
  • 二叉树的迭代遍历
    二叉树前后序遍历(迭代)#include<bits/stdc++.h>usingnamespacestd;structNode{intdata;Node*left;Node*right;Node(intvalue=0):data(value),left(nullptr),right(nullptr){}};Node*insertEle();voidpreorder(Node*pNode);voidmid......
  • 代码随想录 第21天 | ● 530.二叉搜索树的最小绝对差 ● 501.二叉搜索树中的众数 ●
    leetcode:530.二叉搜索树的最小绝对差-力扣(LeetCode)思路:判断最小绝对差,肯定用中序遍历,双指针一前一后依次判断。classSolution{intresult=Integer.MAX_VALUE;TreeNodepre=null;publicintgetMinimumDifference(TreeNoderoot){if(root==......
  • 【leetcode】二叉树的前序遍历➕中序遍历➕后序遍历
    大家好,我是苏貝,本篇博客带大家刷题,如果你觉得我写的还不错的话,可以给我一个赞......
  • 力扣刷题Days19-637.二叉树的层平均数
    目录1,题目2,代码2.1广度优先遍历2.2深度优先遍历3,学习与总结1,题目给定一个非空二叉树的根节点 root ,以数组的形式返回每一层节点的平均值。2,代码2.1广度优先遍历/***Definitionforabinarytreenode.*functionTreeNode(val,left,right){*......
  • 洛谷题单指南-二叉树-P1030 [NOIP2001 普及组] 求先序排列
    原题链接:https://www.luogu.com.cn/problem/P1030题意解读:已知中序、后序,求先序。解题思路:与洛谷题单指南-二叉树-P1827[USACO3.4]美国血统AmericanHeritage非常类似,不在介绍过程,直接给出代码。100分代码:#include<bits/stdc++.h>usingnamespacestd;stringin,post......
  • 二叉树的垂序遍历
    说在前面......
  • 数据结构之链式二叉树
    当我们初步了解二叉树后我们就可以进一步去深入学习二叉树了1.链式二叉树的遍历这里我们先去定义链式二叉树的结构分为两个指针一左一右他们分别指向左子树和右子树typedefintBTDataType;typedefstructBinaryTreeNode{ BTDataTypedata; structBinartTreeNode......
  • React Antd 的ProTable 如何默认展开树结构
    1、defaultExpandAllRows:true  defaultExpandAllRows设为true就可以了<ProTablerowKey="key"columns={rightBomColumnArr}dataSource={rightBomTableTreeData}......
  • 代码随想录算法训练营第day17|110.平衡二叉树 、 257. 二叉树的所有路径 、404.左叶子
    目录a.110.平衡二叉树b.257.二叉树的所有路径 c.404.左叶子之和a.110.平衡二叉树力扣题目链接(opensnewwindow)给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。示例1......