证明每一棵AVL树都可以被涂成红黑树。所有的红黑树都是AVL树吗?-笔试面试资料

这是qklbishe.com第16431 篇笔试面试资料
提供答案分析,通过本文《证明每一棵AVL树都可以被涂成红黑树。所有的红黑树都是AVL树吗?-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:
证明每一棵AVL树都可以被涂成红黑树。所有的红黑树都是AVL树吗?

证明每一棵AVL树都可以被涂成红黑树。所有的红黑树都是AVL树吗? 问问很棒棒
先给出证明思路和证明,再给出染色算法。
1. 证明思路:
        枚举高为1到4的AVL树,可以发现一棵树可能存在不同的染色方法;AVL树有对子树树高的限制,利用这一点再观察高为1到4的AVL树的染色结果,可以猜测出为高为h的AVL树必有黑高为(h+1)/2的染色方法;再考虑利用数学归纳法证明。证明如下图。
证明每一棵AVL树都可以被涂成红黑树。所有的红黑树都是AVL树吗?
2. 染色算法:想到了两个算法,第一个采用上图描述的“由h确定的染色”,第二个是树上dp。
        2.1 “由h确定的染色”,思路:从上往下,保证当前节点染为黑色,且当前子树黑高为(h+1)/2。代码如下:
public class ColorAvl2RbByHeight {      public void colorAvl2Rb(TreeNode t) {         topDown(t);     }      private void topDown(TreeNode t) {         if (t == null) {             return;         }         t.isRed = false;         if (t.left == null || t.right == null) {             if (t.left != null) {                 t.left.isRed = true;             }             if (t.right != null) {                 t.right.isRed = true;             }             return;         }         if (t.height % 2 == 1 || t.left.height < t.right.height) {             topDown(t.left);         } else {             t.left.isRed = true;             topDown(t.left.left);             topDown(t.left.right);         }         if (t.height % 2 == 1 || t.right.height < t.left.height) {             topDown(t.right);         } else {             t.right.isRed = true;             topDown(t.right.left);             topDown(t.right.right);         }     }          private static class TreeNode {         int height = 1;         int key;         boolean isRed = true;                  TreeNode left;         TreeNode right;     } } 

        2.2 树上dp,思路:对一棵AVL树可能有不同的染色方法,对应会产生不同黑高的红黑树;但要保证左右子树的黑高一样,所以选择子树的染色方法时需要考虑兄弟子树的可能染色方法,然后二者取交集;所以想到树上dp,先从下往上,汇总子树的可能染色方法,产生父节点的可能染色方法,然后从上往下,向子树传递需要保证的黑高,由子树挑选可行的染色方法。具体地,为每个节点维护两个区间,分别是当前节点若为红色时当前子树可能的黑高区间,和当前节点若为黑色时当前子树可能的黑高区间。代码如下:
public class ColorAvl2RbByTreeDP {          public void colorAvl2Rb(TreeNode t) {         bottomUp(t);         topDown(t, t.minBlackBh, false);     }          private void topDown(TreeNode t, int targetBh, boolean canBeRed) {         if (t == null) {             return;         }         if (canBeRed && targetBh >= t.minRedBh && targetBh <= t.maxRedBh) {             t.isRed = true;             topDown(t.left, targetBh, false);             topDown(t.right, targetBh, false);         } else {             t.isRed = false;             topDown(t.left, targetBh - 1, true);             topDown(t.right, targetBh - 1, true);         }     }      private void bottomUp(TreeNode t) {         if (t == null) {             return;         }                  bottomUp(t.left);         bottomUp(t.right);                  if (t.left == null && t.right == null) {             t.minRedBh = 0;             t.maxRedBh = 0;             t.minBlackBh = 1;             t.maxBlackBh = 1;         } else if (t.left == null || t.right == null) {             t.minRedBh = 1;             t.maxRedBh = 0;             t.minBlackBh = 1;             t.maxBlackBh = 1;         } else {             t.minRedBh = Math.max(t.left.minBlackBh, t.right.minBlackBh);             t.maxRedBh = Math.min(t.left.maxBlackBh, t.right.maxBlackBh);             t.minBlackBh = 1 + Math.max(                     t.left.minRedBh <= t.left.maxRedBh ? t.left.minRedBh : t.left.minBlackBh,                     t.right.minRedBh <= t.right.maxRedBh ? t.right.minRedBh : t.right.minBlackBh);             t.maxBlackBh = 1 + Math.min(t.left.maxBlackBh, t.right.maxBlackBh);         }     }          private static class TreeNode {         int minRedBh = 0, maxRedBh = 0;         int minBlackBh = 0, maxBlackBh = 0;         int key;         boolean isRed = true;                  TreeNode left;         TreeNode right;     } } 

        

今天 17:52:11 回复(1)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 证明每一棵AVL树都可以被涂成红黑树。所有的红黑树都是AVL树吗?-笔试面试资料

提供最优质的资源集合

立即查看 了解详情