树形设计【AVL树,红黑树设计】。
树之设计【AVL树、红黑树的设计】
1,设计之初:
?思考:AVL树的意义:用一个高度平衡的二叉树来维持整棵树为一个平衡的二叉树,所以在继承父类[BST二叉查找树]的基础上,考虑AVL什么时候需要调整它的平衡。
--------------------------------------BST 二叉搜索树,进行插入(增加)结点之后的树,可能失衡,需要调整。
-------------------而调整树的主要工作,应该交由AVL 平衡二叉树来完成
【 过程:BST (内部知道发生了失衡,所以需要做出反应),它定义了一个接口方法(调整平衡方法)来应对失衡情况,这个调整平衡方法,交由能力最强的AVL树去具体实现】
接下来,我们来谈谈调整平衡法的具体实现:
1.首先从插入节点的位置开始,找到第一个不平衡的祖父母节点【这个过程需要判断节点不平衡】-需要节点高度属性。
-
-解决方案:AVL树【此刻需要有一个带有高度属性的节点类】重构节点类,添加高度属性。
2.重构后,回到BST中插入(添加)接口的方法:发现该方法的内部创建结点时,使用的结点对象都是通用的结点,并没有使用 AVL 树定义的结点类对象,小于高度属性。
回到AVL树,在AVL树中无法高度判断是否失衡。
--解决:在BST中定义一个创建结点接口方法(默认:创建的节点是公共节点),然后子类 AVL 树再对创建结点接口方法进行重写,
因此,当您需要在添加(插入)接口的方法中创建节点时,您可以使用创建出带有高度属性的结点对象。.
2,设计过程:
内容来源网络,如有侵权,联系删除,本文地址:https://www.230890.com/zhan/51631.html