AVL树和红黑树

目录

前言

一、AVL树

1、AVL树概念

2、AVL树节点的定义

3、AVL树的插入 

 4、AVL树的旋转

 5、AVL树的删除

二、红黑树 

1、红黑树的概念

2、红黑树节点的定义

3、红黑树的插入操作 

三、红黑树与AVL树比较

---

前言

哈喽，小伙伴们大家好。之前我们介绍了二叉搜索树用于搜索数据，但是二叉搜索树具有一些缺陷，比如在大多数节点的子节点都只有一个时，那搜索二叉树就会近似成一条线，搜索的时间复杂度就会从O(logN)退化成O(N)。针对这个问题，一些人对二叉搜索树进行了升级改造，也就是我们今天要学习的AVL树与红黑树。

---

一、AVL树

1、AVL树概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查
找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis（AVL树正是由这两位数学家的名字命名的）在1962年发明了一种解决上述问题的方法：当向一棵搜索二叉树中插入新节点时，要通过调整，使每个节点的左右子树高度差的绝对值不超过1，这样就能使二叉树接近满二叉树，进而提高搜素效率。

一棵AVL树具有以下性质：

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)