替罪羊树
替罪羊树是一种自我平衡的变种
“替罪羊树”背后的直觉是我们都必须面对的问题。当事情出错时,我们需要找替罪羊。一旦我们找到了替罪羊,就可以让他们来解决问题。插入之后,替罪羊会找到子树不平衡的单个节点。这就是替罪羊。然后重新平衡这个替罪羊的子树。
替罪羊树的实现非常灵活。它们可以以删除和查找为代价对插入进行优化,反之亦然。程序员可以根据特定的应用程序定制替罪羊树的实现,这使得这种数据结构非常有吸引力。
我们找到替罪羊的过程很简单。在下面的动图中,树开始是平衡的。当插入一个新节点(12 in)时,树变得不平衡。从新插入的节点开始,我们检查该节点上的子树根,看看它是否平衡。如果是,我们转到父节点并重复。最终我们会找到一个替罪羊,它的子树是不平衡的,或者我们会在根节点处结束,而树仍然是平衡的。在这种情况下,节点8的子树是不平衡的,所以这是我们的替罪羊。
属性
首先是替罪羊树 替罪羊树只存储以下属性 替罪羊树中的每个节点只有以下属性。
财产
函数
大小
树中的节点数。
根
指向树根的指针。
max_size
树自上次完全重建以来的最大大小。
财产
函数
关键
节点的值。
左
指向节点左子节点的指针。
正确的
指向节点右子节点的指针。
操作
替罪羊树唯一处理两种操作:插入和删除。树的查找和遍历在任何中都是完全相同的
插入
插入过程开始时与二叉搜索树相同。通过找到新节点的适当位置 现在,这棵树需要知道它是否需要重新平衡。它通过查找新节点的祖先来查找子树不平衡的第一个节点。一棵树是否平衡通常是其权重属性的一个因素 重新平衡扎根于替罪羊的大树的实际过程需要 这是因为,在我们重建给定节点上的子树根之前
删除实际上比在替罪羊树中插入更容易。树在这里使用属性 当我们从替罪羊树中删除一个节点时,树会检查是否删除
复杂性
替罪羊树的复杂性与其他树非常相似
参见:
大O符号 .
平均 | |
空间* * | |
搜索 | |
遍历 | * |
插入 | * |
删除 | * |
*平摊分析
但比其他自我平衡更好
Python实现
下面的python实现旨在阐明替罪羊树的一些进程。插入的过程已经列出,但是为了简洁,省略了删除。
注意:在这个实现中,一些东西已经从基本结构中改变了,以使事情更清楚。具体来说,所有节点都指向它们的父节点,以使代码更具可读性。但是,当您沿着树向下插入到堆栈中时,通过跟踪所有父节点,这很容易被忽略。
两个
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17日18 19 20 21日22日23日24日25日26日27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
|