二叉搜索树、平衡二叉树、红黑树、B树以及B+树的定义

本文主要是介绍二叉搜索树、平衡二叉树、红黑树、B树以及B+树的定义，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

二叉搜索树

二叉搜索树又称二叉排序树和二叉查找树，它要么是空树，要么是具有下列性质的二叉树：

　　1）每个节点都有一个作为查找依据的关键码。所有节点的关键码互不相同；

　　2）若它的左子树不为空，则左子树上所有节点的关键码均小于根节点的关键码；

　　3）若它的右子树不为空，则右子树上所有节点的关键码均大于根节点的关键码；

　　4）它的左、右子树也是二叉查找树。

平衡二叉树

它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，同时，平衡二叉树必定是二叉搜索树。

红黑树

红黑树是一颗特殊的二叉搜索树，除了二叉搜索树的要求外，它还具有以下特性：

　　1）每个节点要么是黑色，要么是红色。

　　2）根节点是黑色。

　　3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！

　　4）如果一个节点是红色的，则它的子节点必须是黑色的。

　　5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

B树

一颗m阶B树的特性：

　　1）根结点至少有两个子女（如果B树只有一个根节点，这个根节点的key的数量可以为[1~m-1]）；

　　2）每个非根节点所包含的关键字个数 j 满足：⌈m/2⌉ - 1 <= j <= m - 1，节点的值按非降序方式存放，即从左到右依次增加；

　　3）除根结点以及叶子节点以外的所有结点的度数正好是关键字总数加1，故内部节点的子树个数 k 满足：⌈m/2⌉ <= k <= m；

　　4）所有的叶子结点都位于同一层。

B+树

m阶B+树是m阶B树的变体，它的定义大致跟B树一致，不过有以下几点不同：

　　1）有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点，其中⌈m/2⌉ <= n <= m；

　　2）所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接；

　　3）所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字；

　　4）通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

参考：https://blog.csdn.net/u014532217/article/details/79118023

这篇关于二叉搜索树、平衡二叉树、红黑树、B树以及B+树的定义的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！