树 相关问题和算法

一. 二叉树

1. 性质

①在二叉树第n层上,至多有2^(n-1)个结点。

②深度为k的二叉树,至多有(2^k)-1个结点。

③对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2。有n0=n2+1

2. 二叉树遍历

①先序遍历

(根左右)先访问根结点(打印)→先序遍历左子树→先序遍历右子树

上图先序遍历结果:1 2 4 6 7 8 3 5

②中序遍历

(左根右)中序遍历左子树→访问根结点(打印)→中序遍历右子树

上图中序遍历结果:4 7 6 8 2 1 3 5

③后序遍历

(左右根)后序遍历左子树→后序遍历右子树→访问根结点(打印)

上图后序遍历结果:7 8 6 4 2 5 3 1

④再举个栗子

上图: 先序 - + a * b - c d / e f
            中序 a + b * c - d - e / f
            后序 a b c d - * + e f / -

上图为表达式:a+b*(c-d)-e/f

先序、中序、后序 刚好对应着 前缀表达式、中缀表达式、后缀表达式

3. 完全二叉树、满二叉树

  • 完全二叉树是指,除了最后一层每一层都是满的,而最后一层结点按照从右到左的顺序(不一定是满的),中间没有隔空。
  • 满二叉树……顾名思义。
  • 完全二叉树,度为1的结点只可能是1或者0。

4. 线索二叉树

  • n个结点的二叉链表中含有n+1(2n-(n-1)=n+1)个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为"线索")。
  • 线索二叉树建立方式:

    记ptr指向二叉链表中的一个结点,以下是建立线索的规则:
    (1)如果ptr->lchild为空,则存放指向中序遍历序列中该结点的前驱结点。这个结点称为ptr的中序前驱;
    (2)如果ptr->rchild为空,则存放指向中序遍历序列中该结点的后继结点。这个结点称为ptr的中序后继;
    显然,在决定lchild是指向左孩子还是前驱,rchild是指向右孩子还是后继,需要一个区分标志的。因此,我们在每个结点再增设两个标志域ltag和rtag,注意ltag和rtag只是区分0或1数字的布尔型变量,其占用内存空间要小于像lchild和rchild的指针变量。结点结构如下所示。

    (1)ltag为0时指向该结点的左孩子,为1时指向该结点的前驱;

    (2)rtag为0时指向该结点的右孩子,为1时指向该结点的后继;

二. 二叉查找树

