2019考研计算机数据结构复习重点：动态查找表
《数据结构(C语言版)》复习重点在二、三、六、七、九、十章，考试内容两大类：概念，算法，自从计算机专业课统考以后，专业课考试题型分为2类，一类选择题，一类综合应用题。接下来是新东方在线整理的2019考研计算机数据结构复习重点动态查找表。4. 动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素。
1)
二叉排序树：或者是一棵空树;或者是具有下列性质的二叉树：1、若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值;2、若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值;3、它的左、右子树也分别为二叉排序树。
2)
平衡二叉树(AVL树)：它或者是一棵空树;或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是
-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
下面即四种情况分别为：左左、右右、左右、右左，每种情况又有两个图①、②，①是该情况的最简单的图形，②是该情况的一般的图形。
设x为最小不平衡子树的根结点，y为刚插入的点
左左：即在x的左孩子a的左孩子c上插入一个结点y(该结点也可以是c,如图①)，即y可以是c，也可以是c的左孩子(如图②)，也可以是c的右孩子(不在画出)。
图①就不用说了，结点x和结点a变换，则树平衡了;那么图②就是树中的一般情况了a结点有右孩子d，那要进行x和a变换，那么a的右孩子放哪啊?很简单，如图放在x的左孩子上;分析：x>d,d>a,所以d可作为x的左孩子，且可作为a的右孩子中的孩子。下边这样的类似情况不再分析，自己分析分析。
实现：找到根结点x，与它的左孩子a进行交换即可使二叉树树再次平衡;
右右：即在x的右孩子a的右孩子c上插入一个结点y(该结点也可以是c,如图①)，即y可以是c，也可以是c的右孩子(如图②)，也可以是c的左孩子(不在画出)。
实现：找到根结点x，与它的右孩子a进行交换即可使二叉树树再次平衡;
左右：即在x的左孩子a的右孩子c上插入一个结点y(该结点也可以是c,如图①)，即y可以是c，也可以是c的右孩子(如图②)，也可以是c的左孩子(不在画出)。
这个左右和下边的右左，稍微复杂了点，需要进行两次交换，才能达到平衡，注意这时y是c的右孩子，最终y作为x的左孩子;若y是c的左孩子，最终y作为a的右孩子，画图分析一下~~下边类似，不再敖述。
实现：找到根结点x，让x的左孩子a与x的左孩子a的右孩子c进行交换，然后再让x与x此时的左孩子c进行交换，最终达到平衡;
右左：即在x的右孩子a的左孩子c上插入一个结点y(该结点也可以是c,如图①)，即y可以是c，也可以是c的右孩子(如图②)，也可以是c的左孩子(不在画出)。
实现：找到根结点x，让x的右孩子a与x的右孩子a的左孩子c进行交换，然后再让x与x此时的右孩子c进行交换，最终达到平衡;
上边的四种情况包含了所有插入时导致不平衡的情况，上面给出的仅仅是一棵大树中的最小不平衡子树，一定要想清楚，别迷了!另外一定要注意这个交换操作，比如a与b交换(a在上，b在下)，b一定要占据a的位置!什么意思?就是b要放在(覆盖)储存a的那块内存上，再通俗点说，若a是x的左孩子，则交换后b要做x的左孩子;这就是所谓的b占据a的位置!
页:
[1]