最后更新于
最后更新于
二叉搜索树又名二叉排序树, 二叉查找树. 具有以下的性质:
若它的左子树不空, 则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空, 则右子树上所有结点的值均大于它的根结点的值
它的左, 右子树也分别为二叉排序树
BST的查找, 插入, 删除节点的方法参考: .
二叉排序树有一个重要的性质:
中序遍历一棵二叉搜索树的结果是得到一个升序序列
这个性质在, 以及中都有使用.
二叉搜索树有一个缺点, 在插入数据是有序的序列, 会导致二叉树退化成链表, 从而导致在查找, 删除, 插入时的性能均从降为, 如下图:
它的左右两个子树的高度差的绝对值不超过1
平衡二叉树的左右两个子树都是一棵平衡二叉树
节点的平衡因子是它的左子树的高度减去它的右子树的高度, 带有平衡因子1, 0, -1的节点被认为是平衡的; 带有平衡因子-2或2等的节点被认为是不平衡的, 并需要重新平衡这个树. 平衡因子可以直接存储在每个节点中, 或从可能存储在节点中的子树高度计算出来.
详情参考:
红黑树是一种平衡二叉树, 是一种复杂的平衡树结构. 红黑树出现的原因, 是平衡树要求每个节点的左子树和右子树的高度差至多等于1, 这个要求实在是太严了, 导致每次进行插入/删除节点的时候, 几乎都会破坏平衡规则, 进而我们都需要通过左旋和右旋来进行调整, 使平衡树的性能大打折扣.
红黑树是一种不大严格的平衡树, 使得在插入, 删除等操作时, 不会像平衡树那样, 频繁着破坏红黑树的规则, 所以不需要频繁着调整, 性能超高.
为了解决这个问题, 需要给二叉搜索树赋予平衡特性, 使得查找, 删除, 插入的平均及最差情况下时间复杂度都为.
平衡树是有多种多样的形式, 具体参考.
是最早被发明的自平衡二叉查找树, 它满足:
查找, 插入和删除在平均和最坏情况下的时间复杂度都是. 增加和删除元素的操作则可能需要借由一次或多次树旋转, 以实现树的重新平衡.