前言
首先声明一点，本文比较苍白无力，因为是看视频理解后用来记录，方便查看的，如想详细学习可私信回复我。
文章内容来自 享学课堂King老师ppt课件；大家不喜勿喷。
1.二叉排序树
二叉排序树(BST，Binary Sort Tree)也称二叉查找树（Binary Search Tree），或二叉搜索树。
满足以下属性：
- 左子树的所有的值小于根节点的值
- 右子树的所有的值大于根节点的值
-
左、右子树满足以上两点
二叉排序树1.png
1.查找操作:Find
查找的值X从根节点开始
1.如果X小于根节点值，则在左子树中继续查找；
2.如果X大于根节点值，则在右子树中继续查找；
3.如果X值等于根节点值，则返回该节点；
4.如果都查不到，则返回空Null；
查找的效率决定于树的高度。
2.插入操作：Insert
插入的值X从根节点开始查找
1.X值小于该节点值，在左子树中继续；
2.X值大于该节点值，在右子树中继续；
3.如果节点是叶节点，X值小于该节点值则插入左子节点，否则插入右节点；
3.删除操作：Delete
插入的值X从根节点开始查找
1.如果节点的值等于X，则删除；
2.X值小于该节点值，在左子树中继续；
3.X值大于该节点值，在右子树中继续；
2.平衡二叉树
平衡二叉树（AVL树，Balance Binary Search Tree ）
它是一 棵二叉排序树，它的左右两个子树的高度差（平衡因子）的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
目的：使得树的高度最低，因为树查找的效率决定于树的高度。
如下：40节点：左子树高度为3，右子树高度为2，满足；
30节点：左子树高度为2，右子树高度为0，不满足；
平衡二叉树2.png
如果A是一颗平衡二叉树，如果新插入一个元素，会有两个结果：
平衡没有被打破，不用调整；平衡被打破，需要调整
调整原则：根据插入节点与失衡结点的位置关系来划分
1.LL旋转
插入节点在失衡结点的左子树的左边，只需要经过一次左旋即可达到平衡
LL旋转.png
2.RR旋转
插入节点在失衡结点的右子树的右边，只需要经过一次右旋即可达到平衡
RR旋转.png
3.LR旋转
插入节点在失衡结点的左子树的右边，失衡结点的左子树先做RR旋转，失衡结点再做LL旋转也可达到平衡
LR旋转.png
4.RL旋转
插入节点在失衡结点的右子树的左边，失衡结点的右子树先做LL旋转，失衡结点再做RR旋转也可达到平衡
RL旋转.png
网友评论