做视频网站怎么赚钱的,网站的首页设计方案,天水做网站,广告平台对接前言
在关键字排列随机的情况下#xff0c;二叉排序树的平均查找长度和 l o g n log n logn是等数量级的。在某些情况下#xff0c;尚需在构成二叉排序树的过程中进行“平衡化”处理#xff0c;使其成为平衡二叉树。 如果任何初始化序列构成的二叉排序树都是平衡二叉树二叉排序树的平均查找长度和 l o g n log n logn是等数量级的。在某些情况下尚需在构成二叉排序树的过程中进行“平衡化”处理使其成为平衡二叉树。 如果任何初始化序列构成的二叉排序树都是平衡二叉树因为平衡二叉树上任何结点的左右子树的深度之差都不超过1则可以证明它的深度和 l o g n log n logn是同数量级别的(其中n为结点个数)。由此它的平均查找长度也和 l o g n log n logn同数量级。
平衡二叉树定义及性质
平衡二叉树(Balanced Binary Tree 或 Height-Balanced Tree)又称AVL树。它或者是一棵空树或者是具有下列性质的二叉树 (1) 它的左子树和右子树都是平衡二叉树 (2) 它的左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子定位为该结点的左子树的深度减去它的右子树的深度则平衡二叉树上所有节点的平衡因子只可能是-1、0和1。
平衡二叉排序树的插入操作
一般情况下假设由于在二叉排序树上插入结点而失去平衡的最小树根结点的指针为a(即a是离插入结点最近且平衡因子绝对值超过1的祖先节点)则失去平衡后进行调整的规律可归纳为下列4种情况 (1) 单向右旋平衡处理由于在*a的左子树根结点的左子树上插入结点*a的平衡因子由1增至2致使以*a为根的子树失去平衡则需再进行一次向右的顺时针旋转操作。如下图所示
(2) 单向左旋平衡处理由于在*a的右子树根结点的右子树上插入结点*a的平衡因子由-1增至-2致使以*a为根的子树失去平衡则需再进行一次向左的逆时针旋转操作。如下图所示
(3) 双向旋转(先左后右)平衡处理由于在*a的左子树根结点的右子树上插入结点*a的平衡因子由1增至2致使以*a为根结点的子树失去平衡则需进行两次旋转(先左旋后右旋)操作。如下图所示
(4) 双向旋转(先右后左)平衡处理由于在*a的右子树根结点的左子树上插入结点*a的平衡因子由-1增至-2致使以*a为根结点的子树失去平衡则需进行两次旋转(先右旋后左旋)操作。如下图所示
上述4中情况(1)和(2)对称(3)和(4)对称。旋转操作的正确性容易由保持二叉排序树的特性中序遍历所得关键字序列由小至大有序证明。当平衡的二叉排序树因插入结点而失去平衡时仅需对最小不平衡子树进行旋转即可。因为经过旋转处理之后的子树深度和插入之前相同因而不影响插入路径上所有祖先结点的平衡度。 在平衡的二叉排序树BBST上插入一个新的数据元素e的递归算法可描述如下 (1) 若BBST为空树则插入一个数据元素为e的新结点作为BBST的根结点树的深度加1。 (2) 若e的关键字和BBST的根结点的关键字相等则不进行插入。 (3) 若e的关键字小于BBST的根结点的关键字而且在BBST的左子树中不存在和e有相同关键字的结点则将e插入在BBST的左子树上并且当插入之后的左子树深度1时分别就下列不同情况处理之 (a) BBST的根结点的平衡因子为-1(右子树的深度大于左子树的深度)则将根结点的平衡因子更改为0BBST的深度不变 (b) BBST的根结点的平衡因子为0(左子树和右子树的深度相等)则将根结点的平衡因子更改为1BBST的深度1 © BBST的根结点的平衡因子为1(左子树的深度大于右子树的深度若BBST的左子树根结点的平衡因子为1则需进行单向右旋平衡处理并且在右旋后将根结点和其右子树根结点的平衡因子更改为0树的深度不变若BBST的左子树根结点的平衡因子为-1则需进行先向左、后向右的双向旋转平衡处理并且在旋转处理之后修改根结点和其左子树、右子树根结点的平衡因子树的深度不变 (4) 若e的关键字大于BBST的根结点的关键字而且在BBST的右子树不存在于e有相同关键字的结点则将e插入在BBST的右子树上并且当插入之后的右子树深度1时分别就不同的情况处理之。其处理操作和步骤3中所述相对称这里不展开说明。 由于平衡二叉排序树的插入代码实现较复杂有兴趣的同学可以自行参考**《数据结构》的9.2.1 二叉排序树和平衡二叉树小节**学习。
平衡二叉排序树的创建
将二叉排序树转换成平衡树
public TreeNode balanceBST(TreeNode root) {ListInteger sortedList new ArrayList();traverseByInorder(root, sortedList);return createTree(sortedList, 0, sortedList.size()-1);
}private void traverseByInorder(TreeNode root, ListInteger sortedList) {if(root null) {return;}traverseByInorder(root.left, sortedList);sortedList.add(root.val);traverseByInorder(root.right, sortedList);
}private TreeNode createTree(ListInteger sortedList, int left, int right) {int mid (left right) 1;TreeNode root new TreeNode(sortedList.get(mid));if(left mid -1) {root.left createTree(sortedList, left, mid -1);}if(right mid1) {root.right createTree(sortedList, mid1, right);}return root;
}将有序数组转换平衡二叉排序树
public TreeNode sortedArrayToBST(int[] nums) {return createTree(nums, 0, nums.length - 1);
}private TreeNode createTree(int[] nums, int left, int right) {if(nums.length 0) {return null;}int mid (left right) 1;TreeNode root new TreeNode(nums[mid]);if(left mid -1) {root.left createTree(nums, left, mid - 1);}if(right mid 1) {root.right createTree(nums, mid 1, right);}return root;
}将有序链表转换成平衡二叉排序树
public TreeNode sortedListToBST(ListNode head) {return createTree(head, null);
}private TreeNode createTree(ListNode leftNode, ListNode rightNode) {if(leftNode rightNode) {return null;}ListNode middleNode getMiddleNode(leftNode, rightNode);TreeNode root new TreeNode(middleNode.val);root.left createTree(leftNode, middleNode);root.right createTree(middleNode.next, rightNode);return root;
}private ListNode getMiddleNode(ListNode left, ListNode right) {ListNode fast left;ListNode slow left;while (fast ! right fast.next ! right) {fast fast.next.next;slow slow.next;}return slow;
}判断一棵树是否是平衡二叉树
判断一棵树是不是平衡二叉树就是判断这棵树是否满足平衡二叉树的性质 (1) 它的左子树和右子树都是平衡二叉树 (2) 它的左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子定位为该结点的左子树的深度减去它的右子树的深度则平衡二叉树上所有节点的平衡因子只可能是-1、0和1。
public boolean isBalanced(TreeNode root) {if(root null) {return true;}return Math.abs(height(root.left) - height(root.right))1 isBalanced(root.left) isBalanced(root.right);
}private int height(TreeNode root) {if(root null) {return 0;}return Math.max(height(root.left), height(root.right)) 1;
}public boolean isBalanced(TreeNode root) {return height(root) 0;
}
private int height(TreeNode root) {if(root null) {return 0;}int leftHeight height(root.left);int rightHeight height(root.right);if(leftHeight -1 || rightHeight -1 || Math.abs(leftHeight - rightHeight) 1) {return -1;}return Math.max(leftHeight, rightHeight) 1;
}参考
《数据结构》 严蔚敏 吴伟民 著 9.2.1 二叉排序树和平衡二叉树 https://zhuanlan.zhihu.com/p/163515903 平衡二叉树专题 https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/ 108. 将有序数组转换为高度平衡的二叉搜索树 https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/ 109. 有序链表转换为高度平衡的二叉搜索树 https://leetcode.cn/problems/balanced-binary-tree/ 110. 平衡二叉树 https://leetcode.cn/problems/balance-a-binary-search-tree/description/ 1382. 将二叉搜索树变平衡的二叉搜索树
