1.二叉树：
复杂度为o(logn),二分查找。任何节点的左边都比它小，右边都比它大；
缺点：有可能会退化成链表，此时复杂度为O(n);
2.平衡二叉树
原则：左子树与右子树的高度差小于等于1；
优点：解决了二叉查找退化为链表的缺点，能把查找时间复杂度控制在O(logn);
缺点：每次增删几乎都会破坏左子树与右子树高度差<=1的原则，需要左旋或者右旋，使得性能大打折扣；
3.红黑树
每个节点到叶子节点的路径，经过的黑色节点数相同，复杂度为O(logn)；
增删节点不易打破红黑树的规则，相对效率更高，但是单查找效率来说，平衡树>红黑树；
红黑树是对平衡树的一种折中；
版权声明：本文为zxjdC原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。