红黑树的定义和性质 红黑树的出现之前，先有的二叉查找树(BST)以及平衡二叉树(AVL树)： BST根节点的值大于所有左子树的所有值，小于右子树的所有值。 AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的高度差为小于等于1。 AVL的出现改变了BST可能退化为单链表的缺点，AVL在查找时候的性能取决于树的高度，但是在插入和删除的时候性能不如人意。进而发展出了红黑树这一数据结构，因此红黑树是一种特化的AVL树。 红黑树具有五条基本的性质： 根节点是黑色的 Null叶子节点是黑色的 节点只…

一点碎碎念   最近这几天，在搞华为的软件精英挑战赛，虽然比赛打的不咋地，但是好在能把以前的数据结构，图论相关知识复习一下（心态还是要摆正的）。不过话说回来，参加华为软件精英挑战赛，一定要熟悉C++，其他的Python，Java，C都是弟弟，不然时间上吃大亏。今年的初赛考察的是有向图寻找闭环的知识点，既然考察了有向图，那就顺带把无向图也一块温习一遍。 图的基本分类与储存   图的分类依据有很多种，比较重要的两种分类依据就是分为有向图和无向图，稀疏图和稠密图。如何正确的分类会直接影响之后算法的选择，其中有向图和无向图…