BST的特点: 据结构 中序遍历BST可得到一个关键字的有序 序列。 在BST上插入新结点时,不必移动其他 结点,仅需改动某结点的指针(因新结点 总是BST上的一个新叶结点) BST既具有类似折半查找的特性(与BST 的平衡度有关)又采用了链表存储结构 (折半查找不能为链表存储结构),因此, 对于经常要进行查找、插入和删除记录的 有序表,采用BST尤其合适。 平衡二叉树(AVL树) 数据结构 定义:它或是一棵空树,或者是左子树 和右子树的深度之差的绝对值不超过1; 且左子树和右子树都是平衡二叉树。 平衡因子BF:是该结点的左子树的深度 减去它的右子树的深度。 查 平衡二叉树上的所有结点的平衡因子只 找 可能是1,0,1。 在构成二叉排序树的过程中进行“平衡 化”处理,成为二叉平衡树11 数 据 结 构 之 查 找 21 ¾ BST的特点： ¾ 中序遍历BST可得到一个关键字的有序 序列。 ¾ 在BST上插入新结点时，不必移动其他 结点，仅需改动某结点的指针（因新结点 总是BST上的一个新叶结点）。 ¾ BST既具有类似折半查找的特性（与BST 的平衡度有关）又采用了链表存储结构 （折半查找不能为链表存储结构），因此， 对于经常要进行查找、插入和删除记录的 有序表，采用BST尤其合适。 数 据 结 构 之 查 找 22 ¾ 平衡二叉树(AVL树)： ¾ 定义：它或是一棵空树，或者是左子树 和右子树的深度之差的绝对值不超过1； 且左子树和右子树都是平衡二叉树。 ¾ 平衡因子BF：是该结点的左子树的深度 减去它的右子树的深度。 ¾ 平衡二叉树上的所有结点的平衡因子只 可能是-1，0，1。 ¾ 在构成二叉排序树的过程中进行“平衡 化”处理，成为二叉平衡树