1.二叉搜索树、平衡二叉树
2.平衡二叉树之红黑树、
3.B 树、B+树、B* 树、
4.字典树 ( Trie树 )
二叉搜索树(又名二叉排序树)
特点:
1.左子树上的节点均小于根节点
2.右子树上的节点均大于根节点
二叉平衡树
为什么要有二叉平衡树,二叉搜索树的结构与值的插入顺序有关,同一组数,若其元素的插入顺序不同,二叉搜索树的结构是千差万别的。举个例子,给出一组数[1,3,5,8,9,13]
若按照[5,1,3,9,13,8]这样的顺序插入,其流程是这样的:
若按照[1,3,5,8,9,13]这样的顺序插入,其流程是这样的:
插入的序列越接近有序,生成的二叉搜索树就越像一个链表。
为了避免二叉搜索树变成“链表”,我们引入了平衡二叉树,即让树的结构看起来尽量“均匀”,左右子树的节点数尽量一样多。
如何生成二叉平衡树
先按照生成二叉搜索树的方法构造二叉树,直至二叉树变得不平衡,即出现这样的节点:左子树与右子树的高度差大于1。至于如何调整,要看插入的导致二叉树不平衡的节点的位置。主要有四种调整方式:LL(左旋)、RR(右旋)、LR(先左旋再右旋)、RL(先右旋再左旋)。
二叉平衡树特点:左子树与右子树的高度差不大于1
时间复杂度:log2n
出现不平衡时到底是执行LL、RR、LR、RL中的哪一种旋转,取决于插入的位置。可以根据值的大小关系来判断插入的位置。插入到不平衡节点的右子树的右子树上,自然是要执行LL旋转;插入到不平衡节点的左子树的左子树上,自然是要执行RR旋转;插入到不平衡节点的左子树的右子树上,自然是要执行LR旋转;插入到不平衡节点的右子树的左子树上,自然是要执行RL旋转。
经典面试算法题——判断一棵树是不是平衡二叉树(递归)
https://leetcode-cn.com/problems/balanced-binary-tree/
java:
class Solution {
private int height(TreeNode root) {
if (root == null) {
return -1;
}
return 1 + Math.max(height(root.left), height(root.right));
}
public boolean isBalanced(TreeNode root) {
if (root == null) {
return true;
}
return Math.abs(height(root.left) - height(root.right)) < 2
&& isBalanced(root.left)
&& isBalanced(root.right);
}
};
网友评论