树总结

特别的树

二叉搜索树(BST)

二叉搜索树又名二叉排序树, 二叉查找树. 具有以下的性质:

• 若它的左子树不空, 则左子树上所有结点的值均小于它的根结点的值

• 若它的右子树不空, 则右子树上所有结点的值均大于它的根结点的值

• 它的左, 右子树也分别为二叉排序树

BST的查找, 插入, 删除节点的方法参考: 二叉排序树.

重要性质

二叉排序树有一个重要的性质:

• 中序遍历一棵二叉搜索树的结果是得到一个升序序列

这个性质在[108][简单][DFS][二分] 将有序数组转换为二叉搜索树, 以及[109][中等][DFS][双指针] 有序链表转换二叉搜索树中都有使用.

平衡二叉树

二叉搜索树有一个缺点, 在插入数据是有序的序列, 会导致二叉树退化成链表, 从而导致在查找, 删除, 插入时的性能均从$O(\log{N})$降为$O(N)$, 如下图:

为了解决这个问题, 需要给二叉搜索树赋予平衡特性, 使得查找, 删除, 插入的平均及最差情况下时间复杂度都为$O(\log{N})$.

平衡树是有多种多样的形式, 具体参考平衡树.

AVL树是最早被发明的自平衡二叉查找树, 它满足:

• 它的左右两个子树的高度差的绝对值不超过1

• 平衡二叉树的左右两个子树都是一棵平衡二叉树

查找, 插入和删除在平均和最坏情况下的时间复杂度都是$O(\log{N})$. 增加和删除元素的操作则可能需要借由一次或多次树旋转, 以实现树的重新平衡.

节点的平衡因子是它的左子树的高度减去它的右子树的高度, 带有平衡因子1, 0, -1的节点被认为是平衡的; 带有平衡因子-2或2等的节点被认为是不平衡的, 并需要重新平衡这个树. 平衡因子可以直接存储在每个节点中, 或从可能存储在节点中的子树高度计算出来.

详情参考:

• 什么是平衡二叉树

• AVL树 WIKI

红黑树

红黑树是一种平衡二叉树, 是一种复杂的平衡树结构. 红黑树出现的原因, 是平衡树要求每个节点的左子树和右子树的高度差至多等于1, 这个要求实在是太严了, 导致每次进行插入/删除节点的时候, 几乎都会破坏平衡规则, 进而我们都需要通过左旋和右旋来进行调整, 使平衡树的性能大打折扣.

红黑树是一种不大严格的平衡树, 使得在插入, 删除等操作时, 不会像平衡树那样, 频繁着破坏红黑树的规则, 所以不需要频繁着调整, 性能超高.