树之设计【AVL树、红黑树的设计】

发布时间:2022-07-01 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了树之设计【AVL树、红黑树的设计】脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

树之设计【AVL树、红黑树的设计】

 

1,设计之初:

树之设计【AVL树、红黑树的设计】

 

 ✿ 思考:AVL树的意义:高度平衡二叉树,用来维持整棵树是一棵平衡的二叉树,那么在继承父类【BST 二叉搜索树】基础上,考虑啥时候 AVL需要调整平衡?

  --------------------------------------BST 二叉搜索树,进行插入(增加)结点之后的树,可能失衡,需要调整。

   -------------------而调整树的主要工作,应该交由AVL 平衡二叉树来完成

 

【 过程:BST (内部知道发生了失衡,所以需要做出反应),它定义了一个接口方法(调整平衡方法)来应对失衡情况,这个调整平衡方法,交由能力最强的AVL树去具体实现】

接下来,讲讲 调整平衡方法的具体实现:
1,首先从插入结点位置开始去找,找到第一个失衡的祖父结点【这个过程需要判断结点失衡】------------需要有结点高度属性
                ----------------------结点类是在BT中定义的,定义时高度并不是一个通用的属性,此时需要它时,也不便加入【不通用呀】。
                      --------------解决:AVL 树【此刻需要有一个带上高度属性的结点类】重构一下结点类,以便加入高度这个属性。

2,重构完,回到BST 中的插入(增加)接口方法:发现~该方法内部创建结点时,使用的结点对象都是通用的结点,并没有使用 AVL 树定义的结点类对象,则它就少了高度这个属性,   传回给AVL树中,在AVL树中就没法进行高度判断是否失衡。
    
                  ----------------------解决:在BST中定义一个创建结点接口方法(默认:创建的结点是通用结点),然后子类 AVL 树再对创建结点接口方法进行重写,                          使得 增加(插入)接口方法中需要创建结点时,可以创建出带有高度属性的结点对象。

 

2,设计过程:

树之设计【AVL树、红黑树的设计】

 

脚本宝典总结

以上是脚本宝典为你收集整理的树之设计【AVL树、红黑树的设计】全部内容,希望文章能够帮你解决树之设计【AVL树、红黑树的设计】所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。