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

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

相关文章
|
算法
AVL树,Treap树,红黑树的实现(上)
AVL树,Treap树,红黑树的实现
|
2月前
|
存储 C++
【C++】AVL树
AVL树是一种自平衡二叉搜索树:它以苏联科学家Georgy Adelson-Velsky和Evgenii Landis的名字命名。
26 2
|
6月前
|
C++ 容器
【C++】—— 详解AVL树
【C++】—— 详解AVL树
|
6月前
|
存储 测试技术 C++
C++【AVL树】
C++【AVL树】
73 0
二叉搜索树之AVL树
二叉搜索树之AVL树
|
算法 Java Python
实现AVL树
大家好,我是王有志。今天,我们会用Java和Python分别实现第一个平衡二分搜索树--AVL树。
82 0
实现AVL树
|
算法
平衡二叉树(AVL树)
平衡二叉树(AVL树)
81 0
数据结构-各种树(二叉树、二叉查找树、平衡二叉树、红黑树、B树、B+树)
数据结构-各种树(二叉树、二叉查找树、平衡二叉树、红黑树、B树、B+树)
|
测试技术 C++ Perl
C++之AVL树(下)
C++之AVL树(下)
68 0