云南建设投资集团网站/黑科技引流推广神器免费

二叉查找树

1. 特征

1. 左子树上所有节点的值均小于或等于他的根节点的值
2. 右子树上所有节点的值均大于或等于他的根节点的值
3. 左右子树也分别为二叉排序树

二叉平衡树（AVL树）

1. 介绍

AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，AVL数是严格的平衡二叉树，

2. 局限性

由于维护这种高度平衡（即所有节点的左右子树高度差绝对值不超过1），不管是执行插入还是删除操作，只要不满足平衡条件，就必须通过旋转来保持平衡，而旋转是非常耗时的，所以，AVL数适合于插入和删除次数比较少，但查找多的情况。

红黑树

1. 红黑树特征

红黑二叉树是一棵二叉搜索树，它在每个节点增加了一个存储位记录几点的颜色，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。

2. 红黑树具体特征

1. 每个节点的颜色不是红色就是黑色
2. 根节点是黑色的
3. 如果一个节点是红色，那么它的两个子节点就是黑色的
4. 对于每个节点，从该节点到其后代叶子节点的简单路径上，均包含相同数目的黑色节点
5. 每个叶子节点都是给色的

3. 红黑树的查找时间复杂度

O(logn)

4. 面试问题一：hashMap的复杂度比rbtree要小，为啥epoll采用rbtree？

为了解决过度哈希冲突带来的长链表，会将链表转为红黑树

5. 和平衡二叉树比较

红黑树确保没有一条路径会比其他路径长出两倍，因此红黑树是弱平衡二叉树，但是相对于严格要求的AVL树来说，红黑树旋转次数更少，因此对于搜索、插入、删除较多的操作下，红黑树更合适。