树的高度和深度
From CSDN 暴走抹茶MOUKOY
1.高度
对于高度的理解，我们不管他数据结构什么什么知识，就拿楼房来说，假如一个人提问：楼房的高度有好高？我们会下意识的从底层开始往上数，假如楼有6层，则我们会说，这个楼有6层楼那么高，则提问者就会大概知道楼有多高了。所以高度就是从下往上对比，这是我们的习惯。而在树中，树的高度也是从下往上数，如图所示
K节点在树的底层，是一个叶子节点，则一般定义为K的高度在最低为1，以此类推，O的高度也是为1，P的节点也是为1。M节点是叶子节点O的父节点，从下往上数，M节点高度为2。那么G节点的高度是多少呢？从G-L的高度为2，从G-M-O节点高度为3，到底G节点高度为多少呢，正确答案是3，请看定义：
高度的定义为：从结点x向下到某个叶结点最长简单路径中边的条数
注意：对于是否是边的条数这个不清楚，待我后来查证，这个主要是由于其初值是1还是0来确定的，一般都是以1开始
2.深度
理解了高度，则深度的理解就很容易了，深度是从根节点往下，列如上图中：B的深度为2。
3.总结
对于整棵树来说，最深的叶结点的深度就是树的深度；树根的高度就是树的高度。这样树的高度和深度是相等的。
对于树中相同深度的每个结点来说，它们的高度不一定相同，这取决于每个结点下面的叶结点的深度。
AVL Tree
From CSDN PlusPlus1 / 董的博客
一、概述
AVL树是最先发明的自平衡二叉查找树。AVL树以其发明者前苏联学者 G.M. Adelson-Velsky 和 E.M. Landis 名字而命名，他们在1962年的论文《An algorithm for the organization of information》中发表了它。
AVL树中，一个非常重要的概念为平衡因子（Balance factor），对于任意节点 x ，其平衡因子定义为该节点右子树和左子树高度差，即 bf（x）=h（x-right）-h（x-left）。
带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。
二、基本术语
有四种种情况可能导致二叉查找树不平衡，分别为：
（1）LL：插入一个新节点到根节点的左子树（Left）的左子树（Left），导致根节点的平衡因子由1变为2
（2）RR：插入一个新节点到根节点的右子树（Right）的右子树（Right），导致根节点的平衡因子由-1变为-2
（3）LR：插入一个新节点到根节点的左子树（Left）的右子树（Right），导致根节点的平衡因子由1变为2
（4）RL：插入一个新节点到根节点的右子树（Right）的左子树（Left），导致根节点的平衡因子由-1变为-2
针对四种种情况可能导致的不平衡，可以通过旋转使之变平衡。有两种基本的旋转：
（1）左旋转：将根节点旋转到（根节点的）右孩子的左孩子位置
（2）右旋转：将根节点旋转到（根节点的）左孩子的右孩子位置
三、AVL树的旋转操作
AVL树的基本操作是旋转，有四种旋转方式，分别为：左旋转，右旋转，左右旋转（先左后右），右左旋转（先右后左），实际上，这四种旋转操作两两对称，因而也可以说成两类旋转操作。
3.1 LL
下图所示为LL构型，在B节点的左子树上插入节点导致A节点失衡，调整过程为：以B节点为轴心，A节点顺时针旋转至B的右子树，A的右子树用B的右子树代替。通过右旋操作，返回以B为Root的平衡子树。
3.2 RR
RR情况需要左旋解决，如下图所示：
3.3 LR
下图所示为LR构型，在B节点的右子树上插入新节点导致A节点失衡，调整过程分两个步骤：首先以C为轴心，B绕C逆时针旋转，生成的子树作为A的左子树；这样就变化成了LL型，然后用上图所示的方法调整即可。通过先左旋后右旋，返回以C为Root的平衡子树。
3.4 RL
RL情况需要右左旋解决（先B右旋转，后A左旋转），如下图所示：
四、AVL数的插入和删除操作
(1) 插入操作：实际上就是在不同情况下采用不同的旋转方式调整整棵树,向AVL树中插入节点后，要判断是否引起失衡，如果失衡则需要进一步确定构型，选择合适的基本旋转操作来调整。
(2) 删除操作：首先定位要删除的节点，然后用该节点的右孩子的最左孩子替换该节点，并重新调整以该节点为根的子树为AVL树，具体调整方法跟插入数据类似。删除操作对应为插入操作的逆向操作，调整平衡的时候也需要确定被删除节点的分支构型来选择合适的旋转方法。
网友评论