那些年面试官问你的红黑树----->(浅谈)
在了解红黑树之前,先要了解二叉树,又叫二叉查找树、二叉搜索树、二叉排序树。二叉树顾名思义: 是一种每个节点最多有两个子节点的树,同时遵循 左节点的值<父节点的值<右节点的值 这样的规律。 二叉树有如下几个特点: 节点的左子节点小于节点本身 节点的右子节点大于节点本身 左右节点同样为二叉搜索树 下图就是一棵典型的二叉树: 它是一种查找次数小于等于树高的数据结构。如图中树有4层,即树高为4,当我们需要查找8时,经过的路线是这样的: 1、8<9,往左查找 2、8>5,往右查找 3、8>7,往右查找 4、8=8,找到结果 总共查找4次,等于树高。这棵树不管怎么找,查找次数总是小于等于树高。 二叉树的插入同样遵循上述规则,会一步一步对比,从而找到插入的位置,可以想象上图中的8不存在,而是需要插入一个8,结果与上述路线一致。 二叉树的删除会涉及到无子节点和有子节点两种情况,无子节点直接删除即可,有子节点会需要用左边最大值或右边最小值替换当前删除节点,具体不细聊。 当二叉树插入数值不均衡时,会出现树结构的变形与查找性能的损耗,比如现在二叉树有8,9,12三个值,然后需要...