每日一博 | 二叉树解题思维
二叉树小科普 ⼆叉树是最多仅有两个子节点的树，根据节点的分布情况可分为： 平衡二叉树: 每个结点的左右子树的高度相差不能大于1 满二叉树: 除了最底层的叶节点，每个结点都有左右子树 完全二叉树: 深度(1～H-1)的结点数达到最大个数，深度H的结点都连续集中在最左边，比如堆 二叉搜索树：每个节点必须满足：节点值>=左子节点，<=右子节点，其中序遍历就是有序序列 1、二叉搜索树 n个元素的二叉搜索树，理想情况下，查找、插入的时间复杂度是O(logn)，但在一直递增或递减的场景下进行插入，会导致所有的元素出现在树的左节点上，此时类似于链表结构，时间复杂度趋向于O(n)，因此诞生了 平衡二叉搜索树(AVL)：要求严格的平衡性控制，不会出现平衡因子超过1的情况 红黑树：查找、插⼊、删除操作在最坏情况下的时间复杂度不超过 O(logn)，并且有较⾼的插⼊和删除效率 1.1、红黑树 红黑树是一种自平衡的二叉搜索树，任何不平衡都会在三次旋转内解决。它不仅满足搜索树的特点，而且满足： 黑根黑叶：根节点必须是黑色的、叶子节点均是值为null的黑节点 红结黑子：节点可红可黑，若是红色的，则它的...