1. 简介

  • 二叉查找树(Binary Search Tree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉排序树。
  • 中序遍历二叉排序树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可。搜索,插入,删除的复杂度等于树高,O(log(n))。二叉树里面没有相同键值的数字。
  • 下面程序代码都是基于这个图来测试的:

2. 二叉查找树的构造(插入结点)

  • 如果树是空树,则将in_node所指结点作为根结点插入,否则:
    若in_node->data等于root的根结点的数据域之值,则返回,否则:
    若in_node->data小于root的根结点的数据域之值,则把in_node所指结点插入到左子树中,否则:
    把in_node所指结点插入到右子树中。
  • 下方的代码示意如何建立一颗二叉树,并在建立后中序遍历输出一个排序好的数字序列。(为了实现“如果树是空树,则将in_node所指结点作为根结点插入”,插入函数第一个参数定义为指针的地址,这样才能在传递进函数后改变指针的指向)

3. 二叉查找树的查找

  • 在二叉排序树root中查找x的过程为:
    若root是空树,则搜索失败,否则:
    若key等于root的根结点的数据域之值,则查找成功;否则:
    若key小于root的根结点的数据域之值,则搜索左子树;否则:
    查找右子树。

4. 二叉查找树删除一个结点

  • 在二叉排序树删去一个结点,分三种情况讨论:
    ①若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。
    ②若*p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点*f的左子树或右子树即可,作此修改也不破坏二叉排序树的特性。
    ③若*p结点的左子树和右子树均不空。在删去*p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:其一是令*p的左子树为*f的左子树,*s为*f左子树的最右下的结点,而*p的右子树为*s的右子树;其二是令*p的直接前驱(或直接后继)替代*p,然后再从二叉排序树中删去它的直接前驱(或直接后继)。
  • 删除结点的代码实现得有点勉强,因为定义的数据结构没有父结点的指针域,自己多写了一个找父结点的函数。所以整体实现的可能不太好看,欢迎大佬指正。
#include <iostream>
using namespace std;

//二叉树的定义
struct BTreeNode {
	int Data;	//值域
	struct BTreeNode* LeftChild=NULL;	//左指针域
	struct BTreeNode* RightChild=NULL;	//右指针域
};
//中序遍历
void Inorder(struct BTreeNode* BT);
void inorder(struct BTreeNode* BT, struct BTreeNode** root);//用于删除结点时候的中序遍历插入
//插入一个结点(建立一颗查找二叉树)
int insert_node(BTreeNode** root, BTreeNode* in_node); 
//找寻一个键值,存在则返回存放位置,不存在则返回空指针
BTreeNode* find_node(BTreeNode* root, int key);
//找到该值的父结点
BTreeNode * fatehr_node(BTreeNode * root, int key, BTreeNode* father);
//删除二叉树的一个键值
int remove_node(BTreeNode** root, int key);


int main() {
	//建立树的过程
	struct BTreeNode *head=NULL;
	struct BTreeNode in_node[8];
	in_node[0].Data = 12;	in_node[1].Data = 5;	in_node[2].Data = 18;
	in_node[3].Data = 2;	in_node[4].Data = 9;	in_node[5].Data = 15;
	in_node[6].Data = 19;	in_node[7].Data = 17;
	for (int i = 0; i < 8; i++) {
		insert_node(&head, &in_node[i]);
	}
	//中序遍历输出
	cout << "Inorder output:";
	Inorder(head);
	cout << endl;
	//查找一个键值
	struct BTreeNode* find = find_node(head, 2);
	if (find == NULL)
		cout << "Nothing find." << endl;
	else
		cout << find->Data << endl;
	//删除一个值
	 remove_node(&head, 5);
	 cout << "Delete output:";
	 Inorder(head);
	 cout << endl;

	getchar();
	return	0;
}

void Inorder(struct BTreeNode* BT) {
	if (BT != NULL)
	{
		Inorder(BT->LeftChild);
		cout << BT->Data << " ";
		Inorder(BT->RightChild);
	}
}
void inorder(struct BTreeNode* BT, struct BTreeNode** root){
	if (BT != NULL)
	{
		inorder(BT->LeftChild,root);
		insert_node(root, BT);
		inorder(BT->RightChild,root);
	}
}

int insert_node(BTreeNode** root, BTreeNode* in_node) {
	//如果树为空,将该结点当作树根
	if (*root == NULL) {
		*root = in_node;
		return 1;
	}
	//如果树非空,开始比较和插入
	if (in_node->Data == (*root)->Data) {
		//搜索二叉树中不应该有相同的值,所以直接返回
		return -1;
	}
	else if (in_node->Data < (*root)->Data) {
		if ((*root)->LeftChild == NULL) {
			(*root)->LeftChild = in_node;
		}
		else {
			insert_node(&(*root)->LeftChild, in_node);
		}
	}
	else if (in_node->Data >(*root)->Data) {
		if ((*root)->RightChild == NULL) {
			(*root)->RightChild = in_node;
		}
		else {
			insert_node(&(*root)->RightChild, in_node);
		}
	}
	return 1;
}

BTreeNode * find_node(BTreeNode * root, int key){
	if (root == NULL) {
		return NULL;
	}
	if (root->Data == key) {
		return root;
	}
	else if (root->Data > key) {
		find_node(root->LeftChild, key);
	}
	else if (root->Data < key) {
		find_node(root->RightChild, key);
	}
}

int remove_node(BTreeNode** root, int key) {
	BTreeNode* find = find_node(*root, key);
	if (find == NULL) {
		cout << "No key find." << endl;
		return -1;
	}
	else {
		BTreeNode* father = fatehr_node(*root, key, NULL);
		//要删除的结点就是根结点,打扰了……先不考虑这种情况
		if (father == NULL) {
			cout << "Can't delete the root." << endl;
			return -1;
		}
		if (find->LeftChild == NULL && find->RightChild == NULL) {
			//结点为叶子结点,直接删除就好
			if (father->LeftChild->Data == key)
				father->LeftChild = NULL;
			if(father->RightChild->Data == key)
				father->RightChild = NULL;
		}
		else if (find->LeftChild == NULL) {
			//结点存在右树,把右树给父结点右孩子就好
			if (father->RightChild == NULL) {
				if (father->LeftChild->Data == key)
					father->LeftChild = NULL;
				if (father->RightChild->Data == key)
					father->RightChild = NULL;
				father->RightChild = find->RightChild;
			}
			else {
				if (father->LeftChild->Data == key)
					father->LeftChild = NULL;
				if (father->RightChild->Data == key)
					father->RightChild = NULL;
				inorder(find->RightChild,root);
			}
		}
		else if (find->RightChild == NULL) {
			//结点存在左树,把左树给父结点左孩子就好
			if (father->RightChild == NULL) {
				if (father->LeftChild->Data == key)
					father->LeftChild = NULL;
				if (father->RightChild->Data == key)
					father->RightChild = NULL;
				father->LeftChild = find->LeftChild;
			}
			else {
				if (father->LeftChild->Data == key)
					father->LeftChild = NULL;
				if (father->RightChild->Data == key)
					father->RightChild = NULL;
				inorder(find->LeftChild, root);
			}
		}
		else {
			//结点有左树也有右树
			if (father->LeftChild->Data == key)
				father->LeftChild = NULL;
			if (father->RightChild->Data == key)
				father->RightChild = NULL;
			inorder(find->RightChild, root);
			inorder(find->LeftChild, root);
		}
	}
	return 1;
}

BTreeNode * fatehr_node(BTreeNode * root, int key,BTreeNode* father) {
	if (root->Data == key) {
		return father;
	}
	else if (root->Data > key) {
		fatehr_node(root->LeftChild, key, root);
	}
	else if (root->Data < key) {
		fatehr_node(root->RightChild, key, root);
	}
}

5. 平衡二叉查找树

  • 平衡二叉搜索树(Self-balancing binary search tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
  • 平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列,可以参考Fibonacci(斐波那契)数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。

三. 红黑树

1. 简介

  • 红黑树,本质上来说就是一棵特殊的二叉查找树。它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡,从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
  • 五个性质:
    1)每个结点要么是红的,要么是黑的。  
    2)根结点是黑的。  
    3)每个叶结点(叶结点即指树尾端NIL指针或NULL结点)是黑的。[注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
    4)如果一个结点是红的,那么它的俩个儿子都是黑的。  
    5)对于任一结点而言,其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。 
  • 正是红黑树的这5条性质,使得一棵n个结点是红黑树始终保持了logn的高度,从而也就解释了上面我们所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论的原因。

