AVL树

    今天学习avl树：

今天是根据7.5   AVL 树 * - Hello 算法学习的

     首先我们需要知道树是会退化的，在多次插入和删除操作后，二叉树可能会变成链表，接下来就给你们展示一个案例。

这里先创建一个二叉树，等会展示一下退化的二叉树。

1
2
3
4
5
6
7
from binarytree import Node
if __name__ == '__main__':
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.right.left = Node(5)
    root.right.right = Node(6)

这里展示一下生成的树

                                                                        1

                                                                      /    \

                                                                   2        3

                                                                /        /        \

                                                            4        5            6

 然后来写一个删除节点和一个插入节点的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#删除节点
def delete_node(new_node, data):
    if not new_node:
        return
    if new_node.val is data:
        return
    new_node.left = delete_node(new_node.left, data)
    new_node.right = delete_node(new_node.right, data)
    return new_node   
#插入节点
def insert_node(new_node, father_data, data=0):
    if not new_node:
        return
    if new_node.val == father_data:
        if new_node.left and new_node.right:
            return
        elif new_node.left and not new_node.right:
            new_node.right = Node(data)
        elif new_node.right and not new_node.left:
            new_node.left = Node(data)
    new_node.left = insert_node(new_node.left, father_data, data)
    new_node.right = insert_node(new_node.right, father_data, data)
    return new_node

     我写的删除节点会连带删除它的子节点，所以这里在删除节点3、4，然后在节点2后插入3,3后插入4….6后插入7，于是就退化到了如图所示的这样的队列形态

                                                                1

                                                              /

                                                           2

                                                         /

                                                      3

                                                    /

                                                 4

                                                /

                                             5

                                           /

                                        6

                                      /

                                   7  

    那么为了尽可能保证在一系列删除和插入后依旧能保持二叉树的平衡性，AVL树 被提出来了,称作 平衡二叉搜索树 （二叉搜索树的特征是节点的右子树根节点值大于父节点，左子树根节点值小于父节点；二叉平衡树的特征是它的左子树和右子树的高度之差的绝对值（又称平衡因子）不超过1，且左子树和右子树都是平衡二叉树）。

树的高度指的是树的最底层叶子到该节点的路径长度，拿上图生成的那棵树举例，1 节点的高度为2,3 节点的高度为1,5节点的高度为0（因为5就是右子树的最底层）

    顾名思义，AVL树同时具有二叉搜索树和平衡二叉树的特征，所以AVL树节点的插入和删除都离不开树的旋转 来保持平衡 。

树的旋转

    百度上的解释是：树旋转是在二叉树中的一种子树调整操作， 每一次旋转并不影响对该二叉树进行中序遍历的结果。这里提到中序遍历很容易就联想到平衡二叉树，那么接下来就拿平衡二叉树来举例讲解。

   先假设有一颗平衡二叉树A：

                                                            9

                                                        /        \

                                                      6            13

                                                    /    \          /

                                                4         7  2

这张图上那个2就先假设是13的左子树

接下来将9向右旋，那么很明显9就会成为6的右子树，而原先是6右子树的7就会和6断开

                                                6

                                            /        \

                                        4                9

                                                                \

                                                    7            13

                                                                /

                                                            2                                                                  

前面已经说过，树旋转之后的中序遍历顺序是不会变的，那么只需要简单算一下很快就能知道，旋转后7会成为9的左子树。

                                                               6

                                                           /      \

                                                        4            9

                                                                  /        \

                                                              7             13

                                                                           /

                                                                        2

根节点右旋一般会成为左子树的右节点,左旋一般会成为右子树的左节点。

暂时就想到这么多，我也是边学边写，有不到或者错误的地方大家多多包涵。