二叉排序树#
二叉排序树, 又叫二叉搜索树 , BST (Binary Search Tree)
- 线性存储和链式存储的优缺点
比如我们有一个数组 [7,3,10,12,5,1,9]
虽然我们可以直接取出下标为几的元素,但是却不能直接取出值为几的元素, 比如,我们如果想取出值为9的元素的话,就得先去遍历这个数组, 然后挨个看看当前位置的数是不是9 , 就这个例子来说我们得找7次
假设我们手里的数组已经是一个有序数组了 [1,3,5,7,9,11,12]
我们可以通过二分法快速的查找到想要的元素,但是对它依然是数组,如果想往第一个位置上插入元素还是需要把从第一个位置开始的元素,依次往后挪. 才能空出第一个位置,把新值放进去
假设我们将这一行数转换成链式存储, 确实添加, 删除变的异常方便, 但是查找还是慢, 不管是查询谁, 都得从第一个开始往后遍历
- 我们的主角: 二叉搜索树
二叉排序树有如下的特点:
- 对于二叉排序树中的任意一个非叶子节点都要求他的左节点小于自己, 右节点大于自己
- 空树也是二叉排序树
将上面的无序的数组转换成二叉排序树长成下图这样
如果我们按照中序遍历的话结果是: 1 3 5 7 9 11 12 , 正好是从小到大完成排序
再看他的特征: 如果我们想查找12 , 很简单 7-10-12 , 如果我们想插入也很简单,它有链表的特性
java&二叉排序树#
封装Node和Tree
// tree public class BinarySortTree { Node root; } // node public class Node { private int value; private Node leftNode; private Node rightNode; }
构建一颗二叉排序树, 思路是啥呢? 如果没有根节点的话,直接返回,如果存在根节点, 就调用根节点的方法,将新的node添加到根节点上, 假设我们现在遍历到的节点是NodeA. 新添加的节点是NodeB, 既然想添加就得比较一下NodeA和NodeB的值的大小, 将如果NodeB的值小于NodeA,就添加在NodeA的右边, 反之就添加在NodeA的左边
-----------BinarySortTree.class--------------- /** * 向二叉排序树中添加节点 */ public void add(Node node) { if (root == null) { root = node; } else { root.add(node); } } -------------Node.class------------ /** * 添加节点 * * @param node */ public void add(Node node) { if (node == null) return; //判断需要添加的节点的值比传递进来的节点的值大还是小 // 添加的节点小于当前节点的值 if (node.value < this.value) { if (this.leftNode == null) { this.leftNode = node; } else { this.leftNode.add(node); } } else { if (this.rightNode == null) { this.rightNode = node; } else { this.rightNode.add(node); } } }
删除一个节点
删除一节点有如下几种情况, 但是无论是哪种情况,我们都的保存当前节点的父节点, 通过他的父节点对应节点=null实现节点的删除
情况1: 如图
这是最好处理的情况, 就是说需要删除的元素就是单个的子节点
情况2: 如图
这种情况也不麻烦,比如我们想删除上图中的2号节点, 我们首先保存下node2的父节点 node7, 删除node2时发现node2有一个子节点,于是我们让 node7 的 leftNode = node1
情况3: 如图
比如我们想删除7, 但是7这个节点还有一个子树 按照中序遍历这个树的顺序是 1,3,5,7,9,11,13, 想删除7的话,其实
- 临时存储node9
- 删除node9
- 用临时存储的node9替换node7
如果node9还有右节点怎么办呢?
- 临时保存node9
- 删除node9
- 让node9的右节点替换node9
- 让临时存储的node9替换node7
/** * 删除一个节点 * * @param value * @return */ public void delete(int value) { if (root == null) { return; } else { // 找到这个节点 Node node = midleSearch(value); if (node == null) return; // 找到他的父节点 Node parentNode = searchParent(value); // todo 当前节点是叶子节点 if (node.getLeftNode() == null && node.getRightNode() == null) { if (parentNode.getLeftNode().getValue() == value) { parentNode.setLeftNode(null); } else { parentNode.setRightNode(null); } // todo 要删除的节点存在两个子节点 } else if (node.getLeftNode() != null && node.getRightNode() != null) { // 假设就是删除7 //1. 找到右子树中最小的节点,保存它的值,然后删除他 int minValue = deleteMin(node.getRightNode()); //2.替换被删除的节点值 node.setValue(minValue); } else { // todo 要删除的节点有一个左子节点或者是右子节点 // 左边有节点 if (node.getLeftNode() != null) { // 要删除的节点是父节点的左节点 if (parentNode.getLeftNode().getValue() == value) { parentNode.setLeftNode(node.getLeftNode()); } else {// 要删除的节点是父节点的右节点 parentNode.setRightNode(node.getLeftNode()); } } else { // 右边有节点 // 要删除的节点是父节点的右节点 if (parentNode.getLeftNode().getValue() == value) { parentNode.setLeftNode(node.getRightNode()); } else {// 要删除的节点是父节点的右节点 parentNode.setRightNode(node.getRightNode()); } } } } } /** * 删除并保存以当前点为根节点的树的最小值节点 * @param node * @return */ private int deleteMin(Node node) { // 情况1: 值最小的节点没有右节点 // 情况2: 值最小的节点存在右节点 // 但是下面我们使用delete,原来考虑到了 while(node.getLeftNode()!=null){ node=node.getLeftNode(); } delete(node.getValue()); return node.getValue(); } /** * 搜索父节点 * * @param value * @return */ public Node searchParent(int value) { if (root == null) { return null; } else { return root.searchParent(value); } }
缺点#
二叉排序树其实对节点权是有要求的, 比如我们的数组就是[1,2,3,4] 那么画成平衡二叉树的话长下面这样
它不仅没有二叉排序树的优点,而且还不如单链表的速度快
AVL树（平衡二叉树)#
定义: 什么是平衡二叉树#
平衡二叉树的出现就是为了 解决上面二叉排序树[1,2,3,4,5,6]这样成单条链的略势的情况,它要求,每个树的左子树和右子树的高度之差不超过1, 如果不满足这种情况了,马上马对各个节点进行调整,这样做保证了二叉排序树的优势
如何调整#
- 情况1: 对于node1来说, 它的左边深度0 , 右边的深度2 , 于是我们将它调整成右边的样子
- 情况2: 在1234的情况下, 添加node5,导致node2不平衡, 进行如下的调整
- 情况3: 在12345的基础上添加node6,导致node4不平衡, 对node4进行调整, 其实就和情况1相同了
- 情况4: 在1234567的情况下,进行添加8. 打破了node5的平衡, 因此进行旋转
一个通用的旋转规律
看这个典型的有旋转的例子
node4的出现,使用node8的平衡被打破, 因此我们需要进行调整, 按照下面的步骤进行调整
下面说的this是根节点node8, 按照下面的步骤在纸上画一画就ok
- 创建新node, 使新node.value = this.value
- 新节点的rightNode = this.rightNode
- 新节点的leftNode = this.leftNode.rightNode
- this.value = this.LeftNode.value
- this.leftNode = this.leftNode .leftNode
- this.leftNode = 新创建的node
**需要注意的情况: **
新添加6使得node8不再平衡,但是如果你按照上面的步骤进行旋转的话,会得到右边的结果, 但是右边的结果中对于node4还是不平衡的,因此需要预处理一下
再进行右旋转时,提前进行检验一下,当前节点的左子树是否存在右边比左边高的情况, 如果右边比较高的话,就先将这个子树往左旋转, 再以node8为根,整体往右旋转
