精华内容
下载资源
问答
  • 有序队列类似于中序遍历,又是平衡二叉树,考虑左右子树节点个数一致,所以如果是奇数个值,那根节点就在中间位置,否则根节点可以在中间偏前个或者后个,取1/2位置,代码如下所示: ​ /** * Definition for...

    有序队列类似于中序遍历,又是平衡二叉树,考虑左右子树节点个数一致,所以如果是奇数个值,那根节点就在中间位置,否则根节点可以在中间偏前一个或者后一个,取1/2位置,代码如下所示:

    ​
    /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func sortedArrayToBST(nums []int) *TreeNode {
    	return createBst(nums, 0, len(nums)-1)
    }
    
    func createBst(nums []int, left,right int)*TreeNode{
    	if left > right{
    		return nil
    	}
    	mid := (left+right)/2
    	root := &TreeNode{Val: nums[mid]}
    	root.Left = createBst(nums, left, mid-1)
    	root.Right = createBst(nums, mid+1, right)
    	return root
    }
    
    ​

    展开全文
  • """FUN1 由无序数组创建平衡二叉树 """ """FUN2 向平衡二叉树添加节点 """ """FUN3 将二叉树恢复平衡""" """FUN4 计算每个结点的height""" """FUN5 计算每个结点的balance""" """FUN6 左旋""" """FUN7 右旋"...

    目录

    平衡二叉树的主要操作

    AVL.py

    tree.py

    github:


    平衡二叉树的主要操作

        """FUN0 初始化"""
        """FUN1 由无序数组创建平衡二叉树 """
        """FUN2 向平衡二叉树添加节点 """
        """FUN3 将二叉树恢复平衡"""
        """FUN4 计算每个结点的height"""
        """FUN5 计算每个结点的balance"""
        """FUN6 左旋"""
        """FUN7 右旋"""
        """FUN9 中序遍历平衡二叉树,并打印结果"""
        """FUN10 打印平衡二叉树图形"""
        """FUN11 将平衡二叉树转化为普通的二叉树"""

    AVL.py

    """
    平衡二叉树
    """
    from tree import *
    
    
    class AvlTree(object):
        """FUN0 初始化"""
    
        def __init__(self):
            self.node = None
            self.height = -1
            self.balance = 0
    
        """FUN1 由无序数组创建平衡二叉树 """
    
        def avl_create(self, arr):
            for i in arr:
                self.avl_insert(i)
    
        """FUN2 向平衡二叉树添加节点 """
    
        def avl_insert(self, val):
            node = TreeNode(val)
            if self.node is None:
                self.node = node
                self.node.left = AvlTree()
                self.node.right = AvlTree()
            elif val < self.node.val:
                self.node.left.avl_insert(val)
            else:
                self.node.right.avl_insert(val)
            # 调整使平衡
            self.avl_rebalance()
    
        """FUN3 将二叉树恢复平衡"""
    
        def avl_rebalance(self):
            # 计算平衡因子
            self.avl_heights(False)
            self.avl_balance(False)
    
            while self.balance < -1 or self.balance > 1:
                if self.balance < -1:  # R
                    if self.node.right.balance > 0:         # 如果是RL
                        self.node.right.avl_rotate_right()  # 对RL需要先转化成RR
                        self.avl_heights()
                        self.avl_balance()
                    self.avl_rotate_left()                  # RR
                    self.avl_heights()
                    self.avl_balance()
                if self.balance > 1:  # L
                    if self.node.left.balance < 0:          # 如果是LR
                        self.node.left.avl_rotate_left()    # 对LR需要先转换成LL
                        self.avl_heights()
                        self.avl_balance()
                    self.avl_rotate_right()                 # LL
                    self.avl_heights()
                    self.avl_balance()
    
        """FUN4 计算每个结点的height"""
    
        def avl_heights(self, recursive=True):
            if self.node is None:
                self.height = -1
            else:
                if recursive:  # 在插入结点时计算高度,由上到下计算高度; 结点调换位置时,由下到上计算高度
                    if self.node.left:
                        self.node.left.avl_heights()
                    if self.node.right:
                        self.node.right.avl_heights()
                self.height = 1 + max(self.node.left.height, self.node.right.height)
    
        """FUN5 计算每个结点的balance"""
    
        def avl_balance(self, recursive=True):
            if self.node is None:
                self.balance = 0
            else:
                if recursive:
                    if self.node.left:
                        self.node.left.avl_balance()
                    if self.node.right:
                        self.node.right.avl_balance()
                self.balance = self.node.left.height - self.node.right.height
    
        """FUN6 左旋"""
    
        def avl_rotate_left(self):
            new_root = self.node.right.node
            new_sub_left = new_root.left.node
            old_root = self.node
    
            self.node = new_root
            old_root.right.node = new_sub_left
            new_root.left.node = old_root
    
        """FUN7 右旋"""
    
        def avl_rotate_right(self):
            new_root = self.node.left.node
            new_sub_right = new_root.right.node
            old_root = self.node
    
            self.node = new_root
            old_root.left.node = new_sub_right
            new_root.right.node = old_root
    
        """FUN9 中序遍历平衡二叉树"""
    
        def avl_inorder(self):
            if self.node is None:
                return
            if self.node.left:
                self.node.left.avl_inorder()
            print("val:{}, height:{}, balance:{}".format(self.node.val, self.height, self.balance))
            if self.node.right:
                self.node.right.avl_inorder()
    
        """FUN10 打印平衡二叉树图形"""
    
        def avl_print_graph(self):
            """FUN11 将平衡二叉树转化为普通的二叉树"""
            root = self.acl2Btree()
            # 打印转化后的树
            tree_print_graph(root)
    
        """FUN11 将平衡二叉树转化为普通的二叉树"""
    
        def acl2Btree(self):
            if self.node is None:
                return
            root = TreeNode(self.node.val)
            if self.node.left:
                root.left = self.node.left.acl2Btree()
            if self.node.right:
                root.right = self.node.right.acl2Btree()
            return root
    
    
    arr = [1, 2, 3, 4, 5, 6]
    # arr = [3, 4, 2, 1, 6, 5]
    # arr = [-10, -3, 0, 5, 9]
    """FUN0 初始化"""
    avl = AvlTree()
    """FUN1 由无序数组创建平衡二叉树 """
    avl.avl_create(arr)
    """FUN9 中序遍历平衡二叉树"""
    avl.avl_inorder()
    """FUN10 打印平衡二叉树图形"""
    avl.avl_print_graph()
    
    

    tree.py

    from typing import List
    
    from pyasn1.compat.octets import null
    
    """二叉树数据结构"""
    
    
    class TreeNode:
        def __init__(self, val=-1):
            self.val = val
            self.left = None
            self.right = None
    
    
    """FUN2.3 层次遍历一棵树,以数组的形式返回遍历结果(与原树高度相同的完全二叉树,空结点-1补全), 用于绘制图形"""
    
    
    def tree_level_complete_binary_tree(root):
        if root is None:
            return
        depth = tree_depth(root)
        tree_graph = []
        queue = [root]
        while queue:
            node = queue.pop(0)
            tree_graph.append(node.val)
            if node.left:
                queue.append(node.left)
            else:
                queue.append(TreeNode())
            if node.right:
                queue.append(node.right)
            else:
                queue.append(TreeNode())
            tag = True  # 全是null
            for q in queue:
                if q.val != -1:
                    tag = False
            if tag:  # 全是null
                break
        for i in range(len(tree_graph), 2 ** depth - 1):
            tree_graph.append(-1)
        return tree_graph
    
    
    """FUN3 求一棵树的最大深度"""
    
    
    def tree_depth(root) -> int:
        return 0 if root is None else max(tree_depth(root.left), tree_depth(root.right)) + 1
    
    
    """FUN4 打印一棵二叉树图形"""
    
    
    def tree_print_graph(root):
        depth = tree_depth(root)
        tree_graph = tree_level_complete_binary_tree(root)
        # print(tree_graph)
        nodes_val = [[] for i in range(depth)]  # 记录每一层的结点
        graph = ["" for i in range(depth)]
        # 排列好结点的位置
        for i in range(depth):
            nodes_val[i] = tree_graph[2 ** i - 1: 2 ** (i + 1) - 1]
            # print(nodes_val)
            for j in range(len(nodes_val[i])):
                if nodes_val[i][j] == -1:
                    nodes_val[i][j] = " "
                graph[i] += str(nodes_val[i][j]) + (" " * (2 ** (depth - i + 1) - 1))  # 添加结点之间的间隔,最底层间隔3个“ ”
                # print(graph[i])
            graph[i] = (" " * ((2 ** (depth - i)) - 2)) + graph[i]  # 错开位置,构成树的形状,
            # print(graph[i])
        # print("###################################################################")
        for s in graph:
            print(s)

    github:

    https://github.com/YTIANYE/PractisePython/tree/master/%E5%88%9D%E7%BA%A7%E7%AE%97%E6%B3%95-%E5%B8%AE%E5%8A%A9%E5%85%A5%E9%97%A8/05%E6%A0%91

    展开全文
  • 平衡二叉树

    2020-12-19 04:33:39
    之前学习了二叉排序树,假如现有数列:1,2,3,4,5,要用这个数列创建一棵二叉排序树,结果是这样的:二叉排序树看起来就怪怪的,其实就是斜着放的单链表。这树存在以下问题:左子树全部为空,其实就是个单链表;...

    1. 为什么会出现平衡二叉树这种数据结构?

    之前学习了二叉排序树,假如现有数列:1,2,3,4,5,要用这个数列创建一棵二叉排序树,结果是这样的:

    二叉排序树

    看起来就怪怪的,其实就是斜着放的单链表。这棵树存在以下问题:

    左子树全部为空,其实就是一个单链表;

    其实查询比单链表更慢,因为在检索的时候要判断左子树是否为空,因为不能发挥二叉排序树的优势。

    为了解决上面的问题,平衡二叉树(AVL树)就应运而生了。

    2. 什么是平衡二叉树?

    平衡二叉树又叫AVL树,也叫平衡二叉搜索树,可以保证较高的查询效率;

    它是一棵空树,或者是左右子树的高度差的绝对值不会超过1,并且左右两棵子树都是一棵平衡二叉树;

    平衡二叉树常用的实现算法有红黑树,AVL,替罪羊树,Treap,伸展树等;

    3. 如何创建平衡二叉树?

    (1). 左旋转思路:

    假如现有数列:4,3,6,5,7,8,创建出来的二叉树排序数如下图:

    二叉排序树

    节点4的左子树高度为1,右子树高度为3,高度差是2,所以不是平衡二叉树。如果要将其变成平衡二叉树该怎么做呢?因为其右子树的高度更高,要分点儿给左子树,所以方法叫做左旋转。具体步骤如下:

    创建一个新节点newNode,值为根节点的值,即:Node newNode = new Node(4);

    当前节点currentNode(节点4)的左子树(节点3)作为新节点的左子树,即:newNode.left = currentNode.left;

    当前节点(节点4)的右子树(节点6)的左子树(节点5)作为新节点的右子树,即:newNode.right = currentNode.right.left;

    把当前节点(节点4)的值换成右子节点(节点6)的值,即现在二叉树的效果如下:

    二叉树

    当前节点的右子树(节点6)的右子树(节点7)作为当前节点的右子树,即:currentNode.right = currentNode.right.right,设置完后效果如下:

    二叉树

    最后一步,新节点作为当前节点的左子树,即:currentNode.left = newNode,最后效果如下:

    平衡二叉树

    (2). 右旋转:

    过程和左旋转类似,只不过是将左旋转步骤中的左右颠倒一下。

    创建新节点,值为当前根节点的值;

    当前节点的右子树作为新节点的右子树;

    当前节点左子树的右子树作为新节点的左子树;

    把当前节点的值换成左子节点的值;

    当前节点的左子树的左子树作为当前节点的左子树;

    新节点作为当前节点的右子树。

    (3). 代码实现左/右旋转:

    首先创建如下的AVL树类:

    public class AvlTree {

    // 根节点

    private Node root;

    /**

    * 给外部调用的添加节点的方法

    *

    * @param value

    */

    public void add(int value) {

    add(new Node(value));

    }

    /**

    * 添加节点

    *

    * @param node

    */

    public void add(Node node) {

    if (root == null) {

    root = node;

    } else {

    root.add(node);

    }

    }

    /**

    * 中序遍历

    */

    public void infixOrder() {

    if (root != null) {

    root.infixOrder();

    } else {

    throw new IllegalArgumentException("二叉排序树为空");

    }

    }

    /**

    * 节点类

    *

    * @author zhu

    *

    */

    class Node {

    int value;

    Node left;

    Node right;

    public Node(int value) {

    this.value = value;

    }

    /**

    * 添加节点

    *

    * @param node

    */

    public void add(Node node) {

    if (node == null) {

    return;

    }

    // 如果传入的节点值比当前节点值小

    if (node.value < this.value) {

    // 如果当前节点左边没有节点

    if (this.left == null) {

    // 就把node挂在当前节点左边

    this.left = node;

    } else {

    // 当前节点左边有节点,那就递归

    this.left.add(node);

    }

    } else { // 往右边添加

    if (this.right == null) {

    // 就把node挂在当前节点右边

    this.right = node;

    } else {

    // 当前节点右边有节点,那就递归

    this.right.add(node);

    }

    }

    }

    /**

    * 中序遍历

    */

    public void infixOrder() {

    // 往左递归

    if (this.left != null) {

    this.left.infixOrder();

    }

    // 输出当前节点

    System.out.println(this.value);

    // 向右递归

    if (this.right != null) {

    this.right.infixOrder();

    }

    }

    }

    public Node getRoot() {

    return root;

    }

    public void setRoot(Node root) {

    this.root = root;

    }

    }

    目前这棵树只有最基本的添加节点和中序遍历的方法。因为是否要进行旋转,需要根据树的高度来进行判断,所以在Node内部类中新增如下方法,用来获取树的高度:

    /**

    * 返回以当前节点为根节点的树的高度

    *

    * @return

    */

    public int height() {

    // 左右子树不为空的时候就递归,直到它为空为止,然后取左右子树中高度较大的值作为树的高度,最后加1是自身也算一个高度

    return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;

    }

    /**

    * 返回当前节点左子树的高度

    *

    * @return

    */

    public int leftHeight() {

    return left == null ? 0 : left.height();

    }

    /**

    * 返回当前节点右子树的高度

    *

    * @return

    */

    public int rightHeight() {

    return right == null ? 0 : right.height();

    }

    接下来测试一下获取树的高度的代码是否正确:

    public static void main(String[] args) {

    int[] arr = {4,3,6,5,7,8};

    // int[] arr = {10,12,8,9,7,6}; // 需要右旋转的树

    AvlTree avlTree = new AvlTree();

    for (int i=0; i

    avlTree.add(arr[i]);

    }

    System.out.printf("树的高度:%s\r\n" ,avlTree.getRoot().height());

    System.out.printf("根节点左子树的高度:%s\r\n", avlTree.getRoot().leftHeight());

    System.out.printf("根节点右子树的高度:%s\r\n", avlTree.getRoot().rightHeight());

    }

    如果正常的话,会打印出:

    树的高度:4

    根节点左子树的高度:1

    根节点右子树的高度:3

    接下来,就按照上面左/右旋转的步骤,在Node内部类中写两个方法就好了,如下:

    /**

    * 左旋转

    */

    public void leftRotate() {

    // 1. 创建新节点,值为当前节点的值

    Node newNode = new Node(value);

    // 2. 当前节点左子树作为新节点的左子树

    newNode.left = left;

    // 3. 当前节点的右子树的左子树作为新节点的右子树

    newNode.right = right.left;

    // 4. 把当前节点的值换成右子节点的值

    value = right.value;

    // 5. 当前节点的右子树的右子树作为当前节点的右子树

    right = right.right;

    // 6. 新节点作为当前节点的左子树

    left = newNode;

    }

    /**

    * 右旋转,和左旋转对称

    */

    public void rightRotate() {

    Node newNode = new Node(value);

    newNode.right = right;

    newNode.left = left.right;

    value = left.value;

    left = left.left;

    right = newNode;

    }

    写好之后怎么用呢?在Node内部类中的add方法中,每添加完一个节点,就判断一下是否需要进行左右旋转,如果需要,就调用左右旋转的方法,如下:

    public void add(Node node) {

    if (node == null) {

    return;

    }

    // 如果传入的节点值比当前节点值小

    if (node.value < this.value) {

    // 如果当前节点左边没有节点

    if (this.left == null) {

    // 就把node挂在当前节点左边

    this.left = node;

    } else {

    // 当前节点左边有节点,那就递归

    this.left.add(node);

    }

    } else { // 往右边添加

    if (this.right == null) {

    // 就把node挂在当前节点右边

    this.right = node;

    } else {

    // 当前节点右边有节点,那就递归

    this.right.add(node);

    }

    }

    // 添加完一个节点后,如果(右子树高度 - 左子树高度) > 1,左旋转

    if (rightHeight() - leftHeight() > 1) {

    leftRotate();

    }

    // 添加完一个节点后,如果(左子树高度 - 右子树高度) > 1,右旋转

    if (leftHeight() - rightHeight() > 1) {

    rightRotate();

    }

    }

    这样每次添加一个节点后,都会判断是否需要旋转。同样是刚才测试的代码,再次运行,就会发现树的高度、左右子树的高度都发生变化了。

    (4). 双旋转:

    假如现有数列:10,11,7,6,8,9,用上面的测试代码跑一下,发现结果如下:

    树的高度:4

    根节点左子树的高度:1

    根节点右子树的高度:3

    没错,即使进行了左右旋转,它仍然不是平衡二叉树。这种情况,需要进行双旋转。怎么进行双旋转呢?

    就是当进行右旋转的时候,进行如下操作:

    如果它的左子树的右子树高度大于它的左子树的左子树的高度,就先对它的左节点进行左旋转;

    当进行左旋转的时候,进行如下操作:

    如果它的右子树的左子树高度大于它的右子树的右子树的高度,就先对它的右节点进行右旋转;

    代码就是在刚才add方法中加的两个if中再加一层判断,如下:

    // 添加完一个节点后,如果(右子树高度 - 左子树高度) > 1,左旋转

    if (rightHeight() - leftHeight() > 1) {

    if (right != null && right.leftHeight() > right.rightHeight()) {

    right.rightRotate();

    }

    leftRotate();

    return;

    }

    // 添加完一个节点后,如果(左子树高度 - 右子树高度) > 1,右旋转

    if (leftHeight() - rightHeight() > 1) {

    if (left != null && left.rightHeight() > left.leftHeight()) {

    left.leftRotate();

    }

    rightRotate();

    }

    加上这段逻辑,数列10,11,7,6,8,9形成的二叉树也是平衡的了。

    展开全文
  • 目录平衡二叉树左旋转、右旋转、双旋转的原理代码实现资料收获上...对应的解决解决方案就是平衡二叉树一、平衡二叉树(AVL树)平衡二叉树是在二叉查找树的基础上,增加了以下规则:要么是空树,要么左子树和右子树都是...

    目录

    平衡二叉树

    左旋转、右旋转、双旋转的原理

    代码实现

    资料

    收获

    上一篇我们学习实践了二叉查找树,其结合了链表的灵活性和二分查找的高效性。但是可能会出现左右子树的深度不一致或者差别很大,最差的情况是只有一系列的左/右子树,插入和删除速度没有影响,但查询操作将会很慢。

    d944e772fa52

    对应的解决解决方案就是平衡二叉树

    一、平衡二叉树(AVL树)

    平衡二叉树是在二叉查找树的基础上,增加了以下规则:

    要么是空树,要么左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.

    平衡因子BF(Balance Factor):二叉树上的结点上左子树的深度值减去右子树的深度值。平衡二叉树的平衡因子的绝对值小于等于1

    平衡二叉树的常见树有红黑二叉树、AVL、伸展树等,保证查找的高效率。

    二、左旋转、右旋转、双旋转的原理

    左旋转

    当右子树的高度比左子树的高度要大时,要进行左旋转

    具体步骤

    1. 创建一个新的结点newNode,值等于当前结点的值(比如根结点)

    2. 把新结点的左子树设置为当前结点的左子树 newNode.left= curNode.left

    3. 把新结点的右子树设置为当前结点右子树的左子树 newNode.right=curNode.right.left

    4. 把当前结点的值换为当前结点右子树的值

    5. 把当前结点的右子树设置为当前结点的右子树的右子树 curNode.right = curNode.right.right

    6. 把当前结点的左子树设置为新结点

    实现左旋转。

    案例分析a= 4,3,6,5,7,8

    下面来画图一步步拆解

    d944e772fa52

    **右旋转 **

    1. 创建一个新的结点newNode,值等于当前结点的值

    2. 把新结点的右子结点设置为当前结点的右子结点 newNode.right=cur.right

    3. 把新结点的左子结点设置为当前结点左子树的右子树 newNode.left = curNode.left.right

    4. 把当前结点的值换为当前结点的左子结点的值

    5. 把当前结点的左子树设置为当前结点的左子树的左子树 curNode.left=curNode.left.left

    6. 把当前结点的右子树设置为新结点

    案例分析 a= 10,12,8,9,7,6

    基本流程和左旋转一致,下面来画图一步步拆解

    d944e772fa52

    双旋转

    当符合右旋转条件

    如果当前结点左子树的右子树的高度大于左子树的高度

    先对当前结点的左子树这个结点进行左旋转

    然后对当前结点进行右旋转。

    或者符合左旋转条件

    如果当前结点右子树的左子树结点的高度大于右子树的高度

    先对当前结点的右子树这个结点进行右旋转

    然后对当前结点进行左旋转。

    案例分析 a=10,11,7,6,8,9

    下面来画图一步步拆解

    d944e772fa52

    三、代码实现

    rightRotate和leftRoate的具体实现,比上一小节中画的步骤拆解更精简了些,具体见如下代码实现以及注释

    #include

    #include

    using namespace std;

    //定义平衡二叉树模版类

    template

    class AVLTree

    {

    private:

    //定义二叉平衡树的结点

    struct AVLNode

    {

    T element; //元素值

    AVLNode* left; //左子结点

    AVLNode* right; //右子结点

    int height; //该结点距离所有可达的叶子结点的最大值

    //定义结点的构造方法

    AVLNode(const T & theElement, AVLNode *lt,

    AVLNode *rt, int h = 0)

    : element(theElement), left(lt), right(rt), height(h) {}

    };

    //根结点对象

    AVLNode *root;

    /**

    * 构造平衡二叉树树

    *

    * 插入一个值为x的结点到 以t为根结点的树中

    */

    void insert(const T & x, AVLNode * & t)

    {

    //如果插入结点为空,以当前插入的结点为该结点

    if(t == NULL)

    {

    t = new AVLNode(x, NULL, NULL);

    }

    else if(x < t->element) //如果插入的值小于当前结点的值,进行递归操作,插入到当前结点的左子树中

    {

    //递归 插入到合适的位置

    insert(x, t->left);

    //

    if(height(t->left) - height(t->right) == 2)

    {

    rightRotate(t);

    }

    }

    else if(t->element < x) //如果插入的值大于当前结点的值,进行递归操作,插入到当前结点的右子树中

    {

    insert(x, t->right);

    if( height(t->right) - height(t->left) == 2)

    {

    leftRotate(t);

    }

    }

    else

    ; // 如果插入的值和当前结点的值相同,不处理。是的结点中的值不重复

    // 计算当前结点的height值

    t->height = max(height(t->left), height(t->right)) + 1;

    cout<element<height<

    }

    /**

    * Internal method to remove in a subtree.

    * x is the item to remove.

    * t is the node that roots the subtree.

    * Set the new root of the subtree.

    */

    void remove(const T & x, AVLNode * & t)

    {

    if(t == NULL) //no such element

    {

    return;

    }

    else if(x < t->element) //find in left subtree

    {

    remove(x, t->left);

    if(height(t->right) - height(t->left) == 2)

    {

    leftRotate(t);

    }

    }

    else if(t->element < x) //find in right subtree

    {

    remove(x, t->right);

    if( height(t->left) - height(t->right) == 2)

    {

    rightRotate(t);

    }

    }

    else //delete node *t,

    {

    if(t->left == NULL)

    {

    AVLNode* q = t;

    t = t->right;

    delete q;

    }

    else if(t->right == NULL)

    {

    AVLNode* q = t;

    t = t->left;

    delete q;

    }

    else

    {

    t->element = findMax(t->left)->element;

    remove(t->element,t->left);

    }

    }

    if(t)

    t->height = max(height(t->left), height(t->right)) + 1;

    }

    /**

    * 查找以该结点为根结点的树中 值最小的结点

    */

    AVLNode * findMin(AVLNode *t) const

    {

    if(t == NULL)

    return NULL;

    if(t->left == NULL)

    return t;

    return findMin(t->left);

    }

    /**

    * 查找以该结点为根结点的树中 值最大的结点

    */

    AVLNode * findMax(AVLNode *t) const

    {

    if(t != NULL)

    while(t->right != NULL)

    t = t->right;

    return t;

    }

    /**

    * 查找以t为根结点的树中是否右只为x的结点

    */

    bool contains(const T & x, AVLNode *t) const

    {

    if( t == NULL )

    return false;

    else if( x < t->element )

    return contains( x, t->left );

    else if( t->element < x )

    return contains( x, t->right );

    else

    return true; // Match

    }

    /**

    * 清空以t为根结点的树

    */

    void makeEmpty(AVLNode * & t)

    {

    if(t != NULL)

    {

    makeEmpty(t->left);

    makeEmpty(t->right);

    delete t;

    }

    t = NULL;

    }

    //结点-左子结点-右子结点,没有排序的数组的方式打印

    void preOrder(AVLNode *t)const

    {

    if(t)

    {

    cout<element<

    preOrder(t->left);

    preOrder(t->right);

    }

    }

    //左-中-右,中序遍历,以有序的方式打印

    void inOrder(AVLNode *t)const

    {

    if(t)

    {

    inOrder(t->left);

    cout<element<

    inOrder(t->right);

    }

    }

    /**

    * Internal method to print a subtree rooted at t in sorted order.

    */

    void printTree(AVLNode *t) const

    {

    if(t)

    {

    cout<

    preOrder(t);

    cout<

    cout<

    inOrder(t);

    cout<

    }

    }

    /**

    * 深copy

    */

    AVLNode * clone(AVLNode *t) const

    {

    if( t == NULL )

    return NULL;

    else

    return new AVLNode(t->element, clone(t->left), clone(t->right), t->height );

    }

    /**

    * 该结点距离所有可达的叶子结点的最大值

    */

    int height(AVLNode *t) const

    {

    return t == NULL ? -1 : t->height;

    }

    int max(int lhs, int rhs) const

    {

    return lhs > rhs ? lhs : rhs;

    }

    /**

    * 右旋转

    *

    * 和上面的流程图稍微有些不同,简化了流程。

    * 1. 新建一个结点。把当前结点的

    */

    void singleRightRotate(AVLNode * & k2)

    {

    AVLNode *k1 = k2->left;

    k2->left = k1->right;

    k1->right = k2;

    k2->height = max(height(k2->left), height(k2->right)) + 1;

    k1->height = max( height(k1->left), k2->height) + 1;

    k2 = k1;

    }

    /**

    * 左旋转

    *

    * 文章中第二小节中的方案也可行。这个是其进行简化

    */

    void singleLeftRotate(AVLNode * & k1)

    {

    //创建一个新结点,把当前结点的右子结点赋值为新结点

    AVLNode *k2 = k1->right;

    //当前结点的右结点指向 当前结点右子结点的左子结点

    k1->right = k2->left;

    //新创建的结点的左结点指向当前结点

    k2->left = k1;

    //计算当前结点和新结点的height

    k1->height = max(height(k1->left), height(k1->right)) + 1;

    k2->height = max(height(k2->right), k1->height) + 1;

    //把新结点指向当前结点

    k1 = k2;

    }

    /**

    * 双旋转

    * 先左子结点左旋转

    * 在父节点右旋转

    */

    void doubleWithLeftChild(AVLNode * & k3)

    {

    singleLeftRotate( k3->left );

    singleRightRotate( k3 );

    }

    /**

    * Double rotate binary tree node: first right child.

    * with its left child; then node k1 with new right child.

    * For AVL trees, this is a double rotation for case 3-RL.

    * Update heights, then set new root.

    */

    void doubleWithRightChild(AVLNode * & k1)

    {

    singleRightRotate(k1->right);

    singleLeftRotate(k1);

    }

    /**

    * 右旋转

    *

    * 结点的左子树的height减去右子树的height大于1,要进行调节

    * 如果左子树的左子树的height减去左子树的右子树小于等于-1(对于左子树就要在减1),这种情况就要双旋转

    * 否则进行单旋转

    */

    void rightRotate(AVLNode *& t)

    {

    AVLNode* lc = t->left;

    //1. 如果左子树的左子树的height减去左子树的右子树小于等于-1(对于左子树就要在减1),这种情况就要双旋转

    if(height(lc->left) - height(lc->right) == -1)

    {

    doubleWithLeftChild(t); //先子结点左旋转,再父结点右旋转

    }

    else

    {

    singleRightRotate(t); //单右旋转

    }

    }

    /**

    * 左旋转

    *

    * right balance the subtree with root t

    * this method can use for both insert and delete

    */

    void leftRotate(AVLNode *& t)

    {

    AVLNode* rc = t->right;

    if(height(rc->left) - height(rc->right) == 1)

    {

    doubleWithRightChild(t); //先子结点右旋转、再父结点左旋转

    }

    else

    {

    singleLeftRotate(t); //单左旋转

    }

    }

    public:

    AVLTree() : root(NULL){}

    AVLTree(const AVLTree & rhs) : root(NULL)

    {

    *this = rhs;

    }

    ~AVLTree()

    {

    makeEmpty();

    }

    /**

    * 查找当前树中最小值

    */

    const T & findMin() const

    {

    if(!isEmpty())

    {

    return findMin(root)->element;

    }

    }

    /**

    * 查找当前树中最大值

    */

    const T & findMax() const

    {

    if(!isEmpty())

    {

    return findMax(root)->element;

    }

    }

    /**

    * 查找当前树中是否包含值为x的结点

    */

    bool contains(const T & x) const

    {

    return contains(x, root);

    }

    /**

    * 是否是空树

    */

    bool isEmpty() const

    {

    return root == NULL;

    }

    /**

    * 打印树中所有结点的值

    */

    void printTree() const

    {

    if(isEmpty())

    {

    cout << "Empty tree" << endl;

    }

    else

    {

    printTree(root);

    }

    }

    /**

    * 清空结点

    */

    void makeEmpty()

    {

    makeEmpty(root);

    }

    /**

    * 插入值为x的结点到树中

    */

    void insert(const T & x )

    {

    insert(x,root);

    }

    /**

    * 从树中溢出值为x的结点

    */

    void remove(const T & x)

    {

    remove(x,root);

    }

    /**

    * 深copy

    */

    const AVLTree & operator=(const AVLTree & rhs)

    {

    if( this != &rhs )

    {

    makeEmpty( );

    root = clone(rhs.root);

    }

    return *this;

    }

    };

    int main(int argc, char *argv[])

    {

    const int N = 3;

    AVLTree t;

    //insert

    t.insert(4);

    t.insert(3);

    t.insert(6);

    t.insert(5);

    t.insert(7);

    t.insert(8);

    cout<

    t.printTree();

    cout<

    //remove

    t.remove(6);

    cout<

    t.printTree();

    cout<

    t.makeEmpty();

    system("PAUSE");

    return EXIT_SUCCESS;

    }

    四、资料

    五、 收获

    理解二叉查找树存在的问题,以及平衡二叉树对其优化的规则

    通过画图一步步拆解理解其实现原理

    代码实现平衡二叉树的左旋转、右旋转、双旋转

    看似比较复杂的过程,耐心的拆解其流程,逐步对其实现。就像音视频开发之旅一样,内容系统很庞大,拆分成几个系列,每个系列再细分为具体的知识点,逐一学习实践。因为相信,所以看见。

    感谢你的阅读

    下一篇我们学习实践该算法系列的最后一篇“散列表”,欢迎关注公众号“音视频开发之旅”,一起学习成长。

    欢迎交流

    展开全文
  • System.out.println("平衡二叉树右子树的高度为: "+tree.root.rightHeight()); } //遍历二叉树 public void midOrder() { if (root == null) { System.out.println("二叉树为空, 遍历失败"); } else { root....
  • 数 据 结 构 课 程 设 计课程名称: 平衡二叉树的生成院 系:年级专业:学 号:学生姓名:指导教师:开题时间: 年 月 日完成时间: 年 月 日信 息 工 程 学 院摘要本篇论文系计科专业09年末课程设计论文,按照相应...
  • 平衡二叉树创建种情况,需要将2作为根节点,进行顺时针旋转; //平衡二叉树 右旋(顺时针) struct TreeNode *AVL_Right(struct TreeNode *p) { struct TreeNode *q = p -> lchild; p -> lchild =...
  • 假设一棵平衡二叉树的每个结点都标明了平衡因子b,设计个算法,求平衡二叉树的高度。 输入 多组数据,每组数据行,为平衡二叉树的先序序列。输入的数字为该节点的平衡因子。当序列为“#”时,输入结束。 输出...
  • 选取组数据,10个结点来构造平衡二叉树。 int arr[10] = { 2,1,0,3,4,5,6,9,8,7 }; 1. LL型: 首先数据为2的结点作为根结点插入,接着插入1,仍是平衡的,再插入0是,2的平衡因子变为2,此时出现了不平衡...
  • 先看个问题,如果给二叉排序树添加节点时是顺序的,那么创建出来的二叉排序树可能是个单向链表,一直左子树或一直右子树,这样就失去了二叉树的优势(父节点可以含有两个子节点),而且树的高度可能会很大,查询...
  • 前言需求介绍 题:我们从个数列(1,2,3,4,5,6),来说明构成二叉排序树的一些问题 ...、什么是平衡二叉树 基本介绍 平衡二叉树也叫平衡二叉搜索树(Self balancing binary searchtree)又被称为AVL树, 可以保证查询
  • Java—判断一棵树是否为平衡二叉树 思路:从根节点开始,先判断左右子树的高度差是否超过1,然后接着判断左右子树是否是平衡二叉树 代码实现: /** * @Author shall潇 * @Date 2021/3/4 * @Description 平衡...
  •   平衡二叉树的左右子树的高度差小于等于1。或者说其左子树的高度减去右子树的高度,差值的绝对值小于等于1平衡二叉树,仍然属于排序二叉树。其中序排列里,节点的关键字仍然按递增有序排列。   为了纪念对...
  • 正因为链式二叉树中有很多的空指针,可以让这些指针这向下个节点,这样在遍历时可以不用递归,二使用循环,可以提高遍历速度。 #include <stdio.h> #include <stdlib.h> #include <stdbool.h> ...
  • 近期在学习数据结构上关于平衡二叉树的知识,看了严老师的思路,感觉用java写出递归的构建方式有点困难,由于当中的递归须要把引用传进去,所以感觉是要实现起来比較麻烦,所以就首先想到使用非递归的方式来实现构建...
  • 平衡二叉树就是对二叉查找树的优化升级,它要求每个节点的左右子树的高度相差不大于1 1.平衡二叉树的查找 平衡二叉树和二叉排序树的查找是摸一样的。 2.平衡二叉树的顺序输出 平衡二叉树的中序遍历和二叉排序...
  • 平衡二叉树(AVL树)

    2021-01-24 22:19:15
    平衡二叉树是具有以下特点的二叉查找树:它是一棵空树或它的左右两个子树的高度差的绝对值不超过 1, 并且左右两个子树都是一棵平衡二叉树。 图 平衡二叉树 图二 非平衡二叉树 1.2 为什么...
  • 1如图1。10左边的数都比它小,右边的数都比它大。对于9和15来说也是一样。所以如果要插入个数字14,那么该如何做呢?图2如图2。14比10大,所以在10的右边。比15小,所以在15的左边。比12大,所以在12的右边。二...
  • 平衡二叉树的查找、折半查找的实现、Hash表的实现(除留余数法)
  • 平衡二叉树 与二叉搜索树不同之处是结点结构里多了平衡因子 balance factor : 绝对值(左子树的高度-右子树的高度) 定义 要么是二叉搜索树要么是空树 左右子树的高度差不超过 左右子树都是平衡二叉树 高度的...
  • 实现平衡二叉树创建,插入,删除,查询操作。并求出所构建平衡二叉排序树的平均查找长度ASL。 (1)以二叉链表作为平衡二叉树的存储结构; (2)输入个关键字序列,建立对应的平衡二叉树; (3)向平衡二叉树中...
  • 平衡二叉树(AVL 树)

    2021-04-09 13:23:53
    给你个数列{1,2,3,4,5,6},要求创建一颗二叉排序树(BST), 并分析问题所在 左边 BST 存在的问题分析: 左子树全部为空,从形式上看,更像个单链表. 插入速度没有影响 查询速度明显降低(因为需要依次比较), ...
  • 学习平衡二叉树笔记

    2021-03-11 02:29:57
    个案例(说明二叉排序树可能的问题),给你个数列{ 1,2,3,4,5,6 } ,要求创建一颗二叉排序树(BST),并分析问题所在: 左子树全部为空,从形式上看,更像个单链表; 插入速度没有影响; 查询速度明显降低(因为...
  • 案例:给定数组{1,2,3,4,5,6},要求创建一棵二叉排序树(BST)。 按照此数组创建的二叉排序树如图所示: 分析上图BST树可发现如下问题所在: 左子树全部为空,从形式上看,更像个单链表 查询速度明显降低,...
  • 平衡二叉树(C/C++)

    2020-12-28 11:06:22
    描述: 平衡二叉树是二叉搜索树的改进,本文基于你已了解...为提升二叉排序树的平均效率,可将其升级为平衡二叉树,其特点是:所有根结点的左子树和右子树深度差不超过1。其中左右子树的深度差也称为平衡因子。每插入
  • 平衡二叉树种特殊的二叉排序树,理解平衡二叉树首先要理解什么是二叉排序树。 如果已经了解二叉排序树可以直接看下面平衡二叉树内容。 二叉排序树(Binary Sort Tree) 所谓二叉排序树(BST)即: (1)若该树的左...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 30,712
精华内容 12,284
关键字:

创建一棵平衡二叉树