2. 树的旋转

  • 当我们在对红黑树进行插入和删除等操作时,对树做了修改,那么可能会违背红黑树的性质。为了继续保持红黑树的性质,我们可以通过对结点进行重新着色,以及对树进行相关的旋转操作,即修改树中某些结点的颜色及指针结构,来达到对红黑树进行插入或删除结点等操作后,继续保持它的性质或平衡。
  • 对于树的旋转,能保持不变的只有原树的搜索性质,而原树的红黑性质则不能保持,在红黑树的数据插入和删除后可利用旋转和颜色重涂来恢复树的红黑性质。
  • 树的旋转,分为左旋和右旋。
  • 左旋中的“左”,意味着“被旋转的节点将变成一个左节点”。右旋中的“右”,意味着“被旋转的节点将变成一个右节点”。仔细观察下面"左旋"和"右旋"的示意图。我们能清晰的发现,它们是对称的。无论是左旋还是右旋,被旋转的树,在旋转前是二叉查找树,并且旋转之后仍然是一颗二叉查找树。

 

  • 左旋:


    当在某个结点pivot上,做左旋操作时,我们假设它的右孩子y不是NIL[T],pivot可以为任何不是NIL[T]的左孩子结点。
    左旋以pivot到y之间的链为“支轴”进行,它使y成为该孩子树新的根,而y的左孩子b则成为pivot的右孩子。
    左旋操作的参考代码如下所示:
    /* 
     * 对红黑树的节点(x)进行左旋转
     *
     * 左旋示意图(对节点x进行左旋):
     *      px                              px
     *     /                               /
     *    x                               y                
     *   /  \      --(左旋)-->           / \                #
     *  lx   y                          x  ry     
     *      / \                        / \
     *    ly   ry                     lx  ly  
     *
     *
     */
    template <class T>
    void RBTree<T>::leftRotate(RBTNode<T>* &root, RBTNode<T>* x)
    {
        // 设置x的右孩子为y
        RBTNode<T> *y = x->right;
    
        // 将 “y的左孩子” 设为 “x的右孩子”;
        // 如果y的左孩子非空,将 “x” 设为 “y的左孩子的父亲”
        x->right = y->left;
        if (y->left != NULL)
            y->left->parent = x;
    
        // 将 “x的父亲” 设为 “y的父亲”
        y->parent = x->parent;
    
        if (x->parent == NULL)
        {
            root = y;            // 如果 “x的父亲” 是空节点,则将y设为根节点
        }
        else
        {
            if (x->parent->left == x)
                x->parent->left = y;    // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
            else
                x->parent->right = y;    // 如果 x是它父节点的左孩子,则将y设为“x的父节点的左孩子”
        }
        
        // 将 “x” 设为 “y的左孩子”
        y->left = x;
        // 将 “x的父节点” 设为 “y”
        x->parent = y;
    }
  • 右旋:


     
    /* 
     * 对红黑树的节点(y)进行右旋转
     *
     * 右旋示意图(对节点y进行左旋):
     *            py                               py
     *           /                                /
     *          y                                x                  
     *         / \      --(右旋)-->             /  \                     #
     *        x   ry                           lx   y  
     *       / \                                   / \                   #
     *      lx  rx                                rx  ry
     * 
     */
    template <class T>
    void RBTree<T>::rightRotate(RBTNode<T>* &root, RBTNode<T>* y)
    {
        // 设置x是当前节点的左孩子。
        RBTNode<T> *x = y->left;
    
        // 将 “x的右孩子” 设为 “y的左孩子”;
        // 如果"x的右孩子"不为空的话,将 “y” 设为 “x的右孩子的父亲”
        y->left = x->right;
        if (x->right != NULL)
            x->right->parent = y;
    
        // 将 “y的父亲” 设为 “x的父亲”
        x->parent = y->parent;
    
        if (y->parent == NULL) 
        {
            root = x;            // 如果 “y的父亲” 是空节点,则将x设为根节点
        }
        else
        {
            if (y == y->parent->right)
                y->parent->right = x;    // 如果 y是它父节点的右孩子,则将x设为“y的父节点的右孩子”
            else
                y->parent->left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”
        }
    
        // 将 “y” 设为 “x的右孩子”
        x->right = y;
    
        // 将 “y的父节点” 设为 “x”
        y->parent = x;
    }

     

