考试网 >> IT认证 >> 水平 >> 软件指导 >> 程序员数据结构笔记(二)

发布时间：2006-06-28 04:46     点击：

　　　总的时间复杂度：(m+n)/2

　　●二叉排序树　1）定义：左子树键值大于根节点键值；右子树键值小于根的键值，其左右子树均为二叉排序树。　

　　　　　　　　　2）特点：中序遍历有序->（删除节点用到此性质）

　　　　　　　　　3）二叉排序树的查找：如果根大于要查找的树，则前左子树前进，如果根小于要查找的树，则向右子树前进。

　　　　　　　　　4）结点的插入->二叉排序树的构造方法

　　　　　　　　　5）结点删除（难点）　 1、右子树放在左子树的最右边

　　　　　　　　　　　　　　　　　　　　2、左子树放在右子树的最左边

　●avl树（二叉平衡树）：左右子树高度只能差１层，即｜h｜<=1其子树也一样。

　　●B树：n阶B树满足以下条件　1）每个结点（除根外）包含有N～2N个关链字。　　　　　　　　　　　　　　　　2）所有叶子节点都在同一层。

　　　　　　　　　　　　　　　　3）B树的所有子树也是一棵B树。

　　　特点：降低层次数，减少比较次数。

排序

一、知识点

　　1、排序的定义

　　　　　　　　　/内排序：只在内存中进行

　　2、排序的分类

　　　　　　　　　\外排序：与内外存进行排序　

　　　内排序：　　　/直接插入排序

　　　　1）插入排序

　　　　　　　　　　\shell排序

　　　　　　　　　　/冒泡排序

　　　　2）交换排序　

　　　　　　　　　　\快速排序

　　　　　　　　　　　/简单选择排序

　　　　3）选择排序 堆

　　　　　　　　　　　\ 锦标赛排序

　　　　4）归并排序（二路）

　　　　5）基数排序（多关链字排序）

　　3、时间复杂度（上午题目常考，不会求也得记住啊兄弟姐妹们！）

　　　　　　　　　* * * * * * 15 * * * 15 * * *

　　　　/稳定　　 * * * * * * * * 15 15 * * * *(前后不变)　

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。