数据结构平衡二叉树的操作演示,生成平衡二叉树例题

　　00-1010定义节点结构搜索算法插入算法LL类型RR类型LR类型RL类型插入方法删除算法概述示例分析代码完整代码

定义

　　Key:关键字的值

　　值：关键字的存储信息

　　Height:树的高度(只有一个节点的树的高度为1)

　　Left:左子树的根节点的引用。

　　Right:右子树根节点的引用。

　　AVLNodeK类扩展了ComparableK，V { public K key公V值；公共int高度；公共AVLNodeK，V左；公共AVLNodeK，V右；public AVLNode(K key，V value，int height){ this . key=key；this.value=valuethis.height=高度；}}

　　二叉查找树00-1010搜索算法：Java数据结构二叉查找树的实现

结点结构

AVL树是二叉查找树，可以用二叉查找树插入法插入节点，但是插入新节点可能会破坏AVL树的平衡。

　　如果出现这种情况，需要在插入节点后调整平衡树，以恢复平衡的性质。实现这种调整的操作称为“旋转”。

　　插入一个新节点X后，要调整不平衡最小子树，即从插入点到根找到第一个不平衡节点A。

　　平衡因子:此节点的左子树高度和右子树高度之差。如果差值的绝对值小于或等于1，说明该节点是平衡的；如果差值的绝对值为2(不会出现其他情况)，说明该节点不平衡，需要平衡。

　　节点A不平衡的原因及调整方法如下。

　　00-1010A节点的平衡因子为2，说明该节点是最小的不平衡节点，需要调整A节点。问题发生在节点A的左子节点的左子节点，所以是LL型。

　　扁担原理:惯用右手

　　将A的左子B提升到新的根节点；将原来的根节点A缩减为B的右子节点；子树按大小连接(BL和AR不变，BR调整到A的左子树)。高度调整：由于调整后的B的高度取决于A的高度，所以先更新A的高度，再更新B的高度。private AVLNodeK，V rightRotate(AVLNodeK，V a) { AVLNodeK，V b=a . left；a .左=b .右；b . right=a；a . height=math . max(getHeight(a . left)，getHeight(a . right))1；b . height=math . max(get height(b . left)，get height(b . left))1；返回b；}

　　00-1010A节点的平衡因子为2，说明该节点是最小的不平衡节点，需要调整A节点。要求

　　题发生在 A 结点右子结点的右子结点，所以为 RR 型。

　　扁担原理：左旋

　　将 A 的右孩子 B 提升为新的根结点；将原来的根结点 A 降为 B 的左孩子；各子树按大小关系连接(AL 和 BR 不变，BL 调整为 A 的右子树)。高度调整：由于调整后 B 的高度依赖于 A 的高度，所以先更新 A 的高度，再更新 B 的高度。

 private AVLNode<K, V> leftRotate(AVLNode<K, V> a) { AVLNode<K, V> b = a.right; a.right = b.left; b.left = a; a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1; b.height = Math.max(getHeight(b.left), getHeight(b.left)) + 1; return b; }

LR 型

A 结点的平衡因子为2，说明该结点是最小不平衡结点，需要对 A 结点进行调整。问题发生在 A 结点左子结点的右子结点，所以为 LR 型。

