Open
Description
树
是以边(edge)相连的结点(node)的集合，每个结点存储对应的值(value/data)，当存在子结点时与之相连
二叉树
树的任意节点至多包含两棵子树
满二叉树(完美二叉树)
每一层都挂满2个节点,所以一颗深度为h的满二叉树的节点数目是2^h - 1
完全二叉树
完全二叉树就是除最后一层之前的都是满节点，最后一层从左向右排列但是不需要排满
霍夫曼树
带权路径最短的二叉树称为哈夫曼树或最优二叉树
二叉查找树（二叉搜索树、二叉排序树、BST）
若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值
若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值
任意节点的左、右子树也分别为二叉查找树
没有键值相等的节点
二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低,最好为O(logn),最差为O(N)也就是退化为线性列表
二叉搜索树的中顺遍历可以得到一个有序的数值
平衡二叉树
平衡二叉树又称为 AVL 树，其实就是一颗 平衡的二叉排序树,在二叉查找树中，
任一节点对应的两棵子树的最大高度差为 1，这样的二叉查找树称为平衡二叉树。
右子树的高度减左子树的高度得到的差叫做平衡因子,该值应为0，1，-1.如果不是这三个值，那么说明需要平衡该AVL树,这个时候需要找到最近的不平衡的树通过旋转来调整
插入二叉树总共有四种情况会导致树的不平衡
-
第一种情况RR,如果需要平衡必须以18节点为轴进行左旋转
-
第二种情况 LR, 为了平衡二叉树必须先左旋（RR）再右旋（LL）
-
第三种情况 RL，为了平衡二叉树必须先左旋（LL）再右旋（RR）
-
第四种情况LL, 如果需要平衡必须以7节点为轴进行右旋转
