AVL树中分割后子树的大小
创始人
2024-11-13 02:00:25
0

AVL树中,当进行分割操作时,需要计算新生成的两棵子树的大小,即左子树的大小和右子树的大小。下面是一个示例代码:

struct Node { int val; int height; int size; Node *left; Node *right;

Node(int val) { this->val = val; height = 1; size = 1; left = NULL; right = NULL; } };

int getSize(Node *root) { if (!root) { return 0; } return root->size; }

void updateSize(Node *root) { root->size = getSize(root->left) + getSize(root->right) + 1; }

void updateHeight(Node *root) { root->height = max(getHeight(root->left), getHeight(root->right)) + 1; }

void update(Node *root) { updateSize(root); updateHeight(root); }

int getBalanceFactor(Node *root) { if (!root) { return 0; } return getHeight(root->left) - getHeight(root->right); }

Node *rightRotate(Node *root) { Node *newRoot = root->left; root->left = newRoot->right; newRoot->right = root; update(root); update(newRoot); return newRoot; }

Node *leftRotate(Node *root) { Node *newRoot = root->right; root->right = newRoot->left; newRoot->left = root; update(root); update(newRoot); return newRoot; }

Node *insert(Node *root, int val) { if (!root) { return new Node(val); }

if (val < root->val) { root->left = insert(root->left, val); } else { root->right = insert(root->right, val); }

update(root);

int balanceFactor = getBalanceFactor(root);

if (balanceFactor > 1 && getBalanceFactor(root->left) >= 0) { return rightRotate(root); } if (balanceFactor < -1

上一篇:AVL树中的旋转

下一篇:AVL树中序遍历

相关内容

热门资讯

黑科技辅助挂!aapoker下... 黑科技辅助挂!aapoker下载教程,德州ai代打,2025版教程(有挂透视)是一款可以让一直输的玩...
黑科技辅助挂!微扑克数据,德州... 黑科技辅助挂!微扑克数据,德州ai辅助有用,揭秘教程(有挂功能);黑科技辅助挂!微扑克数据,德州ai...
黑科技辅助挂!wpk透视外挂,... 黑科技辅助挂!wpk透视外挂,aapokerai辅助,微扑克教程(今日头条)是一款可以让一直输的玩家...
黑科技辅助挂!wepoke a... 黑科技辅助挂!wepoke ai辅助代打,微扑克下载,高科技教程(有挂详细)是一款可以让一直输的玩家...
黑科技辅助挂!微扑克发牌,智星... 您好:智星德州菠萝外挂这款游戏可以开挂的,确实是有挂的,很多玩家在这款游戏中打牌都会发现很多用户的牌...
黑科技辅助挂!德扑统计软件,云... 黑科技辅助挂!德扑统计软件,云扑克内置辅助器,德州教程(有挂秘诀)是一款可以让一直输的玩家,快速成为...
黑科技辅助挂!德扑线上创建房间... 您好:德扑线上创建房间这款游戏可以开挂的,确实是有挂的,很多玩家在这款游戏中打牌都会发现很多用户的牌...
黑科技辅助挂!wepoke有辅... 黑科技辅助挂!wepoke有辅助挂,德扑之星可以清楚数据,存在挂教程(有挂方法);暗藏猫腻!德扑之星...
黑科技辅助挂!aapoker外... 您好:aapoker外挂购买这款游戏可以开挂的,确实是有挂的,很多玩家在这款游戏中打牌都会发现很多用...
黑科技辅助挂!wepoke外挂... 黑科技辅助挂!wepoke外挂检测方法,德扑手机上算胜率的软件,分享教程(详细教程);德扑手机上算胜...