　　从旋转的角度：对 B 左旋，然后对 A 右旋将 B 的左孩子 C 提升为新的根结点；将原来的根结点 A 降为 C 的右孩子；各子树按大小关系连接(BL 和 AR 不变，CL 和 CR 分别调整为 B 的右子树和 A 的左子树)。

 private AVLNode<K, V> leftRightRotate(AVLNode<K, V> a) { a.left = leftRotate(a.left); // 对 B 左旋 return rightRotate(a); // 对 A 右旋 }

RL 型

A 结点的平衡因子为2，说明该结点是最小不平衡结点，需要对 A 结点进行调整。问题发生在 A 结点右子结点的左子结点，所以为 RL 型。

　　从旋转的角度：对 B 右旋，然后对 A 左旋将 B 的左孩子 C 提升为新的根结点；将原来的根结点 A 降为 C 的左孩子；各子树按大小关系连接(AL 和 BR 不变，CL 和 CR 分别调整为 A 的右子树和 B 的左子树)。

 private AVLNode<K, V> rightLeftRotate(AVLNode<K, V> a) { a.right = rightRotate(a.right); return leftRotate(a); }

插入方法

根结点默认高度为1

　　某结点的左右子树高度差的绝对值为2，则需要进行平衡处理

　　I.左子树高

　　key小于root.left.key：LL型，进行右旋

　　key大于root.left.key：LR型，进行左右旋

　　II.右子树高

　　key大于root.right.key：RR型，进行左旋

　　key小于root.right.key：RR型，进行右左旋

 public void insert(K key, V value) { root = insert(root, key, value); } private AVLNode<K, V> insert(AVLNode<K, V> t, K key, V value) { if (t == null) { return new AVLNode<>(key, value, 1); } else if (key.compareTo(t.key) < 0) { t.left = insert(t.left, key, value); t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1; // 平衡因子判断 if (getHeight(t.left) - getHeight(t.right) == 2) { if (key.compareTo(root.left.key) < 0) // 左左：右旋 t = rightRotate(t); else // 左右：先左旋，再右旋 t = leftRightRotate(t); } } else if (key.compareTo(t.key) > 0) { t.right = insert(t.right, key, value); t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1; // 平衡因子判断 if (getHeight(t.left) - getHeight(t.right) == -2) { if (key.compareTo(root.right.key) > 0) // 右右：左旋 t = leftRotate(t); else // 右左：先右旋，再左旋 t = rightLeftRotate(t); } } else { t.value = value; } return t; }

删除算法

概述

可采用二叉查找树的删除算法进行删除。Java数据结构之二叉查找树的实现删除某结点 X 后，沿从 X 到根节点的路径上考察沿途结点的平衡系数，若第一个不平衡点为 A，平衡以 A 为根的子树。平衡后，可能使子树 A 高度变小。这样可能导致 A 的父节点不满足平衡性。所以要继续向上考察结点的平衡性，最远可能至根结点，即最多需要做O(logn)次旋转。对比插入操作：平衡 A 后，子树高度不变，A 子树以外的结点不受影响，即插入最多涉及O(1)次旋转。

实例分析

下面举个删除的例子：

　　删除以下平衡二叉树中的 16 结点

　　16 为叶子，将其删除即可，如下图。

　　指针 g 指向实际被删除节点 16 之父 25，检查是否失衡，25 节点失衡，用 g 、u 、v 记录失衡三代节点（从失衡节点沿着高度大的子树向下找三代），判断为 RL 型，进行 RL 旋转调整平衡，如下图所示。

　　继续向上检查，指针 g 指向 g 的双亲 69，检查是否失衡，69 节点失衡，用 g 、u 、v 记录失衡三代节点，判断为 RR 型，进行 RR 旋转调整平衡，如下图所示。

代码

代码描述：

　　1.若当前结点为空，则返回该节点

　　2.若关键值小于当前结点的关键值，则递归处理该结点的左子树

　　3.若关键值大于当前结点的关键值，则递归处理该结点的右子树

　　4.若关键值等于当前结点的关键值

　　若当前结点的左子树为空，则返回该结点的右子树根节点若当前结点的右子树为空，则返回该结点的左子树根节点若当前结点左右子树都不为空，则找到该结点的中序前驱结点（该结点左子树的最右结点）或中序后继结点（该结点右子树的最左结点），将其值赋予该结点，然后递归删除中序前驱或后继结点。5.更新结点高度

　　6.若该结点左子树高度更高，且处于不平衡状态

　　若为 LL 型，进行右旋若为 LR 型，先左旋，再右旋7.若该结点右子树高度更高，且处于不平衡状态

　　若为 RL 型，先右旋，再左旋若我 RR 型，进行左旋8.返回该结点

 public void remove(K key) { this.root = delete(root, key); } public AVLNode<K, V> delete(AVLNode<K, V> t, K key) { if (t == null) return t; if (key.compareTo(t.key) < 0) { t.left = delete(t.left, key); } else if (key.compareTo(t.key) > 0) { t.right = delete(t.right, key); } else { if(t.left == null) return t.right; else if(t.right == null) return t.left; else { // t.left != null && t.right != null AVLNode<K, V> pre = t.left; while (pre.right != null) { pre = pre.right; } t.key = pre.key; t.value = pre.value; t.left = delete(t.left, t.key); } } if (t == null) return t; t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1; if(getHeight(t.left) - getHeight(t.right) >= 2) { if(getHeight(t.left.left) > getHeight(t.left.right)) { return rightRotate(t); } else { return leftRightRotate(t); } } else if(getHeight(t.left) - getHeight(t.right) <= -2) { if(getHeight(t.right.left) > getHeight(t.right.right)) { return rightLeftRotate(t); } else { return leftRotate(t); } } return t; }

完整代码

class AVLNode<K extends Comparable<K>, V> { public K key; public V value; public int height; public AVLNode<K, V> left; public AVLNode<K, V> right; public AVLNode(K key, V value, int height) { this.key = key; this.value = value; this.height = height; }}class AVLTree<K extends Comparable<K>, V> { public AVLNode<K, V> root; public int getHeight(AVLNode<K, V> t) { return t == null ? 0 : t.height; } public void insert(K key, V value) { root = insert(root, key, value); } public void remove(K key) { this.root = delete(root, key); } public AVLNode<K, V> delete(AVLNode<K, V> t, K key) { if (t == null) return t; if (key.compareTo(t.key) < 0) { t.left = delete(t.left, key); } else if (key.compareTo(t.key) > 0) { t.right = delete(t.right, key); } else { if(t.left == null) return t.right; else if(t.right == null) return t.left; else { // t.left != null && t.right != null AVLNode<K, V> pre = t.left; while (pre.right != null) { pre = pre.right; } t.key = pre.key; t.value = pre.value; t.left = delete(t.left, t.key); } } if (t == null) return t; t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1; if(getHeight(t.left) - getHeight(t.right) >= 2) { if(getHeight(t.left.left) > getHeight(t.left.right)) { return rightRotate(t); } else { return leftRightRotate(t); } } else if(getHeight(t.left) - getHeight(t.right) <= -2) { if(getHeight(t.right.left) > getHeight(t.right.right)) { return rightLeftRotate(t); } else { return leftRotate(t); } } return t; } private AVLNode<K, V> insert(AVLNode<K, V> t, K key, V value) { if (t == null) { return new AVLNode<>(key, value, 1); } if (key.compareTo(t.key) < 0) { t.left = insert(t.left, key, value); // 平衡因子判断 if (getHeight(t.left) - getHeight(t.right) == 2) { if (key.compareTo(t.left.key) < 0) // 左左：右旋 t = rightRotate(t); else // 左右：先左旋，再右旋 t = leftRightRotate(t); } } else if (key.compareTo(t.key) > 0) { t.right = insert(t.right, key, value); // 平衡因子判断 if (getHeight(t.left) - getHeight(t.right) == -2) { if (key.compareTo(t.right.key) > 0) // 右右：左旋 t = leftRotate(t); else // 右左：先右旋，再左旋 t = rightLeftRotate(t); } } else { t.value = value; } t.height = Math.max(getHeight(t.left), getHeight(t.right)) + 1; return t; } private AVLNode<K, V> rightLeftRotate(AVLNode<K, V> a) { a.right = rightRotate(a.right); return leftRotate(a); } private AVLNode<K, V> leftRightRotate(AVLNode<K, V> a) { a.left = leftRotate(a.left); return rightRotate(a); } private AVLNode<K, V> leftRotate(AVLNode<K, V> a) { AVLNode<K, V> b = a.right; a.right = b.left; b.left = a; a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1; b.height = Math.max(getHeight(b.left), getHeight(b.right)) + 1; return b; } private AVLNode<K, V> rightRotate(AVLNode<K, V> a) { AVLNode<K, V> b = a.left; a.left = b.right; b.right = a; a.height = Math.max(getHeight(a.left), getHeight(a.right)) + 1; b.height = Math.max(getHeight(b.left), getHeight(b.right)) + 1; return b; } private void inorder(AVLNode<K, V> root) { if (root != null) { inorder(root.left); System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") "); inorder(root.right); } } private void preorder(AVLNode<K, V> root) { if (root != null) { System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") "); preorder(root.left); preorder(root.right); } } private void postorder(AVLNode<K, V> root) { if (root != null) { postorder(root.left); postorder(root.right); System.out.print("(key: " + root.key + " , value: " + root.value + " , height: " + root.height + ") "); } } public void postorderTraverse() { System.out.print("后序遍历："); postorder(root); System.out.println(); } public void preorderTraverse() { System.out.print("先序遍历："); preorder(root); System.out.println(); } public void inorderTraverse() { System.out.print("中序遍历："); inorder(root); System.out.println(); }}

方法测试

 public static void main(String[] args) { AVLTree<Integer, Integer> tree = new AVLTree<>(); tree.insert(69, 1); tree.insert(25, 1); tree.insert(80, 1); tree.insert(16, 1); tree.insert(56, 1); tree.insert(75, 1); tree.insert(90, 1); tree.insert(30, 1); tree.insert(78, 1); tree.insert(85, 1); tree.insert(98, 1); tree.insert(82, 1); tree.remove(16); tree.preorderTraverse(); tree.inorderTraverse(); tree.postorderTraverse(); }

输出

先序遍历：(key: 80 , value: 1 , height: 4) (key: 69 , value: 1 , height: 3) (key: 30 , value: 1 , height: 2) (key: 25 , value: 1 , height: 1) (key: 56 , value: 1 , height: 1) (key: 75 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 90 , value: 1 , height: 3) (key: 85 , value: 1 , height: 2) (key: 82 , value: 1 , height: 1) (key: 98 , value: 1 , height: 1)中序遍历：(key: 25 , value: 1 , height: 1) (key: 30 , value: 1 , height: 2) (key: 56 , value: 1 , height: 1) (key: 69 , value: 1 , height: 3) (key: 75 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 80 , value: 1 , height: 4) (key: 82 , value: 1 , height: 1) (key: 85 , value: 1 , height: 2) (key: 90 , value: 1 , height: 3) (key: 98 , value: 1 , height: 1)后序遍历：(key: 25 , value: 1 , height: 1) (key: 56 , value: 1 , height: 1) (key: 30 , value: 1 , height: 2) (key: 78 , value: 1 , height: 1) (key: 75 , value: 1 , height: 2) (key: 69 , value: 1 , height: 3) (key: 82 , value: 1 , height: 1) (key: 85 , value: 1 , height: 2) (key: 98 , value: 1 , height: 1) (key: 90 , value: 1 , height: 3) (key: 80 , value: 1 , height: 4)

　　

以上就是Java数据结构之平衡二叉树的实现详解的详细内容，更多关于Java平衡二叉树的资料请关注盛行IT其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。