二叉树、平衡二叉树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

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

相关文章
|
7月前
|
存储 算法 数据库
树中枝繁叶茂:探索 B+ 树、B 树、二叉树、红黑树和跳表的世界
树中枝繁叶茂:探索 B+ 树、B 树、二叉树、红黑树和跳表的世界
71 0
|
算法
AVL树,Treap树,红黑树的实现(上)
AVL树,Treap树,红黑树的实现
|
6月前
|
C++
【c++】avl树
【c++】avl树
44 0
|
7月前
AVL 树
AVL 树
57 2
|
7月前
|
C++ 容器
【C++】—— 详解AVL树
【C++】—— 详解AVL树
|
7月前
|
机器学习/深度学习 存储 算法
树【二叉树,红黑树,B树,B+树】
树【二叉树,红黑树,B树,B+树】
75 0
二叉搜索树之AVL树
二叉搜索树之AVL树
|
C++
C++实现AVL树
C++实现AVL树
67 0
|
算法
平衡二叉树(AVL树)
平衡二叉树(AVL树)
86 0