二叉树 about blog HOT 1 OPEN

二叉查找树

又称二叉排序树，其特性：

• 左子树上所有结点的值均小于或等于它的根结点的值
• 右子树上所有结点的值均大于或等于它的根结点的值
• 左、右子树也分别为二叉排序树

如图：

查找规则

• 如果二叉查找树为空，则返回空操作，否则，执行一下操作
• 先取根节点，如果节点 X 等于根节点，则返回
• 如果节点小于根节点，则递归查找左子树
• 如果节点大于根节点，则递归查找右子树

查找的最大次数等同于树的高度

插入

• 若树为空则直接将新节点插入，否则执行下面步骤
• 要插入的数据比根节点数据大，遍历右子树，如果右子树为空，则将新数据直接插入到右子节点的位置；不为空，则继续遍历右子树
• 要插入的数据比根节点数据小，遍历左子树，如果左子树为空，则直接将新数据插入到左子节点的位置；不为空，则继续遍历左子树

删除

删除可以从以下三种情形来理解，如图：

注：图来自于极客时间《数据结构与算法之美》专栏

• 要删除的节点没有子节点，修改父节点的指向为 null，如上图要删除的节点 55
• 要删除的节点只有一个节点，即只有左子节点或右子节点，则将要删除节点的父节点的指针指向要删除节点的子节点即可，如上图要删除的节点 13
• 果要删除的节点有两个子节点，则需要先找到这个节点右子树中的最小节点或者左子树中的最大节点，将其替换到要删除的节点上，然后删除这个右子树中的最小节点或左子树中的最大节点，如上图要删除的节点 18

缺点或者说是局限性

二叉搜索树最坏情况可能是链表，相应的时间复杂度是 O(n) 级别

红黑树

红黑树是一种自平衡的二叉查找树，除了符合二叉查找树的基本特征外，还具备：

• 节点是红色或黑色
• 根节点是黑色
• 每个叶子节点都是黑色的空节点（NIL节点）
• 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

from blog.