一、定义
均衡树是搜寻树与堆的联合数学构造
均衡树是一颗空树或者其左右子树高度相差不大于1，并且左右两颗子树都是均衡二叉树。
均衡树与二叉搜寻树的区别：均衡树自身是二叉搜寻树，但其来源gaodai$ma#com搞$$代**码网是二叉搜寻树通过”旋转“失去的最优二叉搜寻树 （最优二叉搜寻树：具备起码的均匀比拟次数的二叉搜寻树，均匀比拟次数=每个结点的查找概率*查找该节点的比拟次数(从各节点一层一层还是比拟，也就是层数)）求和），集体了解均衡树不肯定是二叉，B树就能够是多叉。
二、特点
均衡树的均匀查找时间 小于等于 二叉搜寻树的均匀查找时间
三、分类
(1)均衡二叉树
(2)红黑树
(3)B树
根节点至多两个子节点，至少M个子节点
其余节点至多M/2个子节点，至少M个子节点
每个节点至多M/2-1个Key，至少M-1个Key，并且升序排列
所有叶子节点位于同一层
实用于查问多
(4)B+树
非叶子节点只存储Key值，不存储数据>叶子节点存储key值和数据。非叶子节点仅具备索引性能，跟记录无关的信息寄存在叶子节点
叶子节点减少链指针，所有叶子节点形成一个有序链表
实用于索引与数据的拆散
一个节点中的 key 从左到右非递加排列，如果某个指针的左右相邻 key 别离是 keyi 和 keyi+1，且不为 null，则该指针指向节点的所有 key 大于等于 keyi 且小于等于 keyi+1。
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：关于java:平衡树
转载请注明原文链接：关于java:平衡树