3. 插入结点

  • 整体步骤:①将红黑树当作一颗二叉查找树,将节点插入;②将节点着色为红色;③通过旋转和重新着色等方法来修正该树,使之重新成为一颗红黑树。
  • 第③步的的重新着色:
    如果插入的是根结点,因为原树是空树,此情况只会违反性质2,所以直接把此结点涂为黑色。
    如果插入的结点的父结点是黑色,由于此不会违反性质2和性质4,红黑树没有被破坏,所以此时也是什么也不做。
  • 除了上面一点,如果遇到以下三种情况需要进行修复:
                        现象说明 处理策略
    Case 1 当前节点的父节点是红色,且当前节点的祖父节点的另一个子节点(叔叔节点)也是红色。 (01) 将“父节点”设为黑色。
    (02) 将“叔叔节点”设为黑色。
    (03) 将“祖父节点”设为“红色”。
    (04) 将“祖父节点”设为“当前节点”(红色节点);即,之后继续对“当前节点”进行操作。
    Case 2 当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的右孩子 (01) 将“父节点”作为“新的当前节点”。
    (02) 以“新的当前节点”为支点进行左旋。
    Case 3 当前节点的父节点是红色,叔叔节点是黑色,且当前节点是其父节点的左孩子 (01) 将“父节点”设为“黑色”。
    (02) 将“祖父节点”设为“红色”。
    (03) 以“祖父节点”为支点进行右旋。

