数据结构

B树 定义及性质 对于一个m阶的B树 每个结点最多有m-1个关键字和m个孩子指针 根结点最小可以有1个关键字 非根结点至少有$\lceil m/2\rceil-1$个关键字 对于一个有n个关键字的结点 每个结点的n个关键字以非降序排列 每个结点的n+1个孩子指针 对于一个指针,其左关键字为$key_{i}$,其右关键字为$key_{i+1}$,如果它不为null,那么该指针指向的结点的所有key都大于关键字$key_{i}$,且小于关键字$key_{i+1}$ 每个叶子结点具有相同的深度. ...

红黑树 定义及性质 每个结点或是黑色,或是红色 根结点是黑色 每个叶子结点是黑色(这里说的叶子结点是null结点) 如果一个结点是红色的,那么它的两个孩子结点必须是黑色 从任意一个结点出发,到该结点的子孙叶结点的路径上,必须经过相同数量的黑色结点

平衡二叉树 定义及性质 ​ 平衡二叉树是其左右子树的高度差小于2的二叉搜索树 ...

二叉搜索树 定义及性质: 若它的左子树不为空,则它的左子树的所有结点都小于根结点 若它的右子树不为空,则它的右子树的所有结点都大于根节点 任一子树也满足二叉搜索树 ...