[算法]二叉树的动画讲解-AVL树原创

这是一棵树，这是一棵程序员的树。今天我们要聊聊算法中的二叉搜索树。二叉树作为一棵树，只有一个根节点，如果没有子节点，那就是叶子节点，会有很多二叉树节点之多于两个子节点，一左一右，左子节点包括它的徒子徒孙都会小于父节点，父节点又会小于右子节点和它的徒子徒孙，这一特性在左右的子数中同样成立。如果现在我们要查找11这个值，先从根节点开始比较，发现比五大，那么按照上述的特性直接和右子节点八比较，发现也比八大，那么就是在选择柚子节点的11，发现一样结束查找，总共比较三次，我们发现比较次数就是数的高度，三次相比于线性数据结构，比如列表，如果同样需要查找11的话，那么就需要从头开始，一个一个。

给你一直到最后，那么总共需要七次，所以二叉树的结构可以更快速。那么如果有很多个呢？查找次数又是多少呢？或者说树的高度是多少呢？我反而起到而行之数一数第零层基根节点有一个，第一层有两个，第二层有四个，第三层有八个，那么第N层的话就有二的N次方各节点，所以如果这N加一层包含的所有节点15是所有值的加和二的N加一次方减一相当于可以容纳的节点数M，反过来就是LOG2M加一减一等于N，简而言之就是大o log m的时间复杂度。然后这棵树很平衡，我们就叫平衡二叉树。平衡二叉树的定义是任何节点的左子数和右子数的高度差不超过一，就可以称为平衡二叉数。如果我们继续插入直六，按照差照。

的方式，先和五比较，然后再和八比较，最后和七比较，最终成为七的左子节点，那么这里的785节点看起来不对称，但是它们的高度差都是一，所以仍然是平衡的。那么二叉数平衡有什么好处吗？现在有一组树，从一到十，按照顺序先把一作为根节点，然后插入二，再插入三，以此类推。这是一棵线性结构的树，所以它的时间复杂度就是大OM，而一棵平衡二叉树的时间复杂度则是大o log，而不平衡的树则处于这两者之间。所以平衡二叉树是R叉树中查到最优的结构。那么如何保持平衡状态呢？这种自平衡的二叉树就叫AV2数自平衡一共有四种情况，第一种，插入值一，通过比较成为节点三的左子节点，那么节点九的左子数有三层。

右子数只有一层变成不平衡了，那么现在从插入的节点一出发，向上追寻最近的不平衡子数的根节点是节点九，然后九节点的左子节点右在这个路径上，所以有两个左，称为左左类型。对于这样的结构，需要将这三个节点右旋，也就是将六作为根节点，九作为六的右子节点，三还是六的左子节点，七变成九的左子节点，三的子节点保持不变。第二种插入值六通过比较成为节点七的左子节点。如上的方式，从六出发，找到第一个不平衡子数的根节点，也就是九，往下沿着路径分别是节点五和节点七，所以是先左后右，是左右类型。现在对五和七左旋调整剩下的六，再和刚才一样把七和九右旋调整五的子数。

与上述两种对称的结构分别是右右类型和右左类型。从插入点出发直到不平衡子数的根节点，右右类型选择左旋达到平衡，右左类型先右旋再左旋达到平衡。avr数节点的删除导致不平衡也是类似的方式。