4. 删除结点:

  • 整体步骤:①将红黑树当作一颗二叉查找树,将该节点从二叉查找树中删除(详细处理过程看上文:二、二叉查找树);②通过"旋转和重新着色"等一系列来修正该树,使之重新成为一棵红黑树。
  • 我们从被删结点后来顶替它的那个结点开始调整,并认为它有额外的一重黑色。这里额外一重黑色是什么意思呢,我们不是把红黑树的结点加上除红与黑的另一种颜色,这里只是一种假设,我们认为我们当前指向它,因此空有额外一种黑色,可以认为它的黑色是从它的父结点被删除后继承给它的,它现在可以容纳两种颜色,如果它原来是红色,那么现在是红+黑,如果原来是黑色,那么它现在的颜色是黑+黑。有了这重额外的黑色,原红黑树性质5就能保持不变。现在只要恢复其它性质就可以了,做法还是尽量向根移动和穷举所有可能性。
  • 如果是以下情况,修正比较简单:
    ①当前结点是红+黑色
    解法,直接把当前结点染成黑色,结束此时红黑树性质全部恢复。
    ②当前结点是黑+黑且是根结点
    解法:什么都不做,结束。
  • 但如果是以下情况呢?:
    删除修复情况1:当前结点是黑+黑且兄弟结点为红色(此时父结点和兄弟结点的子结点分为黑)
    删除修复情况2:当前结点是黑加黑且兄弟是黑色且兄弟结点的两个子结点全为黑色
    删除修复情况3:当前结点颜色是黑+黑,兄弟结点是黑色,兄弟的左子是红色,右子是黑色
    删除修复情况4:当前结点颜色是黑-黑色,它的兄弟结点是黑色,但是兄弟结点的右子是红色,兄弟结点左子的颜色任意
                      现象说明 处理策略
    Case 1 x是"黑+黑"节点,x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。 (01) 将x的兄弟节点设为“黑色”。
    (02) 将x的父节点设为“红色”。
    (03) 对x的父节点进行左旋。
    (04) 左旋后,重新设置x的兄弟节点。
    Case 2 x是“黑+黑”节点,x的兄弟节点是黑色,x的兄弟节点的两个孩子都是黑色。 (01) 将x的兄弟节点设为“红色”。
    (02) 设置“x的父节点”为“新的x节点”。
    Case 3 x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的左孩子是红色,右孩子是黑色的。 (01) 将x兄弟节点的左孩子设为“黑色”。
    (02) 将x兄弟节点设为“红色”。
    (03) 对x的兄弟节点进行右旋。
    (04) 右旋后,重新设置x的兄弟节点。
    Case 4 x是“黑+黑”节点,x的兄弟节点是黑色;x的兄弟节点的右孩子是红色的,x的兄弟节点的左孩子任意颜色。 (01) 将x父节点颜色 赋值给 x的兄弟节点。
    (02) 将x父节点设为“黑色”。
    (03) 将x兄弟节点的右子节设为“黑色”。
    (04) 对x的父节点进行左旋。
    (05) 设置“x”为“根节点”。

5、参考资料

教你透彻了解红黑树

红黑树(一)之 原理和算法详细介绍

 

四. B树

1. 简介

  • 大规模数据存储中,实现索引查询这样一个实际背景下,树节点存储的元素数量是有限的(如果元素数量非常多的话,查找就退化成节点内部的线性查找了),这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下(为什么会出现这种情况,待会在外部存储器-磁盘中有所解释),那么如何减少树的深度(当然是不能减少查询的数据量),一个基本的想法就是:采用多叉树结构(由于树节点元素数量是有限的,自然该节点的子树数量也就是有限的)。
  • B-树,即为B树。因为B树的原英文名称为B-tree,而国内很多人喜欢把B-tree译作B-树,其实,这是个非常不好的直译,很容易让人产生误解。如人们可能会以为B-树是一种树,而B树又是另一种树。而事实上是,B-tree就是指的B树。
  • B树与红黑树最大的不同在于,B树的结点可以有许多子女,从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样,一棵含n个结点的B树的高度也为O(lgn),但可能比一棵红黑树的高度小许多,应为它的分支因子比较大。所以,B树可以在O(logn)时间内,实现各种如插入(insert),删除(delete)等动态集合操作。
  •  

