CWYAlpha

Just another WordPress.com site

Thought this was cool: 数据结构重读 – 二叉排序树(BST)

leave a comment »


1、前面讨论了静态查找表,它们的特点是,数据是一次性就给好了。

2、而对于动态查找表,数据可以是在查找过程中动态添加、生成的。其实这概念不太严谨。

3、二叉排序树(BST):左子树上所有结点的值均小于根结点的值;右子树上所有结点的值均大于根结点上的值。

4、二叉排序树的查找过程:
(1)若树为空,直接返回/跳出。
(2)树非空,则
(a)若key==root.data,return true。
(b)若key<root.data, root = root.left。
(c)若key>root.data, root = root.right。
(3)若最后还未找到,返回false。

这个查找可以是递归,也可以不递归

5、当构造BST时,要注意:只有关键字不在BST树中时,才能插入。因此,插入一个元素前要先查找(Search)。

6、中序遍历二叉排序树(BST)可以得到一个关键字有序的序列(升序)。

7、BST树删除结点(同样使用之后的AVL树),假设要删除的结点为p,它的双亲结点为f,并假设p为f的左孩子:
(1)若p为叶子结点,直接删除,并更改它双亲的为null即可。
(2)若p只有左子树或者只有右子树,直接让左、右子树成为f的左子树即可。
(3)若p的左子树和右子树均非空。让p的直接前驱(指中序遍历的前一个元素)替代p,然后删除直接前驱。

8、二叉排序树上查找其关键字个数等于路径长度加1(或者所在层次数)。

9、二叉查找树查找平均O(logn),最坏O(n)。

10、上面的最坏,就是查找树由于插入顺序而退化成了一条支线(斜向左下或右下)。
from 四号程序员四号程序员: http://www.coder4.com/archives/3535

Written by cwyalpha

七月 6, 2012 在 10:38 上午

发表在 Uncategorized

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: