《算法导论》 练习13.1-2

2377阅读 0评论2012-05-05 duanlin
分类:Delphi

对图13-1中的红黑树,画出调用TREE-INSERT插入关键字36后的结果。如果插入的结点被标为红色,所得的树是否还是一棵红黑树?如果该节点被标为黑色呢?
 
调用TREE-INSERT插入关键字36后,在结点35生成右孩子结点36。如该节点被标为红色,由于35也为红色,不满足红色结点的左右孩子均为黑色这个红黑树性质。因此不构成红黑树。
若被标为黑色,则在根节点开始的路径:26-41-30-28 和 26-41-30-38-35-36 具有不同数目的黑结点,这样就不满足每个节点到其子孙结点的所有路径上包含相同数目的黑结点这个性质,因此不构成红黑树。
上一篇:《算法导论》 练习12.2-5
下一篇:我的纸版图书目录