2015年国家电网考试备考计算机之数据结构与算法(7)

　　5.树 (Tree)

　　数据结构中为了存储和查找的方便，用各种树结构来存储文件。树结构包括：二叉查找树(二叉排序树)、平衡二叉树(AVL树)、红黑树、B-树、B+树、字典树(trie树)、后缀树、广义后缀树。各种树的表示方法、特点及各自的用途如下：

　　1、二叉查找树(二叉排序树)

　　二叉查找树是一种动态查找表(图a)，具有这些性质：

　　(1)若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值;

　　(2)若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值;

　　(3)其他的左右子树也分别为二叉查找树;

　　(4)二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。

　　2、平衡二叉树(AVL树)

　　含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树(图b)，具有以下性质：

　　(1)要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1;

　　(2)其左右子树也都是平衡二叉树;

　　(3)二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。

　　3、红黑树

　　红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：

　　(1)根节点只能是黑色;

　　(2)红黑树中所有的叶子节点后面再接上左右两个空节点，这样可以保持算法的一致性，而且所有的空节点都是黑色;

　　(3)其他的节点要么是红色，要么是黑色，红色节点的父节点和左右孩子节点都是黑色，及黑红相间;

　　(4)在任何一棵子树中，从根节点向下走到空节点的路径上所经过的黑节点的数目相同，从而保证了是一个平衡二叉树。

　　4、B-树