![](https://csdnimg.cn/release/download_crawler_static/87500419/bg1.jpg)
蚂蚁 Java 一面
1.
二叉搜索树和平衡二叉树有什么关系,强平衡二叉树(AVL 树)和弱平衡二叉树
(红黑树)有什么区别
二叉搜索树:也称二叉查找树,或二叉排序树。定义也比较简单,要么是一颗空
树,要么就是具有如下性质的二叉树:
(1)
若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的
值;
(2)
若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的
值;
(3)
任意节点的左、右子树也分别为二叉查找树;
(4)
没有键值相等的节点。
平衡二叉树:在二叉搜索树的基础上多了两个重要的特点
(1)
左右两子树的高度差的绝对值不能超过 1;
(2)
左右两子树也是一颗平衡二叉树。
红黑书:红黑树是在普通二叉树上,对每个节点添加一个颜色属性形成的,需要
同时满足一下五条性质
(1)
节点是红色或者是黑色;
(2)
根节点是黑色;
(3)
每个叶节点(NIL 或空节点)是黑色;
(4)
每个红色节点的两个子节点都是黑色的(也就是说不存在两个连续的红色节
点);
(5)
从任一节点到其没个叶节点的所有路径都包含相同数目的黑色节点。
区别:AVL
树需要保持平衡,但它的旋转太耗时,而红黑树就是一个没有 AVL
树
那样平衡,因此插入、删除效率会高于 AVL 树,而 AVL
树的查找效率显然高于红黑树。
参
考文章 1:https://blog.csdn.net/qq_25940921/article/details/82183093
参考文章 2:https://blog.csdn.net/yang_yulei/article/details/26066409
2.
B 树和 B+树的区别,为什么 MySQL 要使用 B+树
B 树:
(1)
关键字集合分布在整颗树中;
(2)
任何一个关键字出现且只出现在一个结点中;
(3)
搜索有可能在非叶子结点结束;
(4)
其搜索性能等价于在关键字全集内做一次二分查找;
B+树:
(1)
有 n 棵子树的非叶子结点中含有 n 个关键字(b 树是 n-1
个),这些关键字不保
存数据,只用来索引,所有数据都保存在叶子节点(b 树是每个关键字都保存数据);
(2)
所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,
且叶子结点本身依关键字的大小自小而大顺序链接;
(3)
所有的非叶子结点可以看成是索引部分,结点中仅含其子树中的最大(或最小)
关键字;
(4)
通常在
b+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结
点;
(5)
同一个数字会在不同节点中重复出现,根节点的最大元素就是
b+树的最大元
素。
B+树相比于 B 树的查询优势: