二叉树

二叉树：每个结点最多有两个子树的结构被称作二叉树

满二叉树:除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树

完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1-h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布

image.png

平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

什么是二叉排序树（bst）：又称二叉查找树。

它或者是一棵空树；或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
二叉树遍历：

前序遍历： 根左右

中序遍历： 左根右

后序遍历： 左右根

层遍历： 暂略
前序遍历：W 型

二叉树旋转：

左旋： 自己（P）变为右孩子的左孩子

右旋： 自己（Q）变为左孩子的右孩子

下图所示 对节点Q 的右旋，对节点P 的左旋，二者为互逆操作

image.png

旋转的几种情况

image.png

二叉树旋转判断：（如果左 右子树 高度 差2 则需要旋转）

判断添加 或 删除 的数据 在树根的左节点 还是 右节点
左侧 分为 左左（右旋） 左右（左旋右旋）
右侧 分为 右右（左旋） 右左（右旋 左旋）

左旋

image.png

右旋

image.png

平衡二叉树、B树、B+树、B*树 https://zhuanlan.zhihu.com/p/27700617