平衡二叉树（AVL）
2018-12-18 本文已影响0人
仲达_dc6c
排序二叉树在有的时候性能不好，最极端的情况就变成了单链表的样子，升级版本平衡二叉树。
平衡二叉树，每一个节点的左右两个子树的深度相差不会超过2.
建立二叉树的过程，会用到左旋转和右旋转。
左平衡操作:节点t的不平衡因子，左子树太深。用到了左旋转和右旋转
分为4中情况：
2.如果新的结点插入到t的左孩子的右子树中，则需要进行分情况讨论
排序二叉树在有的时候性能不好，最极端的情况就变成了单链表的样子，升级版本平衡二叉树。
平衡二叉树，每一个节点的左右两个子树的深度相差不会超过2.
建立二叉树的过程，会用到左旋转和右旋转。
左平衡操作:节点t的不平衡因子，左子树太深。用到了左旋转和右旋转
分为4中情况：
2.如果新的结点插入到t的左孩子的右子树中，则需要进行分情况讨论
