二叉平衡树 Dear 丶 2021-09-22 09:42 410阅读 0赞 ## 二叉平衡树 ## 说起这个树,我找了整整两天的时间,刚开始考虑的不周全,然后就一直该一直该,一直加一直加。 定义: 它是一颗空疏或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一颗平衡二叉树。 二叉查找树的定义: 1、若左子树不为空,那么左子树所有结点的值小于均小于他的根结点的值 2、若右子树不为空,那么右子树的所有结点的值大于根结点的值 3、左右子树也分别为二叉查找树(排序树) 4、没有键值相当的结点 如果不知道二叉查找树了请看我上篇文章(格式不太好) 现在二叉查找树添加的源码: 在这里我定义了root,opRoot两个,root主要是根结点,方便以后去操作,opRoot主要是操作树的。 // 插入元素 public void insert(T t){ if(opRoot == null){ root.setT(t); opRoot = root; return ; } opRoot = root ; Node<T> node = new Node<T>(); node.setT(t); insert(opRoot , node) ; } // 插入值 private void insert(Node<T> opRoot, Node<T> node) { if(opRoot.getT().compareTo(node.getT()) > 0){ if(opRoot.getLeft() != null){ insert(opRoot.getLeft() , node ) ; }else { opRoot.setLeft(node); node.setParent(opRoot); } } if(opRoot.getT().compareTo(node.getT()) < 0){ if(opRoot.getRight() != null){ insert(opRoot.getRight() , node) ; }else { opRoot.setRight(node); node.setParent(opRoot); } } } ## 值已经插进去了,现在我们要判断这四种情况: 1、 在结点x的左孩子的左子树中插入元素(左左) 2、 在结点x的左孩子的右子树中插入元素(左右) 3、 在结点x的右孩子的左子树中插入元素(右左) 4、 在结点x的右孩子的右子树中插入元素(右右) 括号里这些代表有,没写的代表下层没有 **首先看第一种情况:** ![这里写图片描述][format_png] 我是这样考虑的,换位置,把第一个左换到上面,然后把第一个上面的放到有下面,注意:需要断开的一定要断开。 **第四种情况,有类似第一种:** ![这里写图片描述][format_png 1] 类似于上面那种,也是交换位置 还有一个leftOrRight这个类 ![这里写图片描述][format_png 2] ## 这里是段开父类之后,然后下面的那个元素指向父类元素 **第二种左右,也是交换位置** ![这里写图片描述][format_png 3] 把最上面的和最下面的交换位置就行,把4放到5的位置,把5放到4的右子树 ![这里写图片描述][format_png 4] **第三种右左** ![这里写图片描述][format_png 5] ![这里写图片描述][format_png 6] 把四和三交换位置,然后把3放到4的左子树 最后一个root.setParent(null),防止操作到根元素,忘记把根的父给清除了。 ![这里写图片描述][format_png 7] 上面这段代码也是判断父类的到底该左子树设置还是右子树设置。 接下来,还要考虑这种: ![这里写图片描述][format_png 8] 左边是第一次按照上面那样插入,留下的病根,右边左转一次的情况,这里还有右转,直到达到预期效 下面代码弄了好多次都不型,只能这样了,作用是判断左右的深度差师傅大于1. private void leftAndRightBalance(Node<T> opRoot) { int left = treeDepth(opRoot.getLeft()) ; int right = treeDepth(opRoot.getRight()) ; if(left - right > 1){ rightxuanzhuan(opRoot); return ; } if(right - left > 1){ leftxuanzhuan(opRoot); return ; } 底下是右旋转旋转一次 // 这里是左旋转的 private void rightxuanzhuan(Node<T> opRoot) { Node<T> parent = opRoot.getParent(); Node<T> left = opRoot.getLeft(); Node<T> right = opRoot.getRight(); Node<T> rightLeft = findLeft(right); if(rightLeft.getT().compareTo(right.getT()) == 0){ rightLeft = null ; } newxuanzhuan(rightLeft); left.setParent(parent); if(parent != null){ parent.setLeft(left); }else { root = left ; left.setParent(null); } if(rightLeft != null){ rightLeft.setLeft(left.getLeft()); } if(left.getLeft()!=null){ left.getLeft().setParent(rightLeft); } }else{ opRoot.setLeft(left.getRight()); if(left.getRight() != null){ left.getRight().setParent(opRoot); } left.setRight(opRoot); zaipanduan(left) } 左旋转一次 private void leftxuanzhuan(Node<T> opRoot) { Node<T> parent = opRoot.getParent(); Node<T> right = opRoot.getRight(); Node<T> rightleft = findLeft(right); newxuanzhuan(rightleft); right.setParent(parent); if(parent != null){ parent.setRight(right); }else{ root = right; } if(rightleft != null){ rightleft.setLeft(opRoot); opRoot.setParent(rightleft); }else{ right.setLeft(opRoot); opRoot.setParent(right); } opRoot.setRight(null); zaipanduan(right); } // 为上面这两个类提供的旋转 private void newxuanzhuan(Node<T> rightleft) { if(rightleft == null){ return ; } Node<T> parent = rightleft.getParent(); if(parent == null || parent.getRight() != null){ return ; } rightleft.setParent(parent.getParent()); if(parent.getParent().getLeft() != null && parent.getParent().getLeft().getT().compareTo(parent.getT()) == 0){ parent.getParent().setLeft(parent.getLeft()); }else{ parent.getParent().setRight(parent.getLeft()); } rightleft.setRight(parent); parent.setParent(rightleft); parent.setLeft(null); } 作用是为上面两个方法提供旋转 下面这个是再进去,判断是否合理 private void zaipanduan(Node<T> left) { if(left != null && left.getLeft() != null){ zaipanduan(left.getLeft()); } if(left !=null && left.getRight() != null){ zaipanduan(left.getRight()); } zaipanduandigui(left); } private void zaipanduandigui(Node<T> left){ xuanzhuanshu(left); } 接下来给你们源码看,在这我建议你一步一步来,每一种你考虑考虑,然后把代码进一步优化 public void insert(T t) { if (root.getT() == null) { root.setT(t); size++; return; } opRoot = root; Node<T> node = new Node<T>(); node.setT(t); insert(opRoot, node); size++; } private void insert(Node<T> opRoot, Node<T> node) { if (opRoot.getT().compareTo(node.getT()) > 0) { if (opRoot.getLeft() != null) { insert(opRoot.getLeft(), node); } else { opRoot.setLeft(node); node.setParent(opRoot); xuanzhuanshu(node); } } if (opRoot.getT().compareTo(node.getT()) < 0) { if (opRoot.getRight() != null) { insert(opRoot.getRight(), node); } else { opRoot.setRight(node); node.setParent(opRoot); xuanzhuanshu(node); } } } /* * 添加的时候有四种判断方式。 第一种是左左 第二种是右右 第三种是左右 第四种是右左 */ private void xuanzhuanshu(Node<T> node) { Node<T> parent = null; // 判断,是否右父父(爷爷元素) if (node.getParent() != null && node.getParent().getParent() != null) parent = node.getParent().getParent(); if (parent == null) { return; } // 连续左左为空,右右有元素 if (parent.getLeft() == null && node.getParent().getLeft() == null) { if (parent.getParent() != null) { leftOrRight(parent.getParent(), node.getParent()); node.getParent().setParent(parent.getParent()); node.getParent().setLeft(parent); } else { node.getParent().setLeft(parent); root = node.getParent(); } parent.setParent(node.getParent()); parent.setRight(null); } // 连续左左有元素,右右为空 if (parent.getRight() == null && node.getParent().getRight() == null) { if (parent.getParent() != null) { leftOrRight(parent.getParent(), node.getParent()); node.getParent().setParent(parent.getParent()); node.getParent().setRight(parent); } else { node.getParent().setRight(parent); root = node.getParent(); } parent.setParent(node.getParent()); parent.setLeft(null); } // 下面是右空,然后在左空 if (parent.getRight() == null && node.getParent().getLeft() == null) { if (parent.getParent() != null) { leftOrRightNoOnOne(parent.getParent(), node); node.setParent(parent.getParent()); node.setLeft(parent.getLeft()); parent.getLeft().setParent(node); parent.getLeft().setRight(null); node.setRight(parent); parent.setParent(node); parent.setLeft(null); } else { root = node; node.setRight(parent); parent.setParent(node); parent.setLeft(null); node.setLeft(node.getParent()); node.getParent().setParent(node); node.getParent().setRight(null); } } // 左空,右空 if (parent.getLeft() == null && node.getParent().getRight() == null) { if (parent.getParent() != null) { leftOrRightNoOnOne(parent.getParent(), node); node.setParent(parent.getParent()); node.setRight(parent.getRight()); parent.getRight().setParent(node); parent.getRight().setLeft(null); node.setLeft(parent); parent.setParent(node); parent.setRight(null); } else { root = node; node.setLeft(parent); parent.setParent(node); parent.setRight(null); node.setRight(node.getParent()); node.getParent().setParent(node); node.getParent().setLeft(null); } } root.setParent(null); opRoot = root ; leftAndRightBalance(opRoot); } // 这个是用来检查左右方法平衡不平衡,两边的深度差是否小于等于1,如果大于1了,根据方向旋转; private void leftAndRightBalance(Node<T> opRoot) { int left = treeDepth(opRoot.getLeft()) ; int right = treeDepth(opRoot.getRight()) ; if(left - right > 1){ rightxuanzhuan(opRoot); return ; } if(right - left > 1){ leftxuanzhuan(opRoot); return ; } } // 这里是左旋转的 private void rightxuanzhuan(Node<T> opRoot) { Node<T> parent = opRoot.getParent(); Node<T> left = opRoot.getLeft(); Node<T> right = opRoot.getRight(); Node<T> rightLeft = findLeft(right); if(rightLeft.getT().compareTo(right.getT()) == 0){ rightLeft = null ; } newxuanzhuan(rightLeft); left.setParent(parent); if(parent != null){ parent.setLeft(left); }else { root = left ; left.setParent(null); } if(rightLeft != null){ rightLeft.setLeft(left.getLeft()); if(left.getLeft()!=null){ left.getLeft().setParent(rightLeft); } }else{ opRoot.setLeft(left.getRight()); if(left.getRight() != null){ left.getRight().setParent(opRoot); } } left.setRight(opRoot); zaipanduan(left); } private void zaipanduan(Node<T> left) { if(left != null && left.getLeft() != null){ zaipanduan(left.getLeft()); } if(left !=null && left.getRight() != null){ zaipanduan(left.getRight()); } zaipanduandigui(left); } private void zaipanduandigui(Node<T> left){ xuanzhuanshu(left); } private void leftxuanzhuan(Node<T> opRoot) { Node<T> parent = opRoot.getParent(); Node<T> right = opRoot.getRight(); Node<T> rightleft = findLeft(right); newxuanzhuan(rightleft); right.setParent(parent); if(parent != null){ parent.setRight(right); }else{ root = right; } if(rightleft != null){ rightleft.setLeft(opRoot); opRoot.setParent(rightleft); }else{ right.setLeft(opRoot); opRoot.setParent(right); } opRoot.setRight(null); zaipanduan(right); } // 为上面这两个类提供的旋转 private void newxuanzhuan(Node<T> rightleft) { if(rightleft == null){ return ; } Node<T> parent = rightleft.getParent(); if(parent == null || parent.getRight() != null){ return ; } rightleft.setParent(parent.getParent()); if(parent.getParent().getLeft() != null && parent.getParent().getLeft().getT().compareTo(parent.getT()) == 0){ parent.getParent().setLeft(parent.getLeft()); }else{ parent.getParent().setRight(parent.getLeft()); } rightleft.setRight(parent); parent.setParent(rightleft); parent.setLeft(null); } // 这个用于处理,不是连续的 private void leftOrRightNoOnOne(Node<T> parent, Node<T> son) { if (parent.getLeft().getT().compareTo(son.getParent().getParent().getT()) == 0) { parent.setLeft(son); } else { parent.setRight(son); } } // 处理连续的 private void leftOrRight(Node<T> parent, Node<T> son) { if (parent.getLeft() != null && parent.getLeft().getT() .compareTo(son.getParent().getT()) == 0) { parent.setLeft(son); } else { parent.setRight(son); } } # 如何觉得能帮助你,麻烦给作者一份信任,让作者有一个写下去的理由,不需要你给的太多,只需1块钱即可。 # ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70] 支付宝 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70 1] 微信 # 如果你是一个新手或者是你已经工作多年,想修改简历或者想内推互联网公司(如:百度、滴滴、小米等公司),均可以帮你内推;如果想修改简历,了解更多知识;下面是作者微信(备注csdn)。 # ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70 2] [format_png]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcxMTE1MjMzNjU3OTE2?x-oss-process=image/format,png [format_png 1]: https://imgconvert.csdnimg.cn/aHR0cDovL2ltZy5ibG9nLmNzZG4ubmV0LzIwMTcxMTE1MjM0NTE2OTc3?x-oss-process=image/format,png [format_png 2]: /images/20210920/2a6f205ce9524033a7dfe0397fecd86f.png [format_png 3]: /images/20210920/8cbdc9065d504f8ca122ec57ad302e6a.png [format_png 4]: /images/20210920/b9c9800a31984733a948d924227a433a.png [format_png 5]: /images/20210920/445c668e108c4df78aaeb7e164618bef.png [format_png 6]: /images/20210920/00f02783355e4adb9784971c68dec5f0.png [format_png 7]: /images/20210920/92bc722209d54c628ac51bd84b08eedb.png [format_png 8]: /images/20210920/a9224761d70844339e88433179ccdc21.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70]: /images/20210920/5c3d28d372854d1f934a1135db691ba5.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70 1]: /images/20210920/ed042c5319534b879d1a33bcb123dd11.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWJhaTkwNg_size_16_color_FFFFFF_t_70 2]: /images/20210920/d5f9bfe50fa740bab5fb4a6570d559fc.png
相关 平衡二叉树 <table style="width:1615px; margin-bottom:20px; background-color:transparent"> <tbody> 淡淡的烟草味﹌/ 2022年06月02日 07:59/ 0 赞/ 203 阅读
相关 平衡二叉树 平衡二叉树(Balanced Binary Tree)是二叉查找树的一个进化体,也是第一个引入平衡概念的二叉树。1962年,G.M. Adelson-Velsky 和 E.M. 墨蓝/ 2022年05月28日 08:57/ 0 赞/ 370 阅读
相关 平衡二叉树 请要相信我,30分钟让你掌握AVL树(平衡二叉树) 前言:本文不适合 给一组数据15分钟就能实现AVL的插入和删除操作的大牛(也 爱被打了一巴掌/ 2022年05月19日 04:21/ 0 赞/ 223 阅读
相关 平衡二叉树 写在前面 > 剑指offer:平衡二叉树 题目要求 > 输入一棵二叉树,判断该二叉树是否是平衡二叉树。平衡二叉树要求任意一个节点的左右字数之间的高度差不超过1。 浅浅的花香味﹌/ 2022年05月17日 01:54/ 0 赞/ 241 阅读
相关 平衡二叉树 平衡二叉树又称AVL树。它或者是颗空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树节点的平衡因子BF定 骑猪看日落/ 2022年05月17日 01:24/ 0 赞/ 219 阅读
相关 平衡二叉树 时间限制:1秒 空间限制:32768K 热度指数:160212 [ 算法知识视频讲解][Link 1] 题目描述 输入一棵二叉树,判断该二叉树是否是平衡二叉树。 向右看齐/ 2022年03月08日 01:44/ 0 赞/ 264 阅读
相关 平衡二叉树 平衡二叉树介绍 是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis提出,因此一般也称作AVL树,AVL树本质还是一棵二叉查找树,只是在其基础 青旅半醒/ 2022年02月24日 07:54/ 0 赞/ 300 阅读
相关 平衡二叉树 (平衡查找树) 平衡二叉树(AVL 树) 看一个案例(说明二叉排序树可能的问题) ![1460404-20190609204205330-1398837969.png][] 上 小咪咪/ 2021年10月29日 07:24/ 0 赞/ 412 阅读
相关 平衡二叉树 package com.avl; / @Auther: 大哥的叔 @Date: 2019/8/18 06:12 @ 忘是亡心i/ 2021年10月15日 05:37/ 0 赞/ 362 阅读
相关 二叉平衡树 二叉平衡树 说起这个树,我找了整整两天的时间,刚开始考虑的不周全,然后就一直该一直该,一直加一直加。 定义: 它是一颗空疏或它的左右两个子树的高度差的绝对值不超过 Dear 丶/ 2021年09月22日 09:42/ 0 赞/ 411 阅读
还没有评论,来说两句吧...