二叉树、平衡二叉树AVL、红黑树、B树、B+树

简介: B树的阶数等于叶节点最大关键字数量+1(因为关键字两边都有指向子节点的指针-分叉)在m阶(m叉)B树中除根结点外,任何节点至少[m/2]个分叉,即至少[m/2]-1个关键字,[ ]代表向上取整。节点内的关键字采用顺序查找或二分查找。因为关键字太少会导致树变高,降低查找效率。另外就是保证同级子树的高度相同-平衡。

网络异常,图片无法展示
|

B树的阶数等于叶节点最大关键字数量+1(因为关键字两边都有指向子节点的指针-分叉)

在m阶(m叉)B树中除根结点外,任何节点至少[m/2]个分叉,即至少[m/2]-1个关键字,

[ ]代表向上取整。

节点内的关键字采用顺序查找或二分查找。

因为关键字太少会导致树变高,降低查找效率。另外就是保证同级子树的高度相同-平衡。

网络异常,图片无法展示
|

B+树的阶数与叶节点最大关键字数量相同,有与分块查找相似的地方;

分支节点中只包含它的叶子结点所有关键字中的最大值。

查找失败:关键字的记录(信息)为空,指向null

文章知识点与官方知识档案匹配,可进一步学习相关知识

目录
打赏
0
0
0
0
434
分享
相关文章
树中枝繁叶茂:探索 B+ 树、B 树、二叉树、红黑树和跳表的世界
树中枝繁叶茂:探索 B+ 树、B 树、二叉树、红黑树和跳表的世界
80 0
|
3月前
|
【C++】AVL树
AVL树是一种自平衡二叉搜索树,由Georgy Adelson-Velsky和Evgenii Landis提出。它通过确保任意节点的两子树高度差不超过1来维持平衡,支持高效插入、删除和查找操作,时间复杂度为O(log n)。AVL树通过四种旋转操作(左旋、右旋、左-右旋、右-左旋)来恢复树的平衡状态,适用于需要频繁进行数据操作的场景。
89 2
|
9月前
AVL 树
AVL 树
73 2
树【二叉树,红黑树,B树,B+树】
树【二叉树,红黑树,B树,B+树】
82 0
C++【AVL树】
C++【AVL树】
92 0
二叉搜索树之AVL树
二叉搜索树之AVL树
C++实现AVL树
C++实现AVL树
77 0
实现AVL树
大家好,我是王有志。今天,我们会用Java和Python分别实现第一个平衡二分搜索树--AVL树。
95 0
实现AVL树
平衡二叉树(AVL树)
平衡二叉树(AVL树)
106 0
数据结构-各种树(二叉树、二叉查找树、平衡二叉树、红黑树、B树、B+树)
数据结构-各种树(二叉树、二叉查找树、平衡二叉树、红黑树、B树、B+树)
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等