计算机备考资料：数据结构基本概念(十)

《计算机备考资料：数据结构基本概念(十)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构：基本概念(十)　　Ø二叉排序树的定义　　二叉排序树或者是一棵空的二叉树，或者是具有下列性质的二叉树：　　⑴若它的左子树不空，则左子树上所有结点的值均小于根结点的值;　　⑵若它的右子树不空，则右子树上所有结点的值均大于根结点的值;　　⑶它的左右子树也都是二叉排序树。　　Ø二叉排序树的查找性能　　如果二叉排序树是平衡的，则其查找效率为O(log2n)。如果二叉排序树为一棵斜树，则其查找效率为O(n)。因此，二叉排序树的查找性能在O(log2n)和O(n)之间。　　Ø平衡二叉树的定义　　平衡二叉树或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树：　　⑴根结点的左子树

2、和右子树的深度最多相差1。　　⑵根结点的左子树和右子树也都是平衡二叉树。　　Ø构造平衡二叉树的基本思想　　在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。　　Ø平衡调整的四种类型　　设结点A为最小不平衡子树的根结点，对该子树进行平衡化调整有以下四种情况：　　⑴LL型：结点x插在根结点A的左孩子的左子树上。　　⑵RR型：结点x插在根结点A的右孩子的右子树上。　　⑶LR型：结点x插在根结点A的左孩子的右子树上。

3、　　⑷RL型：结点x插在根结点A的右孩子的左子树上。　　Ø散列查找的基本思想　　散列查找也称为哈希查找、Hash查找，其基本思想是：在记录的存储位置和它的关键码之间建立一个确定的对应关系H，使得每个关键码key和唯一的一个存储位置H(key)相对应。在查找时，根据这个确定的对应关系找到给定值k的映射H(k)，若查找集合中存在这个记录，则必定在H(k)的位置上。　　Ø散列查找的基本概念　　采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表，将关键码映射为散列表中适当存储位置的函数称为散列函数，所得的存储位置址称为散列地址。　　对于两个不同的关键码k1≠k2

4、，有H(k1)=H(k2)，即两个不同的记录需要存放在同一个存储位置，这种现象称为冲突，k1和k2相对于H称做同义词。　　Ø散列查找的关键问题　　采用散列技术需要考虑的两个关键问题是：　　⑴散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。　　⑵冲突的处理。如何采取合适的处理冲突方法来解决冲突。文后寄语：book118是一个专注于电子文档的在线分享平台，用户在此平台上不但可以自由交换文档，还可以分享最新的行业资讯。book118制定了严格的文档审核策略，以保证文档来源的合法性，对有可能引起知识产权纠纷的文档，网站不予收录。同时，道客巴巴采用了行业领先的文档加密及保

5、护技术，最大程度上保证用户上传的文档的版权不被非法侵犯。注册1、会员信息是您在book118网站的身份标识，注册后，您可以浏览文档、在线阅读或下载，建立并管理自己的文档信息库;2、打开网站的首页，点击页面上方的信息条文字"【免费注册】"，在用户注册页面，输入用户名、密码、电子邮件、验证码，阅读"服务协议"，并选中"同意"复选框，最后点击"注册"按钮;3、也可以在"登录"页面，点击"新用户注册"按钮，进入用户注册页面;