2. B树

  • 如下图所示,即是一棵B树,一棵关键字为英语中辅音字母的B树,现在要从树种查找字母R(包含n[x]个关键字的内结点x,x有n[x]+1]个子女(也就是说,一个内结点x若含有n[x]个关键字,那么x将含有n[x]+1个子女)。所有的叶结点都处于相同的深度,带阴影的结点为查找字母R时要检查的结点):

  • 一棵m阶的B 树的特性如下:
    ①树中每个结点最多含有m个孩子(m>=2);
    ②除根结点和叶子结点外,其它每个结点至少有[ceil(m / 2)]个孩子(其中ceil(x)是一个取上限的函数);
    ③若根结点不是叶子结点,则至少有2个孩子(特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点);
    ④所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点,实际上这些结点不存在,指向这些结点的指针都为null);
    (读者反馈@冷岳:这里有错,叶子节点只是没有孩子和指向孩子的指针,这些节点也存在,也有元素。@研究者July:其实,关键是把什么当做叶子结点,因为如红黑树中,每一个NULL指针即当做叶子结点,只是没画出来而已)。
    ⑤每个非终端结点中包含有n个关键字信息: (n,P0,K1,P1,K2,P2,......,Kn,Pn)。其中:
        a)   Ki (i=1...n)为关键字,且关键字按顺序升序排序K(i-1)< Ki
        b)   Pi为指向子树根的接点,且指针P(i-1)指向子树种所有结点的关键字均小于Ki,但都大于K(i-1)。
        c)   关键字的个数n必须满足: [ceil(m / 2)-1]<= n <= m-1。

 

3. B+树

  • B+树是应文件系统所需而产生的一种B树的变形树。
  • 一棵m阶的B+树和m阶的B树的异同点在于:
    ①有n棵子树的结点中含有n-1 个关键字; (此处颇有争议,B+树到底是与B 树n棵子树有n-1个关键字 保持一致,还是不一致:B树n棵子树的结点中含有n个关键字,待后续查证。而下面B+树的图尚未最终确定是否有问题,请读者注意)
    ②所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)
    ③所有的非终端结点可以看成是索引部分,结点中仅含有其子树根结点中最大(或最小)关键字。 (而B 树的非终节点也包含需要查找的有效信息)

 

4. B*树

  • B*-tree是B+-tree的变体,在B+树的基础上(所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针),B*树中非根和非叶子结点再增加指向兄弟的指针;B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。

 

5. 参考资料

从B树、B+树、B*树谈到R 树

B树和B+树的总结

 

五.  其他考试常见内容

1. 先、中、后序互求

①已知前、中,求后序

前序用来确定根结点,第一个是最开始的根结点;

中序用来确定左右子树,在根结点左边为左子树,在右边为右子树;

根据这递推画出树,再由树写出后序

例:由下面的已知条件可以推出上图

前:GDAFEMHZ

中:ADEFGHMZ

②已知中、后,求前序

后序用来确定根结点,最后一个是最开始的根结点;

中序用来确定左右子树,在根结点左边为左子树,在右边为右子树;

根据这递推画出树,再由树写出前序

例:由下面的已知条件可以推出上图

后:AEFDHZMG

中:ADEFGHMZ

2. B树相关的说法:

  • B-树和B+树都可用于文件的索引结构。
  • B-树和B+树都能有效地支持随机检索。

3. 哈夫曼树带权路径长度

  • 哈夫曼树有n个叶子结点,该树共有多少结点?
    哈夫曼树只有度为0和度为2的结点。
    根据二叉树的性质,n0 = n2 + 1,因此该树中度为2的结点数量为n-1
    于是一共有2n-1个结点

4. 树、森林和二叉树的转换

 

原文链接:加载失败,请重新获取