这两天写的一个二叉平衡树

简介

• 提供了插入、删除、查询节点是否存在、获取树的size、获取迭代器的方法和一个层序遍历的方法

重点：

• 下面平衡树使用的节点中有一个balance属性，记录一个节点是否平衡，不平衡的话是左子树高还是右子树高，高多少，balance = 右子树高度减去左子树高度（可以是-1,0,1）
• 还有一个side属性，用于记录一个节点是父节点的左子节点（-1）还是右子节点（1），还是根节点（0）

下面是源代码，尽量写了清晰的注释

//E  必须要求要  有 hashCode()方法，没有的话，就会调用Object的hashCode()方法，那就大家都相等了
public class Banlance_Tree<E> implements Iterable<E> {private Node root = null;    //    整颗树的根节点private int size;            //树中的节点个数public int size() {return size;}//    内部类private class Node {private Node parent;private Node left;private Node right;private E val;private int balance;         //作为每一个节点的平衡因子(等于右子树高度减去左子树高度)，（可以是-1,0,1）private int side;      //记录当前节点是父节点的左子节点（-1）还是右子节点（1），当前节点是根节点（0）//  构造方法一private Node(E val, int balance, int side) {this.val = val;this.balance = balance;this.side = side;}//  构造方法二private Node(E val, Node parent, int balance, int side) {this.val = val;this.parent = parent;this.balance = balance;this.side = side;}@Overridepublic String toString() {String str1 = parent == null ? "null" : String.valueOf(parent.val);String str2 = left == null ? "null" : String.valueOf(left.val);String str3 = right == null ? "null" : String.valueOf(right.val);return "Node{" +"parent=" + str1 +", left=" + str2 +", right=" + str3 +", val=" + val +", balance=" + balance +", side=" + side +'}';}}//    查询节点是否存在public boolean isExit(E val) {Node node = findNode(val);return node!=null&&node.val.equals(val);      //找到node！=null只能说明两者的hashCode相等，不能说明两者是equals的}//    插入操作public boolean insert(E val) {//  如果该树为空if (root == null) {size++;root = new Node(val, 0, 0);return true;}//    找到要插入位置的父节点Node father = findFatherNode(val);//    插入节点if (val.hashCode() == father.val.hashCode()) {      //树中存在相同 val的节点，不用插入return false;}//    往下就是一定会插入，那么先使 size 自增size++;if (val.hashCode() > father.val.hashCode()) {        //作为右子节点插入father.right = new Node(val, father, 0, 1);father.balance++;} else {     //作为左子节点插入father.left = new Node(val, father, 0, -1);father.balance--;}//      处理旋转操作while (true) {int demoside;demoside = father.side;      //先记录father的side值if (father.balance == 0 || father.side == 0) break;       //说明插入节点有兄弟节点，那就不会导致树的不平衡，即不用斗鱼处理了//     让father指向插入节点的祖父节点father = father.parent;//     处理祖父节点的balanceif (demoside == -1) {             //当前节点作为父节点的左节点father.balance--;} else if (demoside == 1) {       //当前节点作为父节点的右节点     //这里的判断条件可以省略吗？father.balance++;}if (father.balance == 0) {              //这一段if else 可以搬到上面的if else 里面去break;} else if (father.balance == -2) {if (father.left.balance == -1) {      //左左情况（左子树的左子树造成了father节点的不平衡）right_roration(father);} else {left_roration(father.left);      //先对该节点的左子节点左旋right_roration(father);         //再对该节点右旋}} else if (father.balance == 2) {if (father.right.balance == 1) {left_roration(father);} else {right_roration(father.right);left_roration(father);}}}return true;}//    删除操作public boolean delete(E val) {//   找到该节点Node node = findNode(val);if (node == null) return false;      //节点没找到//往下就是要删除的节点找到了size--;//   记录被删除节点Node rem = node;//   该节点不是叶子节点//   找到要删除的叶子节点if (node.left != null) {node = node.left;while (node.right != null) {node = node.right;}} else if (node.right != null) {node = node.right;while (node.left != null) {node = node.left;}}//    用该叶子节点顶替被删除节点的位置rem.val = node.val;deleteLeaf(node);return true;}//    删除叶子节点private void deleteLeaf(Node node) {//    首先要明确，能走到这里，被删除节点node一定是不为null的，且node一定是叶子节点//    被删除节点是根节点if (node.side == 0) {root = null;return;}//    找到被删除节点的父节点Node father = node.parent;//    被节点删除if (node.side == -1) {father.left = null;father.balance++;} else {father.right = null;father.balance--;}//  处理旋转操作while (true) {if (father.balance == 0) {      //以father为根节点的树的深度减少了一次，那么继续往上找if (father.side == 0) {      //该节点为根节点break;}if (father.side == -1) {       //该节点是父节点的左子节点father = father.parent;father.balance++;} else {                       //该节点是父节点的右子节点father = father.parent;father.balance--;}continue;}if (father.balance == -1 || father.balance == 1) {  //如果balance变成了1或者-1，那么balance原来一定是0，那么由0变成1或者-1是不会改变该节点的深度的，也就不可能破会树的平衡了break;} else if (father.balance == -2) {assert father.left != null : "当前节点的balance为-2，而此时当前节点没有左子节点";      // 用一下断言，实际上是不可能出现一个节点的balance为-2，而又没有左子节点的if (father.left.balance == -1) {      //左左情况（左子树的左子树造成了father节点的不平衡）right_roration(father);         //右旋} else {left_roration(father.left);      //先对该节点的左子节点左旋right_roration(father);         //再对该节点右旋}} else if (father.balance == 2) {assert father.right != null : "当前节点的balance为-2，而此时当前节点没有右子节点";      // 用一下断言，实际上是不可能出现一个节点的balance为-2，而又没有右子节点的if (father.right.balance == 1) {left_roration(father);} else {right_roration(father.right);left_roration(father);}}}}//    查找插入节点的父节点（根据插入节点的val查找）（如果val以存在，返回值为val的节点）private Node findFatherNode(E val) {Node demo = root;Node oc = null;while (demo != null) {oc = demo;if (val.hashCode() < demo.val.hashCode()) {      //往左走demo = demo.left;} else if (val.hashCode() > demo.val.hashCode()) {      //往右走demo = demo.right;} else {break;}}return oc;}//    查找节点private Node findNode(E val) {Node fatherNode = findFatherNode(val);if (fatherNode != null && fatherNode.val.hashCode() == val.hashCode()) {return fatherNode;}return null;}//这里的①②③④⑤是表示对节点①进行旋转会影响到的点或周围的点，不是说树就长这样
/*①                  ②↙   ↘               ↙   ↘②     ③     ==>    ④     ①↙   ↘                      ↙   ↘④     ⑤                  ⑤      ③*///右旋（左左）private void right_roration(Node node) {//node 是 ①Node father = node.parent;      //记录node的父节点int side = node.side;      //记录node的sideNode demo = node.left.right;    //demo = ⑤node.left.right = node;         //②.right = ①node.left.parent = node.parent; //②.parent = ①.parentnode.parent = node.left;        //①.parent = ②node.left = demo;               //①.left = ⑤if (demo != null) {demo.parent = node;             //⑤.parent = ①demo.side = -1;}//   处理①和②的balance，①一定会由-2变为0，②一定会由-1变为0node.balance = 0;node.parent.balance = 0;//    处理①和②的sidenode.parent.side = node.side;node.side = 1;//    原来①为该子树的根节点，现在要改为②if (side == 1) {    //原根节点是原根节点父节点的右节点father.right = node.parent;} else if (side == -1) {   //原根节点是原根节点父节点的左节点father.left = node.parent;} else {             //原根节点没有父节点，那直接让node.parent作为root节点root = node.parent;}}/*①                     ③↙   ↘                  ↙   ↘②     ③     ==>       ①     ⑤↙   ↘            ↙   ↘④     ⑤         ②     ④*///左旋（右右）private void left_roration(Node node) {Node father = node.parent;int side = node.side;Node demo = node.right.left;node.right.left = node;node.right.parent = node.parent;node.parent = node.right;node.right = demo;if (demo != null) {demo.parent = node;demo.side = 1;}node.balance = 0;node.parent.balance = 0;node.parent.side = node.side;node.side = -1;if (side == 1) {father.right = node.parent;} else if (side == -1) {father.left = node.parent;} else {root = node.parent;}}//    实现迭代器//      这里迭代器按中序遍历来（反正是对比的hashCode，实际上这个中序遍历时没有什么意义的）private class InnerIterator implements Iterator<E> {private List<E> list = new ArrayList<>();private int index;private InnerIterator() {non_recursion(Banlance_Tree.this.root);}@Overridepublic boolean hasNext() {return index < list.size();}@Overridepublic E next() {if (hasNext()) return list.get(index++);return null;}@Overridepublic void remove() {index++;}private void non_recursion(Node root) {list = new ArrayList<>();Deque<Node> deque = new LinkedList<>();while (root != null || !deque.isEmpty()) {while (root != null) {deque.push(root);root = root.left;}root = deque.pop();list.add(root.val);root = root.right;}}}@Overridepublic Iterator<E> iterator() {return new InnerIterator();}//    层次遍历public void level_traverse() {ArrayList<E> oc = new ArrayList<>();Deque<Node> deque = new LinkedList<>();Node trav = root;deque.offer(trav);while (!deque.isEmpty()) {trav = deque.poll();if (trav == null) continue;oc.add(trav.val);deque.offer(trav.left);deque.offer(trav.right);}System.out.println(oc);}}