二叉搜索树、平衡树（AVL）与红黑树的特点

1、二叉搜索树的特点

二叉搜索树：所有左子树的节点比父节点小，所有右子树的节点比父节点大

一般情况下的查询复杂度：O（logn）

最坏情况：当所有的节点以链表形式排列

最坏情况下的查询复杂度：O(n)

2、平衡二叉树的特点

平衡叉树就是为了解决二叉查找树退化成一颗链表而诞生。

特点：

1、具有二叉查找树的全部特性。

2、每个节点的左子树和右子树的高度差至多等于1。

最坏查找时间：O(logn)

存在问题：平衡树要求每个节点的左子树和右子树的高度差至多等于1，导致每次进行插入/删除节点的时候，几乎都会破坏平衡树的第二个规则，进而需要通过左旋和右旋来进行调整，使之再次成为一颗符合要求的平衡树。

3、红黑树的特点

在插入、删除很频繁的场景中，平衡树需要频繁着进行调整，这会使平衡树的性能大打折扣，为了解决这个问题，于是有了红黑树。

红黑树的特点：

1、具有二叉查找树的全部特性。

2、根节点是黑色

3、每个叶子节点是黑色的空节点。

4、相邻节点不能同时为红色。

5、每个节点，从该节点到达其可达的叶子节点是所有路径，都包含相同数目的黑色节点。

最坏情况下查询复杂度：O(logn)

与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整。（红黑树是一种不大严格的平衡树。）