mysql二叉树和红黑树的区别是什么?

TheDisguiser 2020-08-09 22:22:36 java常见问答 7738

小伙伴们知道mysql中二叉树和红黑树的区别吗?虽然它们都沾着一个树字,但区别可不小,本篇文章就跟着小编来瞧瞧它们的区别吧。

二叉树

二叉树,指在计算机科学中的一种树结构,这种树结构每个结点最多有两个子树,一般被称为左子树(left subtree)与右子树(right subtree)。

在二叉树层中,一棵深度为k,且具有2^k-1个结点的二叉树,被称为满二叉树。这种树的特点是每一层的结点数都是最大结点数,并且在一棵二叉树中,除最后一层外,若其余层都是满的,或者最后一层是满的,又或者是在右边缺少连续若干结点的话,这种二叉树就叫完全二叉树。二叉树层中,具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树,至少有2k-1个叶子结点,至多有2k-1个结点。

二叉树一般是递归定义的,结点有左右子树之分,并且在逻辑上有五种基本型态。

树类型

完全二叉树:设二叉树的高度为n,除n 层外,其余各层 (1~h-1) 的结点数都达到最大个数,第n层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。

满二叉树:满二叉树是除了叶结点外每一个结点都有左右子叶并且叶子结点都处在最底层的二叉树。

平衡二叉树:平衡二叉树又被称为AVL树(区别于AVL算法),它是一棵二叉排序树,具有以下性质:它是空树,它的左右子树的高度差绝对值不超过1,并且左右两个子树都是平衡二叉树。

红黑树

红黑树不追求“完全平衡 ”,它只会求部分达到平衡要求,降低了对旋转的要求,从而提高性能。

红黑树可以以 O(log2 n) 的时间复杂度进行查询、插入、删除等操作。此外,由于它的设计,所有不平衡都能够在三次旋转之内解决。在红黑树中,它的算法时间复杂度与AVL相同,并且统计性能会比AVL树更高。

红黑树并不适应所有应用树的领域。如果数据上是静态的话,那么让他们待在他们能够插入,且不影响平衡的地方会具有更好的性能。如果数据是完全静态的话,试着做一个哈希表,性能可能会更好一些。

以上就是本文的所有内容,有关红黑树和二叉树区别就到这了,还有什么想了解的java常见问答知识欢迎关注。

推荐阅读:

红黑树是什么?红黑树特点有哪些?

跳跃表和红黑树的区别是什么?它们都有什么概念?

红黑树删除节点最坏时间复杂度怎么删?红黑树结构教程